魏眾德，李敬文，武永蘭

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

現(xiàn)實世界中大多數(shù)問題可以抽象為圖論問題，即事物或現(xiàn)象代表為點，事物之間以及現(xiàn)象之間的某種聯(lián)系抽象為邊，用圖表示出事物之間聯(lián)系的拓?fù)浣Y(jié)構(gòu)，進(jìn)一步轉(zhuǎn)變?yōu)閷D的研究。圖論的起源可以追溯至1736年EULER對格尼斯堡七橋問題的研究，但在隨后的近200年里發(fā)展緩慢。受近代電子計算機發(fā)展的影響，圖論在近年來得到快速發(fā)展，形成了一個重要的數(shù)學(xué)分支，并與矩陣論、群論等分支相互交叉做研究。圖論廣泛應(yīng)用于計算機科學(xué)、網(wǎng)絡(luò)、有機化學(xué)等多個領(lǐng)域，尤為熱門的機器學(xué)習(xí)、神經(jīng)網(wǎng)絡(luò)，以圖論的數(shù)學(xué)理論背景作為基礎(chǔ)，進(jìn)而研究出基于圖論的機器學(xué)習(xí)算法，并得以廣泛應(yīng)用。

圖的優(yōu)美標(biāo)號問題是圖論中最為熱門的研究之一，它的研究始于20世紀(jì)60年代Rosa[1]提出的優(yōu)美樹猜想：所有的樹都是優(yōu)美的，由于優(yōu)美標(biāo)號的組合數(shù)變化很多，在數(shù)學(xué)理論分析上造成很大困難，因此該猜想至今無人證明或否定，2010年Fang等[2]利用計算機算法證明了35個頂點內(nèi)的所有樹都是優(yōu)美的。在優(yōu)美樹猜想提出的近40年中，又有多人提出了其它相關(guān)猜想，比如：1980年Graham等[3]提出：任何樹都有和諧標(biāo)號，1991年Gnanajothi等[4]提出：每棵樹都是奇優(yōu)美的。標(biāo)號種類以及標(biāo)號理論分析的多樣性使得研究者查閱文獻(xiàn)較為困難，而在文獻(xiàn)[5]中，則詳細(xì)列出了近60年內(nèi)所有標(biāo)號的研究現(xiàn)狀。優(yōu)美圖的概念由Rosa[1]首次提出，隨后Golomb[6]對優(yōu)美圖給出了明確的定義。由于優(yōu)美圖在軍事方面比如：雷達(dá)脈沖碼，通信網(wǎng)絡(luò)等方面的廣泛應(yīng)用，所以更加引起學(xué)者們的重視，并且其理論研究具有重要價值。

國內(nèi)外學(xué)者對優(yōu)美圖的研究，目前主要集中在樹、與圈相關(guān)的圖、部分特殊圖、并圖和一些非連通圖等方面[7-10]，例如毛毛蟲、花樹等特殊樹目前已經(jīng)證明是優(yōu)美的。而對于一般圖的優(yōu)美性及非優(yōu)美性研究很少，Erd?s[3]在未正式發(fā)表的一篇論文中闡述了多數(shù)圖并不是優(yōu)美的，但未得到證明。Rosa認(rèn)為一個圖G是非優(yōu)美的主要有3個原因[1]：① 圖G有太多的頂點且沒有足夠的邊；②G有太多的邊而沒有足夠的頂點，③G的邊數(shù)具有錯誤的奇偶性。因此，本論文結(jié)合文獻(xiàn)[11]給出的生成非同構(gòu)圖的算法源代碼，以及結(jié)合目前已實現(xiàn)的優(yōu)美標(biāo)號算法，給出了9個點內(nèi)的所有優(yōu)美圖及非優(yōu)美圖的數(shù)量，并對數(shù)據(jù)進(jìn)行分析，得出該范圍內(nèi)的所有圖，非優(yōu)美圖占比很小，且非優(yōu)美圖的分布很有規(guī)律，大致滿足Rosa提出的3個基本原因；對應(yīng)的，優(yōu)美圖的分布也呈現(xiàn)出很有趣的現(xiàn)象，下節(jié)給出具體定理和相關(guān)猜想。

