席曉慧， 王遂纏， 高鵬

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

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

文獻(xiàn)[4]提出了頂點(diǎn)魔幻全標(biāo)號(hào)， 之后該標(biāo)號(hào)被越來越多的學(xué)者關(guān)注和研究． 通過文獻(xiàn)[4-9]可知， 在滿足一定的條件下， 特殊圖圈圖Cn、 路圖Pn，Km，m，Km，m-e以及Kn存在頂點(diǎn)魔幻全標(biāo)號(hào)． 該標(biāo)號(hào)的研究成果主要集中在特殊圖， 針對(duì)一般圖的結(jié)果較少， 研究方法絕大多數(shù)都是傳統(tǒng)方法， 利用計(jì)算機(jī)算法來研究的文獻(xiàn)非常少見．

本文利用頂點(diǎn)魔幻全標(biāo)號(hào)優(yōu)化算法得到有限點(diǎn)內(nèi)的隨機(jī)圖標(biāo)號(hào)， 進(jìn)一步研究太陽圖Sn，GSn，Sn，m以及圖P(n， 1)的頂點(diǎn)魔幻全標(biāo)號(hào)． 通過分析算法結(jié)果， 發(fā)現(xiàn)上述幾類太陽圖的標(biāo)號(hào)特性， 總結(jié)出若干定理并給出證明．

1 基礎(chǔ)知識(shí)

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

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

圖1 示例圖

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

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

頂點(diǎn)魔幻全標(biāo)號(hào)算法基于解空間的遞歸搜索算法， 為了方便介紹算法步驟， 下面給出優(yōu)化前的解空間的定義．

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

2 頂點(diǎn)魔幻全標(biāo)號(hào)優(yōu)化算法

其中，Sp和Sq分別表示頂點(diǎn)和邊的標(biāo)號(hào)值總和．

圖G的每個(gè)頂點(diǎn)滿足

當(dāng)圖G滿足VMTL時(shí)， 魔幻常數(shù)k的取值范圍為

(1)

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

(2)

其中優(yōu)化算法為

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

頂點(diǎn)魔幻全標(biāo)號(hào)優(yōu)化算法實(shí)現(xiàn)的主要思路如下：

(i) 由文獻(xiàn)[12]中的非同構(gòu)圖算法生成有限點(diǎn)內(nèi)的所有非同構(gòu)圖；

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

(iii) 利用解空間優(yōu)化算法對(duì)解空間進(jìn)行優(yōu)化， 將不可用的解空間刪除；

(iv) 搜索解空間得到滿足條件的標(biāo)號(hào)值．

頂點(diǎn)魔幻全標(biāo)號(hào)優(yōu)化算法實(shí)現(xiàn)如下：

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

3 算法結(jié)論及證明

利用算法得到了圖Sn，GSn，Sn，m及圖P(n， 1)(3≤n≤6)的VMTL標(biāo)號(hào)， 經(jīng)過分析得到以下標(biāo)號(hào)結(jié)論：

定理1對(duì)于太陽圖Sn， 當(dāng)n≥3時(shí)存在魔幻常數(shù)k=5n+3的頂點(diǎn)魔幻全標(biāo)號(hào)．

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的頂點(diǎn)集合

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}

對(duì)于太陽圖Sn(n≥3)， 根據(jù)算法執(zhí)行結(jié)果， 分析得到該圖存在以下標(biāo)號(hào)：

太陽圖Sn的頂點(diǎn)和邊標(biāo)號(hào)集合分別為

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

定理2對(duì)于圖GSn， 當(dāng)n≥3時(shí)存在魔幻常數(shù)k=8n+2的頂點(diǎn)魔幻全標(biāo)號(hào)．

證設(shè)圖GSn的頂點(diǎn)集合為

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}

對(duì)于圖GSn(n≥3)， 根據(jù)算法執(zhí)行結(jié)果， 分析得到該圖存在以下標(biāo)號(hào)：

對(duì)于圖GSn， 有

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

對(duì)于圖中任意點(diǎn)vi，k滿足公式

即定理2成立， 以圖GS10為例， 將標(biāo)號(hào)結(jié)論應(yīng)用到圖標(biāo)號(hào)中， 得到圖GS10的VMTL標(biāo)號(hào)如圖2(b)所示．

圖2 VMTL示例圖

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

證由頂點(diǎn)魔幻全標(biāo)號(hào)優(yōu)化算法可知圖Sn，m(n≥3，m≥2)不存在標(biāo)號(hào)， 即算法輸出為圖的鄰接矩陣． 設(shè)圖Sn，m(n≥3，m≥2)的頂點(diǎn)集合為

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存在頂點(diǎn)魔幻全標(biāo)號(hào)， 由定義1可知標(biāo)號(hào)集合為

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

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

(3)

(4)

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

定理4對(duì)于圖P(n， 1)， 當(dāng)n≥3時(shí)存在魔幻常數(shù)k=10n+1的頂點(diǎn)魔幻全標(biāo)號(hào)．

證設(shè)圖P(n， 1)的頂點(diǎn)集合為

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}． 對(duì)于圖P(n， 1)(n≥3)， 根據(jù)算法執(zhí)行結(jié)果， 分析得到該圖存在以下標(biāo)號(hào)：

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

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

定理5對(duì)于圖P(n， 1)， 當(dāng)n≥3時(shí)存在魔幻常數(shù)k=10n+2的頂點(diǎn)魔幻全標(biāo)號(hào)．

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

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

圖3 廣義Petersen圖的VMTL

4 結(jié)束語

本文利用VMTL算法得到有限點(diǎn)內(nèi)的VMTL圖集， 通過對(duì)標(biāo)號(hào)集合分析得到： 太陽圖Sn當(dāng)n≥3時(shí)存在魔幻常數(shù)k=5n+3的頂點(diǎn)魔幻全標(biāo)號(hào)； 圖GSn當(dāng)n≥3時(shí)存在魔幻常數(shù)k=8n+2的頂點(diǎn)魔幻全標(biāo)號(hào)； 圖P(n， 1)當(dāng)n≥3時(shí)存在魔幻常數(shù)k=10n+1和k=10n+2的頂點(diǎn)魔幻全標(biāo)號(hào)． 同時(shí)得到廣義太陽圖Sn，m(n≥3，m≥2)不存在頂點(diǎn)魔幻全標(biāo)號(hào)， 并證明了結(jié)論的正確性．