趙科，李敬文，魏眾德，王露露

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

圖的標號問題是圖論的研究方向之一，Chang等[1]在1981年提出了優(yōu)雅標號的概念。對于給定的圖G(p,q),如果存在一個單射f:V(G)→[0,1,2,q]，使邊標號集合

f(E(G))={f(uv)=(f(u)+f(v))mod(q+1)|

uv∈E(G)}=[1,q]

國內(nèi)外學(xué)者主要在研究特殊圖的優(yōu)雅性[8-10]，例如圈、路、扇等目前已經(jīng)證明是優(yōu)雅的，由于圖的總數(shù)量龐大且結(jié)構(gòu)多變，而針對一般圖的優(yōu)雅性研究較少。因此，本文結(jié)合文獻[11]給出的生成非同構(gòu)簡單連通圖的算法，設(shè)計并實現(xiàn)了一種基于一般圖的優(yōu)雅性判定算法，對16個點之內(nèi)的雙圈圖進行優(yōu)雅性研究，得出了優(yōu)雅圖與非優(yōu)雅圖的分布情況，通過對實驗數(shù)據(jù)進行分析，給出了相關(guān)結(jié)論和猜想。

1 基本概念和定義

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

(i)?v1,v2∈V,如果v1≠v2,則f(v1)≠f(v2);

(ii){f(v)|v∈V}∈{0,1,2,|E|};

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

(iv){g(e)|e∈E}∈{1,2,,|E|};

則稱f為G的一個優(yōu)雅標號(elegant labeling),G稱為優(yōu)雅圖(elegant graph)。

定義2 當(dāng)p≥4且q=p+1時，存在一類(p,q)圖，我們稱之為雙圈圖(bicyclic graphs)，記為(p,p+1)圖。

定義3 ?m,n≥3，由Cm和Cn僅共用一個頂點形成的(p,q)圖，記為C(m,n),其中p=m+n-1,q=m+n。

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

(i)Min(f(u),f(v))≥0;

(ii)Max(f(u),f(v))≤|E|;

(iii)(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的取值范圍可通過如下公式判斷取得：

if (g(e)-m≥0)n=g(e)-m;

elsen=g(e)-m+q+1;

在優(yōu)雅空間中，當(dāng)m=n時，因每個點的標號不同，故去除；為了避免重復(fù)，當(dāng)m>n時，去除該二元組(m,n)。

表1 q優(yōu)雅空間Table 1 Elegant space of q

q優(yōu)雅空間舉例：圖1是一個(9,10)優(yōu)雅雙圈圖，其對應(yīng)的優(yōu)雅空間q=10。如表2所示，加粗的二元組是雙圈圖中每個邊標號所對應(yīng)的頂點標號。

圖1 (9,10)圖優(yōu)雅標號Fig.1 The elegant labeling of graph (9,10)

邊標號g(e)相鄰頂點標號(f(u),f(v))1(0,1)(2,10)(3,9)(4,8)(5,7)2(0,2)(3,10)(4,9)(5,8)(6,7)3(0,3)(1,2)(4,10)(5,9)(6,8)4(0,4)(1,3)(5,10)(6,9)(7,8)5(0,5)(1,4)(2,3)(6,10)(7,9)6(0,6)(1,5)(2,4)(7,10)(8,9)7(0,7)(1,6)(2,5)(3,4)(8,10)8(0,8)(1,7)(2,6)(3,5)(9,10)9(0,9)(1,8)(2,7)(3,6)(4,5)10(0,10)(1,9)(2,8)(3,7)(4,6)

2 解決問題的思路及算法

2.1 解決思路

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

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

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

2.2 優(yōu)雅圖判定算法

首先利用文獻[11]中的非同構(gòu)圖生成算法，生成頂點數(shù)分別為4至16的雙圈圖文件，并以鄰接矩陣形式存儲于p_p+1.txt文件中，并計算出各頂點對應(yīng)圖的個數(shù)；用文中設(shè)計的優(yōu)雅性判定算法對每個圖進行驗證。本算法采用剪枝與預(yù)判函數(shù)相結(jié)合的方式，設(shè)計的遞歸回溯算法，基本思想及詳細步驟如下。

算法的基本思想是：對于給定的一個雙圈圖，對應(yīng)圖的鄰接矩陣為M(n,n)，其中Mii代表圖中的各個頂點，Mij=1代表頂點i與頂點j之間存在一條邊(i≠j),Mij=0代表頂點i與頂點j之間沒有邊(i≠j)。對Mii進行優(yōu)雅標號，標號過程為：1) 從(p+1)優(yōu)雅空間中從上至下，從左至右遍歷二元組(m,n)，首先生成邊標號為1的一個二元組；2) 判斷該二元組是否可用，如果可用，將(m,n)分別標在Mii與Mjj處，且Mij=(m+n)mod(q+1)；如果不可用，從左到右尋找下一個二元組，若二元組沒有，遞歸到上一層；3)邊標號遞增，重復(fù)過程1)、2)，如果生成邊標號為q的二元組，且在矩陣中標記成功，則判斷該圖是優(yōu)雅的，算法退出，如果優(yōu)雅空間已遍歷完，算法結(jié)束。算法詳細步驟：