文中所用的[m,n]為集合{m,m+1,m+2, …,n}，即從m到n的自然數(shù)。為方便起見，

以下給出優(yōu)美標(biāo)號和優(yōu)美圖的定義。

定義1[6]如果一個(p,q)圖G(p個頂點，q條邊)存在一個映射f:V(G)→[0,q],使得圖G中任意兩個頂點x、y滿足f(x)≠f(y),并且定義邊uv∈V(G)的標(biāo)號為f(uv)=|f(u)-f(v)|。當(dāng){f(uv):uv∈E(G)}=[1,q]時，則稱f為圖G的一個優(yōu)美標(biāo)號(garceful labeling)，圖G稱為優(yōu)美圖(graceful grpah)。

算法是基于搜索優(yōu)美空間的，進(jìn)而找出圖的優(yōu)美標(biāo)號。為了詳細(xì)說明算法的執(zhí)行過程，以下給出優(yōu)美空間的明確定義。

定義2 對于邊數(shù)為q的一類優(yōu)美圖，都存在一個表(如表1)，并且滿足：

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

(ii) Max(f(u),f(v))≤edgeLabel；

(iii) |f(u)-f(v)|=edgeLabel。

則稱此表為邊數(shù)為q的優(yōu)美集合，又稱q優(yōu)美空間。

表1 q優(yōu)美空間Table 1 q graceful space

由此可知，對于每個邊標(biāo)號(edgeLabel)，對應(yīng)的取唯一一個二元組(由該邊的兩個相鄰頂點標(biāo)號組成)，而這些二元組集合組成的圖都是優(yōu)美的。

例1 如表2為q=9的優(yōu)美空間，取出的二元組對應(yīng)優(yōu)美圖如圖1所示。

圖1 G(5,9)優(yōu)美標(biāo)號Fig.1 A graceful labeling of G(5,9)

表2 q=9優(yōu)美空間Table 2 Graceful space with q=9

文中是對9個點內(nèi)的所有圖進(jìn)行了優(yōu)美性驗證，其中包含了樹、單圈圖、雙圈圖以及其它圖，而樹和單圈圖已經(jīng)提出相關(guān)猜想，以下列出：

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

猜想2[12]除了圈Cn,n(mod 4)={1,2}是非優(yōu)美圖之外，其它所有的單圈圖都是優(yōu)美的。

1 定理和猜想

本文所討論的圖均為簡單連通圖，若為非連通圖則另加說明。對于一類(p,q)圖，判斷其中每個圖是否優(yōu)美的解決思路如下：①q優(yōu)美空間可以組合出q!個圖；②q!個圖中包含非連通圖和連通圖，但都是優(yōu)美的；③ 所有(p,q)圖中的優(yōu)美圖都包含在q!個圖中，即q優(yōu)美空間具有完備性；④ 如果一個(p,q)圖不包含在q!個圖中，則它是非優(yōu)美的?；谝陨?個思路設(shè)計的優(yōu)美圖判定算法，可知，算法具有正確性，第二節(jié)將給出算法詳細(xì)步驟。根據(jù)算法實驗結(jié)果，給出如下定理和猜想。

一類(p,q)圖，在邊密度過大的情況下，會導(dǎo)致這一類(p,q)圖中的所有圖全部非優(yōu)美。以下給出定理1，在9個點范圍內(nèi)，(p,q)圖由完全圖再減去m條邊(Kn-m)，這類(p,q)圖仍然是非優(yōu)美的。

由定理1，可得如下猜測，對于(p,q)圖，當(dāng)點數(shù)大于9時，邊數(shù)在一定范圍內(nèi)，這類(p,q)圖都是非優(yōu)美的。

猜想3 當(dāng)

時，圖(p,q)是非優(yōu)美的,其中m=0, 1, … ,p-3。

算法搜索結(jié)果得知，在9個點范圍內(nèi)，部分(p,q)圖中的所有圖全部是優(yōu)美的。

