雙圈圖優(yōu)雅性猜想*

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

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

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

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)多變，而針對(duì)一般圖的優(yōu)雅性研究較少。因此，本文結(jié)合文獻(xiàn)[11]給出的生成非同構(gòu)簡(jiǎn)單連通圖的算法，設(shè)計(jì)并實(shí)現(xiàn)了一種基于一般圖的優(yōu)雅性判定算法，對(duì)16個(gè)點(diǎn)之內(nèi)的雙圈圖進(jìn)行優(yōu)雅性研究，得出了優(yōu)雅圖與非優(yōu)雅圖的分布情況，通過對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，給出了相關(guān)結(jié)論和猜想。

1 基本概念和定義

定義1 對(duì)于一個(gè)給定的簡(jiǎn)單連通圖G=(V,E)，如果對(duì)每一個(gè)頂點(diǎn)v∈V，都對(duì)應(yīng)一個(gè)非負(fù)整數(shù)f(v)(f(v)為頂點(diǎn)v的標(biāo)號(hào))，且滿足：

(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的一個(gè)優(yōu)雅標(biāo)號(hào)(elegant labeling),G稱為優(yōu)雅圖(elegant graph)。

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

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

定義4 對(duì)于邊數(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所示。對(duì)于每個(gè)g(e)，只取一個(gè)二元組(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時(shí)，因每個(gè)點(diǎn)的標(biāo)號(hào)不同，故去除；為了避免重復(fù)，當(dāng)m>n時(shí)，去除該二元組(m,n)。

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

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

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

邊標(biāo)號(hào)g(e)相鄰頂點(diǎn)標(biāo)號(hào)(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個(gè)圖都是優(yōu)雅圖，由連通圖與非連通圖組成；

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

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

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

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

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

Input: 一個(gè)圖的鄰接矩陣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

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

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

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

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

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

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

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

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

開發(fā)語言：C#

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

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

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

3.2 定理和猜想

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

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

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

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

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

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

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

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

本文列出部分雙圈圖的優(yōu)雅標(biāo)號(hào)，且這些雙圈圖的優(yōu)雅標(biāo)號(hào)用手工方式較難標(biāo)出，以便增加算法的真實(shí)性和實(shí)用性，圖的命名規(guī)則如下：p_q_number,其中p表示圖的頂點(diǎn)數(shù)，q表示圖的邊數(shù)，number表示為(p,q)圖中列舉的第幾個(gè)優(yōu)雅圖，若只有一個(gè)優(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個(gè)點(diǎn)內(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é) 語

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

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

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