趙 科， 李 敬 文， 魏 眾 德

( 蘭州交通大學(xué) 電子與信息工程學(xué)院， 甘肅 蘭州 730070 )

0 引 言

國內(nèi)外學(xué)者主要在研究特殊圖的優(yōu)雅性，例如圈、路、扇圖等目前已經(jīng)證明是優(yōu)雅的．Rosa提出非優(yōu)美圖產(chǎn)生的3個原因[8]：(1)圖G的頂點過多而邊數(shù)太少；(2)圖G邊數(shù)過多而頂點太少；(3)圖G的邊數(shù)具有錯誤的奇偶性．以上條件同樣適用于優(yōu)雅標(biāo)號．本文根據(jù)文獻(xiàn)[9]中生成非同構(gòu)圖的算法，得到9個點之內(nèi)的所有連通圖，結(jié)合設(shè)計的優(yōu)雅標(biāo)號算法，得到所有優(yōu)雅圖和非優(yōu)雅圖的數(shù)量．

1 定義及基本概念

定義1[1]對于任意的簡單連通圖G=(V，E)，如果對每一個頂點v∈V，都對應(yīng)一個非負(fù)整數(shù)f(v)(f(v)為頂點v的標(biāo)號)，且滿足

(1)?v1，v2∈V，如果v1≠v2，則f(v1)≠f(v2)；

(2){f(v)|v∈V}∈{0，1，2，…，|E|}；

(3)?e1，e2∈E，如果e1≠e2，則g(e1)≠g(e2)，其中g(shù)(e)=(f(v1)+f(v2))mod (q+1)，e=v1v2；

(4){g(e)|e∈E}∈{1，2，…，|E|}

則稱f為圖G的一個優(yōu)雅標(biāo)號，圖G稱為優(yōu)雅圖．

定義2對于邊數(shù)為q的優(yōu)雅圖，滿足以下條件：

(1)min(f(u)，f(v))≥0；

(2)max(f(u)，f(v))≤|E|；

(3)(f(u)+f(v))mod (q+1)=g(e)，且g(e)≠0

則稱為邊數(shù)為q的優(yōu)雅集合，又稱q優(yōu)雅空間．如表1所示，對于每個g(e)，只取一個二元組(m，n)，這些二元組集合組成的圖都是優(yōu)雅的．

m的取值范圍為{0，1，…，q}；n的取值范圍可通過如下公式：n=g(e)-m≥0？g(e)-m：g(e)-m+q+1判斷取得．

在優(yōu)雅空間中，當(dāng)m=n時，因每個點的標(biāo)號不同，故去除；為了避免重復(fù)，當(dāng)m>n時，去除該二元組(m，n)．具體如表1所示．

表2為(5，10)圖的優(yōu)雅空間，其中粗體的二元組為它的一種優(yōu)雅標(biāo)號，如圖1所示．

表1 q優(yōu)雅空間

表2 q=10優(yōu)雅空間

圖1 (5，10)圖優(yōu)雅標(biāo)號

猜想1[1]所有的樹都是優(yōu)雅的．

2 解決思路及算法

2.1 解決思路

本文所研究的圖均為簡單連通圖，具有p個頂點和q條邊的圖稱為(p，q)圖，其中q的范圍為p-1≤q≤p(p-1)/2．當(dāng)p-1>q時，該圖為非連通圖，不在本文研究范圍之內(nèi)．判斷任意一個連通圖是否為優(yōu)雅圖的解決思路如下：

(1)根據(jù)(p，q)圖的邊數(shù)q生成圖的優(yōu)雅空間，可組合成的圖G如下：

(2)G個圖都是優(yōu)雅圖，由連通圖與非連通圖組成；

(3)任意一個連通圖若是優(yōu)雅圖，則一定在圖G中；若不在其中，則該圖一定為非優(yōu)雅圖．

2.2 設(shè)計的優(yōu)雅圖判定算法

算法的基本思想是：對于給定的任意一個連通圖，可以用矩陣形式將它表示，記為M(n，n)，其中n表示頂點個數(shù)，若頂點i與頂點j之間有邊，則Mij=1(i≠j)，若無邊Mij=0(i≠j)．標(biāo)號過程為根據(jù)該圖的邊q生成優(yōu)雅空間，先根據(jù)預(yù)判函數(shù)判斷q=1時的二元組(i，j)是否可用，若可用將相鄰的頂點標(biāo)號，將兩個頂點對應(yīng)的邊標(biāo)為1，邊數(shù)以1遞增，直到邊為q+1時標(biāo)注成功．在選擇二元組過程中，若二元組(i，j)不可用，則尋找下一個二元組．

具體算法步驟如下：

Input：一個圖的鄰接矩陣M(n，n)

Output：該圖是否為優(yōu)雅圖

1.Begin：

2.Calculate the number of edges， generate an Elegant space；

3.edgeCount∈{1，2，…，q，q+1} SetedgeCount=1；