在9個點范圍內(nèi)，并且邊密度不大的情況下，(p,q)圖呈現(xiàn)出一定的規(guī)律性：當(dāng)q(mod 4)={0,3}時，這類(p,q)圖中的非優(yōu)美圖占總圖的比例很小，可以認(rèn)為絕大多數(shù)圖都是優(yōu)美的，根據(jù)實驗結(jié)果，對“邊密度不大”量化為q≤[3.7p-9.3]，因此可得定理3。

定理3 當(dāng)5≤p≤9，q≤[3.7p-9.3]，且q(mod 4)={0,3}時，幾乎所有的(p,q)圖是優(yōu)美的。

證明由表3-表7可知，在邊密度不大的條件下，邊數(shù)q呈現(xiàn)出一定的規(guī)律性，即q(mod 4)={0,3}時，(p,q)圖中幾乎所有的圖都是優(yōu)美的，根據(jù)表中數(shù)據(jù)對此條件進(jìn)行量化，取出散點(x,y),其中當(dāng)p=x,q≤y時，(p,q)圖滿足此規(guī)律，由表3-表7可分別取出散點(5,9)、(6,13)、 (7,17)、(8,20)、(9,24),如圖2所示。

圖2 9個點內(nèi)“邊密度不大”上界Fig.2 The upper boundary of “small side density” in the 9 points

對數(shù)據(jù)進(jìn)行線性擬合，可得y=3.7x-9.3，由于邊數(shù)為整數(shù)，故定義y=[3.7p-9.3]。因此，q≤[3.7p-9.3]，定理3成立。

由定理3，可以進(jìn)行如下猜測，當(dāng)點數(shù)大于9時，該規(guī)律依然滿足。

猜想4 當(dāng)p>9,q≤[3.7p-9.3], 且q(mod 4)={0,3}時，幾乎所有的圖(p,q)是優(yōu)美的。

由于9個點內(nèi)“邊密度不大”的上界是根據(jù)實驗數(shù)據(jù)結(jié)果限定的，本質(zhì)上是一個模糊界限，但是可以對圖論中相關(guān)標(biāo)號領(lǐng)域的研究給予數(shù)據(jù)支持。

2 優(yōu)美圖判定算法

首先利用文獻(xiàn)[11]中的生成非同構(gòu)圖算法，生成9個點內(nèi)的所有非同構(gòu)圖，并且按不同的點與邊進(jìn)行區(qū)分，以鄰接矩陣形式分別存儲于文件p_q.txt中。

本算法包含2個子算法，分別為：基于優(yōu)美空間搜索判定算法和基于鄰接矩陣優(yōu)美判定算法。算法1的基本思想是：首先對文件p_q.txt做預(yù)處理，其中p為圖的頂點數(shù)，q為對應(yīng)邊數(shù)，預(yù)處理包括4部分：(i)計算文件中圖的總個數(shù)；(ii)求每個圖對應(yīng)的度序列；(iii)求每個圖對應(yīng)的特征值；(iv)對每個圖設(shè)一個標(biāo)志，用于標(biāo)識該圖是否已經(jīng)優(yōu)美；然后搜索優(yōu)美空間，搜索出的圖與源文件中的圖進(jìn)行對比，如果為文件中第i個圖，則將圖Gi標(biāo)為優(yōu)美。

算法1 基于優(yōu)美空間搜索判定算法

輸入: (p,q)圖的鄰接矩陣文件p_q.txt

輸出: 文件中所有非優(yōu)美圖

1.begin

2.讀鄰接矩陣文件p_q.txt

3.fori1→nn是文件中所有圖的總個數(shù)

4.ComputeDegreeSeq(Graphi)

5.ComputeEigenvalue(Graphi)

6.IsGraphiGrace=false

7.end for

8.search graceful space

9.二元組集合→鄰接矩陣TempMatrix

10.ComputeDegreeSeq(TempMatrix)

11.ComputeEigenvalue(TempMatrix)

12.fori1→n