算法：雙圈圖優(yōu)雅性判定算法

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}

Set edgeCount=1;

4.DeepSearch (edgeCount)

5.{

6.If (edgeCount=q+1)

7.Success and quit;

8.Select a two tuple(p1,p2);

9.Forp1 0→q

10. if (edgeCount-p1≥0)p2=edgeCount-p1;

11.elsep2=edgeCount-p1+q+1;

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

13.Checkp1 andp2 in Martix;

14.Fori1→n

15.if(Miican be use)Mii=p1;

16.Forj1→nandi≠j

17.if (Mjjcan be use &&Mij==1)

18.{

19.Mjj=p2;

20.Mij=edgeCount;

21.edgeCount=edgeCount+1;

22.DeepSearch(edgeCount);

23.}

24.End Forj1→nandi≠j

25.End Fori1→n

26.if (Elegant Space is Finished)

27.This Graph is UnElegant;

28.End

該算法是針對一個特定圖對應(yīng)的鄰接矩陣進行標號，如果該圖是優(yōu)雅的，則可以快速得到一個優(yōu)雅標號，具有較好的時間收斂性；如果該圖是非優(yōu)雅的，則要搜索完整個優(yōu)雅空間，此時算法具有較高的耗時。利用該算法，可以對本文中所涉及的所有的雙圈圖進行優(yōu)雅性驗證。

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

本文結(jié)合文獻[11]中的生成所有非同構(gòu)圖的算法，運用文中設(shè)計的優(yōu)雅性判定算法，對頂點數(shù)4≤p≤16的所有雙圈圖進行優(yōu)雅性驗證，統(tǒng)計了雙圈圖的優(yōu)雅個數(shù)、非優(yōu)雅個數(shù)，及特定(p,p+1)圖優(yōu)雅性驗證所運行的時間。本文列舉了部分優(yōu)雅雙圈圖的標號，標號無規(guī)律可循，用傳統(tǒng)手工方式較難標出。

算法的運行環(huán)境如下：

計算機處理器：Intel(R) Core(TM) i7-7700 CPU @ 3.60 GHz

運行內(nèi)存：64.0 GB

運行的操作系統(tǒng)：Windows 7 64位

算法開發(fā)軟件：Visio Studio 2013

開發(fā)語言：C#

3.1 16個點內(nèi)所有雙圈圖優(yōu)雅個數(shù)統(tǒng)計

雙圈圖優(yōu)雅個數(shù)統(tǒng)計如表3所示，其中第一列為(p,p+1)圖，代表頂點數(shù)和邊數(shù)確定的一類雙圈圖，第二列與第三列分別表示這一類雙圈圖的優(yōu)雅圖總數(shù)與非優(yōu)雅圖總數(shù)，第四列為這一類雙圈圖的總個數(shù)，第六列為判斷該類雙圈圖中每個圖的優(yōu)雅性所耗費的時間。

表3 16個點內(nèi)雙圈圖的優(yōu)雅性統(tǒng)計表Table 3 The statistics of the elegant of bicyclic graphs in 16 points

3.2 定理和猜想

定理1 對于(p,p+1)圖，當(dāng)4≤p≤16且p+1≠1(mod 4)時，雙圈圖(p,p+1)都是優(yōu)雅的。

證明由算法的正確性及表3可知，定理1成立。

猜想1 對于(p,p+1)圖，當(dāng)p+1≠1(mod 4)時，雙圈圖(p,p+1)都是優(yōu)雅的。

定理2 對于(p,p+1)圖，當(dāng)4≤p≤16且p+1=1(mod 4)時，雙圈圖C(m,n)是非優(yōu)雅圖。

證明由雙圈圖的定義可知，q=p+1。假設(shè)q(mod 4)≡1時，雙圈圖C(m,n)是優(yōu)雅圖。

3.3 16個點內(nèi)所有非優(yōu)雅雙圈圖

圖2給出16個點內(nèi)的所有非優(yōu)雅雙圈圖，非優(yōu)雅雙圈圖圖的命名規(guī)則如下：在C(m,n)中，m為第一個圈圖Cm的點數(shù)，n為第二個圈圖Cn的點數(shù)。

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

本文列出部分雙圈圖的優(yōu)雅標號，且這些雙圈圖的優(yōu)雅標號用手工方式較難標出，以便增加算法的真實性和實用性，圖的命名規(guī)則如下：p_q_number,其中p表示圖的頂點數(shù)，q表示圖的邊數(shù)，number表示為(p,q)圖中列舉的第幾個優(yōu)雅圖，若只有一個優(yōu)雅圖，則number予以省略。圖(12,13)、(13,14)、(14,15)部分優(yōu)雅圖如圖3所示，(15，16)、(16，117)部分優(yōu)雅圖見圖4，(17，18)、(20，21)、(24，25)、(29，30)部分優(yōu)雅圖見圖5。

圖2 16個點內(nèi)的所有非優(yōu)雅雙圈圖Fig.2 All non-elegant bicyclic graphs in 16 points

圖3 (12,13)、(13,14) 、(14,15)部分優(yōu)雅圖Fig.3 Partly elegant graphs of (12,13)、(13,14)、(14,15)

圖4 (15,16)、(16,17)部分優(yōu)雅圖Fig.4 Partly elegant graphs of (15,16)、(16,17)

圖5 (17,18)、(20,21)、(24,25)、(29,30)部分優(yōu)雅圖Fig.5 Partly elegant graphs of (17,18), (20,21),(24,25), (29,30)

4 結(jié) 語

本文給出了一種針對所有圖的優(yōu)雅性驗證算法，利用該算法對16個點內(nèi)的所有雙圈圖進行優(yōu)雅性驗證，得到其中的優(yōu)雅圖及非優(yōu)雅圖個數(shù)。結(jié)果表明，16個點內(nèi)的所有雙圈圖，除了當(dāng)(m+n)(mod 4)=1時，圖C(m,n)為非優(yōu)雅圖外，其余的雙圈圖都是優(yōu)雅的。文中第三節(jié)給出相關(guān)數(shù)據(jù)及部分非優(yōu)雅圖，為圖標號領(lǐng)域內(nèi)進一步證明相關(guān)猜想提供基礎(chǔ)數(shù)據(jù)支持。隨著點數(shù)的增加，圖集過多導(dǎo)致算法執(zhí)行效率下降，不能對16個點之后的所有雙圈圖進行一一驗證，故只在第三節(jié)列出16個點以上的部分優(yōu)雅雙圈圖。在今后對算法進一步優(yōu)化，以便取得新的突破。

通過對程序結(jié)果進行分析，對一個雙圈圖(p,p+1)是否非優(yōu)雅做如下斷言：當(dāng)p+1(mod 4)=1且雙圈圖為C(m,n)時，該雙圈圖為非優(yōu)雅圖?；谝陨蠈嶒灲Y(jié)果，提出一個公開問題。

問題：隨著點數(shù)p的增加，雙圈圖(p,p+1)是否依然滿足猜想2？