4.DeepSearch(edgeCount)

5.{

6. If (edgeCount=q+1)

7. Success and quit；

8. Select a two tuple (p1，p2)；

9. Forp10→q

10.p2=edgeCount-p1>=0?edgeCount-p1：edgeCount-p1+q+1；

11.edgeCount=(p1+p2)%(q+1)

12. Checkp1andp2in Matrix；

13. Fori1→n

14. If (Miican be used)Mii=p1；

15. Forj1→nandi≠j

16. If (Mjjcan be used &&Mij==1)

17. {

18.Mjj=p2；

19.Mij=edgeCount；

20.edgeCount=edgeCount+1；

21. DeepSearch(edgeCount)；

22. }

23. End Forj1→nandi≠j

24. End Fori1→n

25.}

26.If (Elegant space is Finished)

27. This Graph is UnElegant；

28.End

3 算法結(jié)果與分析

本文根據(jù)文獻(xiàn)[9]提供的算法，生成9個點之內(nèi)的所有非同構(gòu)圖，用鄰接矩陣的形式將其保存到p_q.txt文件中．運用本文設(shè)計的任意圖的優(yōu)雅判斷算法，對所有圖進(jìn)行驗證，列表統(tǒng)計了9個點內(nèi)所有優(yōu)雅圖和非優(yōu)雅圖的數(shù)目，并對比了各點對應(yīng)的圖中非優(yōu)雅圖所占比率．

3.1 點數(shù)為2～9的所有圖優(yōu)雅圖個數(shù)統(tǒng)計

當(dāng)q=p-1時，圖為樹圖；當(dāng)q=p(p-1)/2時，圖為完全圖．即對于所有的連通圖，其邊數(shù)q的取值范圍為p-1≤q≤p(p-1)/2．

程序結(jié)果表明，當(dāng)p=2時，圖的個數(shù)為1，且為優(yōu)雅圖；當(dāng)p=3，q=2，3時，圖的個數(shù)為2，且都是優(yōu)雅圖，為簡潔不再列表說明．對點數(shù)4～9的所有圖列表給出，其中N(UG)為非優(yōu)雅圖個數(shù)，N(EG)為優(yōu)雅圖個數(shù)，N(G)為圖的總數(shù)，見表3～8．

由表3～8可以看出，(4，3)、(6，5)、(8，7)圖為樹圖，其中至少有一個非優(yōu)雅樹圖，即圖G有太多的頂點且沒有足夠的邊會導(dǎo)致產(chǎn)生非優(yōu)雅圖；(6，14-15)、(7，20-21)、(8，25-28)、(9，31-36)圖都是稠密圖，且都是非優(yōu)雅圖，即圖G有太多的邊且沒有足夠多的頂點會導(dǎo)致產(chǎn)生非優(yōu)雅圖；(4，4-6)、(5，5-10)、(6，6-13)、(7，7-15)、(8，8-17)、(9，9-21)圖中，當(dāng)邊q=1(mod 4)時，存在非優(yōu)雅圖，且所占比例逐漸遞增，而當(dāng)q≠1(mod 4)時，所有圖都是優(yōu)雅圖，即圖G的邊數(shù)具有錯誤的奇偶性會產(chǎn)生非優(yōu)雅圖．

表3 點數(shù)為4的圖

表4 點數(shù)為5的圖

表5 點數(shù)為6的圖

表6 點數(shù)為7的圖

表7 點數(shù)為8的圖

表8 點數(shù)為9的圖

3.2 定理和猜想

根據(jù)上述實驗結(jié)果，得到以下結(jié)論：

定理1當(dāng)3≤p≤9時，樹T(p，q)幾乎都是優(yōu)雅的，其中

證明(1)當(dāng)p為奇數(shù)時，所有的樹T(p，q)的優(yōu)雅性如表9所示．由表可知，所有的奇樹T(p，q) 都是優(yōu)雅的．

(2)當(dāng)p為偶數(shù)時，樹T(p，q)的優(yōu)雅性如表10所示．由表可知，隨著點數(shù)的增加，非優(yōu)雅樹的比率遞減．

表9 3～9個點內(nèi)所有奇樹的非優(yōu)雅數(shù)對比

表10 3～9個點內(nèi)所有偶樹的非優(yōu)雅數(shù)對比

綜合(1)、(2)可知，當(dāng)3≤p≤9時，樹T(p，q)幾乎都是優(yōu)雅的．

定理2當(dāng)3≤p≤9時，除了圖C5、C9外，所有的單圈圖都是優(yōu)雅的．

證明9個點以內(nèi)的單圈圖由表3～8得出．

猜想2當(dāng)q≠1(mod 4)時，所有的單圈圖是優(yōu)雅的．

定理3當(dāng)2≤p≤9，p≤q≤2p且q≠1(mod 4)時，所有(p，q)圖都是優(yōu)雅的．