13.if(IsDegreeSeqSame(Graphi,TempGraph)&&IsEvalueSame(Graphi,TempGraph)

14.IsGraphiGrace=true;

15.break;

16.end for

17.if(eachGraph is graceful)

18.break;

19.end search

20.fori1→n

21.if(IsGraphiGrace==false)

22.output(Graphi);

23.return

24.end

考慮到優(yōu)美空間龐大以及搜索整個優(yōu)美空間的時間復(fù)雜度較高，當(dāng)文件中所有圖都已經(jīng)標(biāo)為優(yōu)美時，或者該文件中大部分圖都已標(biāo)為優(yōu)美，只有少量暫時未標(biāo)為優(yōu)美的圖時，算法1可以結(jié)束，用算法2解決剩余圖。算法2的基本思想是：對于給定的圖，對應(yīng)圖的鄰接矩陣為Mn，其中Mij=1代表頂點i與頂點j之間有邊(i≠j)，對Mii進(jìn)行優(yōu)美標(biāo)號，Mii即代表該圖中的各個點，標(biāo)號過程為：首先從優(yōu)美空間中選出邊標(biāo)號為q的1個二元組，然后將二元組(m,n)中的2個值分別標(biāo)于鄰接矩陣的主對角線上，即Mii=m，Mjj=n，并且需要滿足條件Mij=1，然后選出邊標(biāo)號為q-1的1個二元組(m′,n′)，標(biāo)于鄰接矩陣主對角線上，邊標(biāo)號遞減，如果當(dāng)前邊標(biāo)號無法在鄰接矩陣中標(biāo)成功，則回退至上一級，重新開始標(biāo)號；如果邊為1的1個二元組已經(jīng)標(biāo)成功，則說明該圖是優(yōu)美的，算法結(jié)束。如果整個優(yōu)美空間已經(jīng)搜索完畢，仍未找到該圖的優(yōu)美標(biāo)號，則確定該圖是非優(yōu)美的。算法2的具體步驟如下：

算法2: 基于鄰接矩陣優(yōu)美判定算法

輸入: 一個鄰接矩陣Mn

輸出: 該鄰接矩陣對應(yīng)圖是否優(yōu)美

1.begin

2.search graceful space(edgeLabel)edgeLabel∈{0,1,2,…,q}

初始化edgeLabel=q

3.if(edgeLabel==0)

4.this graph is graceful;

5.return;

6.select a two tuple(m,n)

m∈{0, 1, …, edgeLabel-m},

n∈{edgeLabel, edgeLabel+1, …,q}, |n-m|=edgeLabel.

7.If (tuple(m,n) is not enabled)

8.ReSelect tuple;

9.fori1→n

10.If (Miiis enabled)

11.Mii=m;

12.forji→n

13.If (Mjjis enabled&&Mij==1)

14.Mjj=n;Mij=edgelabel;

15.end forji→n

16.end fori1→n

17.If (conflict-free)

18.search graceful space(edgeLabel-1)

19.end search

20.if (grace space search finished)

21.This graph is ungraceful

22.end

由于算法2針對一個特定圖，相比算法1的盲目搜索而言，算法2具有更好的收斂性，且往往是計算機驗證非優(yōu)美圖的有力工具。

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

本文利用上述優(yōu)美性判定算法，結(jié)合文獻(xiàn)[11]中給出的生成非同構(gòu)圖算法，對9個點內(nèi)的所有圖進(jìn)行了優(yōu)美性驗證，以下分別列出對9個點內(nèi)的所有圖的優(yōu)美個數(shù)統(tǒng)計表，以及各個點之間圖的優(yōu)美及非優(yōu)美數(shù)對比表，由于篇幅有限，本文只給出部分非優(yōu)美圖和優(yōu)美圖。

算法運行環(huán)境及硬件配置如下：

操作系統(tǒng)：Windows 764位

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

RAM: 64.0 GB

開發(fā)環(huán)境：Visio Studio 2013

開發(fā)語言：C#

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

程序運行結(jié)果表明，當(dāng)點數(shù)為2,3,4時，對應(yīng)的所有圖是優(yōu)美的，圖的總個數(shù)分別為1,2,6。以下列出當(dāng)點數(shù)為5-9時所有圖的優(yōu)美數(shù)及非優(yōu)美數(shù)，如表3-表7。第1列為(p,q)，p為圖的點數(shù)，q為圖的邊數(shù)，可知，當(dāng)點數(shù)為p時，q范圍為[p-1,p(p-1)/2]；當(dāng)q=p-1時，此時圖全部為樹，當(dāng)q=p(p-1)/2時，此時圖為完全圖；第4列為當(dāng)點數(shù)為p，邊數(shù)為q的情況下圖的總個數(shù)；第2列與第3列分別為當(dāng)前圖集中優(yōu)美圖個數(shù)與非優(yōu)美個數(shù)。

表3 點數(shù)為5Table 3 The number of vertices is 5

表4 點數(shù)為6 Table 4 The number of vertices is 6

表5 點數(shù)為7Table 5 The number of vertices is 7

表6 點數(shù)為8Table 6 The number of vertices is 8

表7 點數(shù)為9Table 7 The number of vertices is 9

由表3-表7可以看出，(5,10)，(6,14-15)，(7,18-21)，(8,24-28)，(9,30-36)中的所有圖都是非優(yōu)美的，符合Rosa提出導(dǎo)致一個圖非優(yōu)美的基本原因中的第2條，由此可得定理1，并提出猜想3；由表6和表7可知，在邊數(shù)不過大的情況下，當(dāng)q(mod 4)=1,2時，其非優(yōu)美圖個數(shù)占當(dāng)前圖總數(shù)的比例大幅增加，而當(dāng)q(mod 4)=0,3時，其非優(yōu)美圖個數(shù)占比又相對很小，符合Rosa提出導(dǎo)致一個圖非優(yōu)美的基本原因中的第3條，即G的邊數(shù)具有錯誤的奇偶性，由此可得定理2、定理3，并提出猜想4。盡管非優(yōu)美圖較多，但相比圖的總數(shù)而言，非優(yōu)美圖的數(shù)量還是很少的，如表8所示，列出了2-9個點內(nèi)所有圖的優(yōu)美數(shù)量和非優(yōu)美數(shù)量以及非優(yōu)美占比。

由表8可知，當(dāng)p≥5時，有非優(yōu)美圖出現(xiàn)，但是非優(yōu)美圖數(shù)量占圖總數(shù)的比例很小，而且比率呈現(xiàn)減小趨勢，因此可以得出，9個點內(nèi)大部分圖都是優(yōu)美的。

3.2 9個點內(nèi)部分非優(yōu)美圖

以下給出9個點內(nèi)的部分非優(yōu)美圖，非優(yōu)美圖的命名規(guī)則如下：G(p,q,num)，其中p為點數(shù)，q為邊數(shù)，num表示當(dāng)前(p,q)圖下的第幾個非優(yōu)美圖，如果(p,q)圖中的非優(yōu)美圖只列出1個，則該圖直接命名為G(p,q)。

點數(shù)為5的非優(yōu)美圖已經(jīng)由文獻(xiàn)給出，一共有3個，如圖3所示。

點數(shù)為6的非優(yōu)美圖一共有6個，如圖4所示，其中(1)為圈C6，文獻(xiàn)[1]已經(jīng)給出對于圈圖的優(yōu)美性證明，(6)為完全圖K6，文獻(xiàn)[6]已經(jīng)證明了當(dāng)n≥5時，Kn是非優(yōu)美的。

點數(shù)為7的部分非優(yōu)美圖如圖5所示，其中(3)為荷蘭風(fēng)車，文獻(xiàn)[13-14]中已經(jīng)得出相關(guān)結(jié)論。

表8 2-9個點內(nèi)所有圖的優(yōu)美個數(shù)對比Table 8 A comparison of the number of graceful numbers of all graphs in 2-9 points

圖3 p=5的非優(yōu)美圖Fig.3 Ungraceful graphs with p=5

圖4 p=6的非優(yōu)美圖Fig.4 Ungraceful graphs with p=6

點數(shù)為8的部分非優(yōu)美圖如圖6所示。

點數(shù)為9的部分非優(yōu)美圖如圖7所示。其中(2)、(3)、(4)是有兩個圈共用一個頂點形成，(8)為兩個K5共用一個頂點形成。

由以上部分示例可以得出，大部分非優(yōu)美圖呈現(xiàn)出很強的對稱性，且很多以并圖的方式出現(xiàn)，并且其中有些圖已經(jīng)被數(shù)學(xué)證明是非優(yōu)美的。

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

為了說明算法的正確性和真實性，以下列出9個點內(nèi)部分優(yōu)美圖，而這些優(yōu)美圖的標(biāo)號多數(shù)情況下手工方式較難給出，以(8,13)，(9,14)部分優(yōu)美圖為例。

(8,13)部分優(yōu)美圖如圖8所示。

(9,14)部分優(yōu)美圖如圖9所示。

圖6 p=8的部分非優(yōu)美圖Fig.6 Partial ungraceful graphs with p=8

圖7 p=9的部分非優(yōu)美圖Fig.7 Partial ungraceful graphs with p=9

圖8 (8,13)部分優(yōu)美圖Fig.8 Partial graceful graphs of (8,13)

圖9 (9,14)部分優(yōu)美圖Fig.9 Partial graceful graphs of (9,14)

隨著點數(shù)增大以及邊數(shù)增多，對應(yīng)的優(yōu)美空間也就越大，且圖的總數(shù)量呈現(xiàn)出指數(shù)級增長，這導(dǎo)致存儲空間過大以及算法執(zhí)行效率下降。因此，本文只驗證了9個點內(nèi)所有圖的優(yōu)美性。

4 結(jié) 語

本文給出一種針對一般圖的優(yōu)美性驗證算法，并引入預(yù)判函數(shù)對算法進(jìn)行優(yōu)化，該算法可以得出任意圖的優(yōu)美標(biāo)號，或者確定該圖非優(yōu)美。然后利用該算法對9個點內(nèi)的所有圖進(jìn)行優(yōu)美性分析，最終得出該范圍內(nèi)所有的非優(yōu)美圖。結(jié)果表明，雖然非優(yōu)美圖數(shù)量較多，但相比總數(shù)而言，非優(yōu)美圖數(shù)量占比極小，而且呈現(xiàn)出很強的對稱性，可以認(rèn)為，在有限點內(nèi)，絕大多數(shù)圖是優(yōu)美的。文中第四節(jié)給出相關(guān)數(shù)據(jù)及部分非優(yōu)美圖和優(yōu)美圖，對數(shù)據(jù)進(jìn)行分析，得到了3個定理，并提出相關(guān)猜想，且所得到的數(shù)據(jù)可以為圖標(biāo)號領(lǐng)域內(nèi)進(jìn)一步證明相關(guān)猜想提供基礎(chǔ)數(shù)據(jù)支持。

由表8可知，9個點內(nèi)的所有圖的總數(shù)為273 192，優(yōu)美圖總數(shù)為271 535，優(yōu)美比率達(dá)到99.393 5%；另由定理2可知，部分點、邊數(shù)確定的(p,q)圖是全部優(yōu)美的，因此，本文提出兩個公開問題，如下：

問題1 Erd?s提出大部分圖是非優(yōu)美的，但未得到明確的證明。本文實驗得出9個點內(nèi)大部分圖是優(yōu)美的，優(yōu)美比率達(dá)到99.393 5%，且非優(yōu)美比率呈遞減趨勢。那么隨著點數(shù)的增加，非優(yōu)美的比率會怎樣變化？

問題2 當(dāng)p、q滿足一定的條件時，這類(p,q)圖全部是優(yōu)美的或者是非優(yōu)美的，比如：(9,19)圖中31 996個圖全部是優(yōu)美的，(8,24)中11個圖全部是非優(yōu)美的，這類圖具有怎樣的特性？該如何刻畫？