若干太陽圖的頂點魔幻全標號優化算法①

席曉慧， 王遂纏， 高鵬

甘肅省氣象信息與技術裝備保障中心， 蘭州 730020

圖的標號來源于1967年Rosa提出的優美樹猜想， 它的出現使得很多生活中的實際問題得到解決， 如優美圖可應用在密碼設計、 通訊網絡編址、 交通物流控制、 雷達脈沖編碼及X射線密碼技術等[1-4]． 由于圖形能夠直觀有效地解決實際生活中的一些難以解決的問題， 所以衍生了圖論的一系列應用． 因此， 研究圖的標號不僅能豐富圖論的研究成果， 而且能更廣泛地應用于實際生活中的問題．

文獻[4]提出了頂點魔幻全標號， 之后該標號被越來越多的學者關注和研究． 通過文獻[4-9]可知， 在滿足一定的條件下， 特殊圖圈圖Cn、 路圖Pn，Km，m，Km，m-e以及Kn存在頂點魔幻全標號． 該標號的研究成果主要集中在特殊圖， 針對一般圖的結果較少， 研究方法絕大多數都是傳統方法， 利用計算機算法來研究的文獻非常少見．

本文利用頂點魔幻全標號優化算法得到有限點內的隨機圖標號， 進一步研究太陽圖Sn，GSn，Sn，m以及圖P(n， 1)的頂點魔幻全標號． 通過分析算法結果， 發現上述幾類太陽圖的標號特性， 總結出若干定理并給出證明．

1 基礎知識

圖G(p，q)表示的是包含p個頂點，q條邊， 且頂點集合為V(G)， 邊集合為E(G)的簡單連通圖． 頂點v的度記為d(v)；Cn指的是n個頂點的圈圖．

定義2[3]太陽圖Sn是由n個頂點的Cn和n片葉子組成， 其中Cn的每一頂點只能與一片葉子鄰接， 如圖1(a)所示． 在太陽圖Sn的每一個葉子節點懸掛一個點構成的圖記為圖GSn， 如圖1(b)所示．

圖1 示例圖

定義3[3]Cn的每個頂點vi(i∈{1， 2， …，n})連接m個頂點ui(i∈{1， 2， …，m})所構成的圖記為圖Sn，m， 如圖1(c)所示．

定義4[3]將太陽圖Sn的每個葉子相連構成的圖記為圖p(n， 1)， 如圖1(d)所示．

頂點魔幻全標號算法基于解空間的遞歸搜索算法， 為了方便介紹算法步驟， 下面給出優化前的解空間的定義．

表1 VMTL解空間θ(p， q， k)

2 頂點魔幻全標號優化算法

其中，Sp和Sq分別表示頂點和邊的標號值總和．

圖G的每個頂點滿足

當圖G滿足VMTL時， 魔幻常數k的取值范圍為

(1)

根據公式(1)及定義5實現VMTL算法， 并在算法中增加判斷函數對解空間進行優化， 刪除不滿足判斷函數條件的解空間， 減少算法的時間復雜度， 判斷函數如公式(2)所示：

(2)

其中優化算法為

解空間優化算法Requre 初始化解空間, 圖G的度序列及相同d(v)的個數 Repeat 從訓練集解空間中選擇標號值樣本{(1, k-1), (2, k-2), …, (p+q, k-p+q)}; 參數更新 d(vi)+1|← 符合條件的樣本個數 Until 樣本集篩選完成

頂點魔幻全標號優化算法實現的主要思路如下：

(i) 由文獻[12]中的非同構圖算法生成有限點內的所有非同構圖；

(ii) 獲取圖G的度序列、 魔幻常數， 同時結合定義5得到解空間；

(iii) 利用解空間優化算法對解空間進行優化， 將不可用的解空間刪除；

(iv) 搜索解空間得到滿足條件的標號值．

頂點魔幻全標號優化算法實現如下：