證明由表3～8可知，當(dāng)q=p-1時，所有的圖都是樹圖，滿足定理1．當(dāng)p≤q≤2p且q≠1(mod 4)時，所有(p，q)圖都是優(yōu)雅圖．而q=1(mod 4)時，其中部分圖是非優(yōu)雅的．由此可知，圖的優(yōu)雅性與圖的邊數(shù)存在一定的相關(guān)性．

猜想3當(dāng)p-1≤q≤2p且q≠1(mod 4)時，所有圖都是優(yōu)雅的．

雖然非優(yōu)雅圖較多，但在圖的總數(shù)中占比極小，如表11所示．除頂點p=2，3之外，隨著頂點數(shù)的增加，非優(yōu)雅圖占比越來越小，從而提出猜想4．

表11 2～9個點內(nèi)所有圖的優(yōu)雅數(shù)對比

猜想4所有圖幾乎都是優(yōu)雅圖．

3.3 9個點之內(nèi)的部分非優(yōu)雅圖

雖然9個點以內(nèi)的所有非優(yōu)雅圖數(shù)量占總圖數(shù)的比例較低，但數(shù)量依然較大，只選取其中比較特殊及常見的部分非優(yōu)雅圖，命名方式為p_q_number，其中number表示為(p，q)圖中列舉的非優(yōu)雅圖順序，若只有一個非優(yōu)雅圖，則number予以省略．

點數(shù)為4的非優(yōu)雅圖已經(jīng)由文獻(xiàn)[2]給出，共有1個，如圖2(a)所示．

點數(shù)為5的非優(yōu)雅圖有1個，由文獻(xiàn)[1]給出，并證明了圈圖Cn的優(yōu)雅性，如圖2(b)所示．

(a)p=4

(b)p=5

圖2p=4，5的非優(yōu)雅圖

Fig.2 Non-elegant graph whenpis equal to 4, 5

點數(shù)為6的非優(yōu)雅圖共4個，如圖3所示．點數(shù)為7的非優(yōu)雅圖共16個，部分如圖4所示．

圖3 p=6的非優(yōu)雅圖

圖4 p=7的部分非優(yōu)雅圖

點數(shù)為8的非優(yōu)雅圖共86個，部分如圖5所示．點數(shù)為9的部分非優(yōu)雅圖如圖6所示．

3.4 9個點內(nèi)部分優(yōu)雅圖

為了證明本文提出算法的可行性及有效性，隨機選取了部分優(yōu)雅圖，其頂點數(shù)及邊數(shù)都較大，在不借助計算機程序的條件下，傳統(tǒng)人力標(biāo)注較難完成．(8，19)、(8，23)、(9，14)、(9，18)、(9，20)、(9，29)圖部分優(yōu)雅圖如圖7、8所示．

圖5 p=8的部分非優(yōu)雅圖

圖7 p=8的部分優(yōu)雅圖

圖8 p=9的部分優(yōu)雅圖

4 結(jié) 語

圖的標(biāo)號問題由來已久，傳統(tǒng)的研究方式往往局限于小點數(shù)圖形及某類特殊圖，通過對小點數(shù)的圖形進(jìn)行標(biāo)號，觀察其中的規(guī)律，然后拓展去驗證大點數(shù)的該類型圖，但這種方式具有局限性，且效率低下，無法完成對9個點內(nèi)的所有圖進(jìn)行標(biāo)號，因而無法發(fā)現(xiàn)優(yōu)雅標(biāo)號的普遍規(guī)律．本文通過程序設(shè)計，提出了深度遍歷搜索優(yōu)雅空間的思想，可以搜索出該圖的所有優(yōu)雅標(biāo)號．本文完成了9個點之內(nèi)所有圖的優(yōu)雅性判斷，提出了定理和猜想并給出相關(guān)數(shù)據(jù)及部分非優(yōu)雅圖，為圖標(biāo)號領(lǐng)域內(nèi)進(jìn)一步證明相關(guān)猜想提供了基礎(chǔ)數(shù)據(jù)支持．

通過對程序的結(jié)果進(jìn)行分析，對一個圖G是否優(yōu)雅做如下判斷：(1)所有的奇樹都是優(yōu)雅的；所有的偶樹中至少有一棵非優(yōu)雅樹，但大多數(shù)偶樹都是優(yōu)雅的．(2)當(dāng)p-1≤q≤2p且q≠1(mod 4)時，所有圖都是優(yōu)雅的．

研究可知，2～9個點內(nèi)圖的總數(shù)為273 192，優(yōu)雅圖為272 205，優(yōu)雅比率達(dá)到99.638 7%；針對研究中的發(fā)現(xiàn)，本文提出一個公開問題如下：當(dāng)q≥2p時，這類(p，q)圖全部是優(yōu)雅的，如(9，19)圖中31 996個圖、(9，20)圖中27 764個圖全部是優(yōu)雅的，這類圖具有怎樣的特性？該如何刻畫？