圖(n≤9)的優(yōu)美性*

魏眾德，李敬文，武永蘭

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

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

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

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

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

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

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

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

定義2 對(duì)于邊數(shù)為q的一類優(yōu)美圖，都存在一個(gè)表(如表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

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

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

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

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

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

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

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

1 定理和猜想

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

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

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

猜想3 當(dāng)

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

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

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

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

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

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

對(duì)數(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)行如下猜測(cè)，當(dāng)點(diǎn)數(shù)大于9時(shí)，該規(guī)律依然滿足。

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

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

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

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

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

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

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

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

1.begin

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

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

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

輸入: 一個(gè)鄰接矩陣Mn

輸出: 該鄰接矩陣對(duì)應(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針對(duì)一個(gè)特定圖，相比算法1的盲目搜索而言，算法2具有更好的收斂性，且往往是計(jì)算機(jī)驗(yàn)證非優(yōu)美圖的有力工具。

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

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

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

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

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

RAM: 64.0 GB

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

開(kāi)發(fā)語(yǔ)言：C#

3.1 點(diǎn)數(shù)為2-9的所有圖優(yōu)美個(gè)數(shù)統(tǒng)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

表8 2-9個(gè)點(diǎn)內(nèi)所有圖的優(yōu)美個(gè)數(shù)對(duì)比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

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

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

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

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

為了說(shuō)明算法的正確性和真實(shí)性，以下列出9個(gè)點(diǎn)內(nèi)部分優(yōu)美圖，而這些優(yōu)美圖的標(biāo)號(hà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)

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

4 結(jié) 語(yǔ)

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

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

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

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