VMTL算法Input 圖G(p, q)的鄰接矩陣Output 標號結果Begin1. C ←(p+q)(p+q+1)/22. for i ← 1 to p+q3. k ← (i+C)/p 4. 利用算法1得到當前k值下的解空間φ(p, q, k)5. if(|φ|

3 算法結論及證明

利用算法得到了圖Sn，GSn，Sn，m及圖P(n， 1)(3≤n≤6)的VMTL標號， 經過分析得到以下標號結論：

定理1對于太陽圖Sn， 當n≥3時存在魔幻常數k=5n+3的頂點魔幻全標號．

where is the reduced Plank constant , is the angular frequency, and μ is the reduced mass, which can be calculated by . The electron and hole effective masses (and) are extracted from E-k energy band diagrams based on

證太陽圖Sn的頂點集合

V(Sn)={v1，v2， …，vn，u1，u2， …，un}

邊集合為

E(Sn)={x1，x2， …，xn，y1，y2， …，yn}

即

|V(Sn)|=2n|E(Sn)|=2n

f(v)∪f(e)={1， 2， …， 4n}

對于太陽圖Sn(n≥3)， 根據算法執行結果， 分析得到該圖存在以下標號：

太陽圖Sn的頂點和邊標號集合分別為

由f(vi)和f(ui)的標號可知f(vi)和f(ui)兩兩互不相交， 且為頂點集f(v)到數集{n，n+2， 2n+2， 2n+3， 2n+4， …， 3n， 3n+2， 3n+3， …， 4n}的一一映射． 同理，f(xi)和f(yi)兩兩互不相交， 且為邊集f(e)到數集{1， 2， …，n-1，n+1， 2n+1， 2n， 2n-1， …，n+3， 3n+1}的一一映射． 則f(v)∪f(e)={1， 2， …， 4n}， 對于圖中任意點vi，w為v1的關聯點， 魔幻常數k滿足以下公式：

定理2對于圖GSn， 當n≥3時存在魔幻常數k=8n+2的頂點魔幻全標號．

證設圖GSn的頂點集合為

V(GSn)={v1，v2， …，vn，u1，u2， …，un，w1，w2， …，wn}

邊集合為

E(GSn)={v1v2，v2v3， …，vnvn-1，v1vn，u1w1，u2w2， …，unwn，u1v1，u2v2， …，unvn}

即

f(v)∪f(e)={1， 2， …， 6n}

對于圖GSn(n≥3)， 根據算法執行結果， 分析得到該圖存在以下標號：

對于圖GSn， 有

f(v)∪f(e)={1， 2， …， 6n}

對于圖中任意點vi，k滿足公式

即定理2成立， 以圖GS10為例， 將標號結論應用到圖標號中， 得到圖GS10的VMTL標號如圖2(b)所示．

圖2 VMTL示例圖

定理3廣義太陽圖Sn，m(n≥3，m>1)不存在頂點魔幻全標號．

證由頂點魔幻全標號優化算法可知圖Sn，m(n≥3，m≥2)不存在標號， 即算法輸出為圖的鄰接矩陣． 設圖Sn，m(n≥3，m≥2)的頂點集合為

V={v1，v2， …，vn，u1，1，u1，2， …，u1，m，u2，1， …，un，m}

邊集合為

E={v1v2，v2v3， …，vnvn-1}∪{v1vn，u1，1v1，u1，2v1， …，u1，mv1}∪

{u2，1v2，u2，2v2， …，u2，mv2}∪…∪{un，1vn，un，2vn， …，un，mvn}

如圖1(c)所示． 即|V|=n+mn， |E|=n+mn， 如果圖Sn，m存在頂點魔幻全標號， 由定義1可知標號集合為

f(v)∪f(e)={1， 2， …， 2n(m+1)}

由圖Sn，m可知

d(v1)=d(v2)=…=d(vn)=m+2d(u1，1)=d(u1，2)=…=d(u1，m)= 1

由文獻[8]的定理5可以得到k取最小值時， 圖中d(v)=m+2的頂點及其關聯邊取標號集合{1， 2， …， 2n+mn}， 且頂點集合{v1，v2， …，vn}兩頂點之間的關聯邊取標號集合{1， 2， …，n}．k取最大值時，d(v)=2的頂點集合u={u1，1，u1，2， …，un，m}取標號值{2n+1， 2n+2， …， 2n+2mn}． 即

(3)

(4)

當圖Sn，m滿足頂點魔幻全標號時， 有kmin≤kmax， 結合公式(3)和(4)， 當圖Sn，m存在頂點魔幻全標號時，n和m滿足m2n+m-3n+1≤0． 通過分析可知， 當n≥3，m=1時有解， 該圖為太陽圖， 其標號規律如定理1； 而當n≥3，m>1時無解， 因此不存在頂點魔幻全標號． 定理3成立．

定理4對于圖P(n， 1)， 當n≥3時存在魔幻常數k=10n+1的頂點魔幻全標號．

證設圖P(n， 1)的頂點集合為

V(P(n， 1))={v1，v2， …，vn，u1，u2， …，un}

邊集合為

E(P(n， 1))={x1，x2， …，xn，y1，y2， …，yn，u1v1，u2v2， …，unvn}

即V|P(n， 1)|=2n，E|P(n， 1)|=3n， 所以f(v)∪f(e)={1， 2， …， 5n}． 對于圖P(n， 1)(n≥3)， 根據算法執行結果， 分析得到該圖存在以下標號：

對于圖p(n， 1)， 其頂點和邊的集合分別為

綜上所述， 定理4成立． 以圖P(9，1)為例， 由標號結論得到圖P(9，1)，k=91的VMTL標號如圖3(a)所示．

定理5對于圖P(n， 1)， 當n≥3時存在魔幻常數k=10n+2的頂點魔幻全標號．

證由定理4可知圖P(n， 1)的f(v)∪f(e)={1， 2， …， 5n}， 由算法可知圖P(n， 1)(n≥3)存在以下標號：

定理5成立． 以圖P(9，1)為例， 由標號結論得到圖P(9，1)，k=92的VMTL標號如圖3(b)所示．

圖3 廣義Petersen圖的VMTL

4 結束語

本文利用VMTL算法得到有限點內的VMTL圖集， 通過對標號集合分析得到： 太陽圖Sn當n≥3時存在魔幻常數k=5n+3的頂點魔幻全標號； 圖GSn當n≥3時存在魔幻常數k=8n+2的頂點魔幻全標號； 圖P(n， 1)當n≥3時存在魔幻常數k=10n+1和k=10n+2的頂點魔幻全標號． 同時得到廣義太陽圖Sn，m(n≥3，m≥2)不存在頂點魔幻全標號， 并證明了結論的正確性．