多目標優化的圖的鄰點可區別均勻V-全染色算法

曹道通, 李敬文，江紅豆, 文 飛

(1.蘭州交通大學 電子與信息工程學院，蘭州 730070； 2.蘭州交通大學 應用數學研究所，蘭州 730070)

(*通信作者電子郵箱caodaotong1990@163.com)

多目標優化的圖的鄰點可區別均勻V-全染色算法

曹道通1*, 李敬文1，江紅豆1, 文 飛2

(1.蘭州交通大學 電子與信息工程學院，蘭州 730070； 2.蘭州交通大學 應用數學研究所，蘭州 730070)

(*通信作者電子郵箱caodaotong1990@163.com)

圖的鄰點可區別均勻V-全染色(AVDEVTC)是指在滿足鄰點可區別V-全染色的基礎上，還要保證每種顏色的使用次數相差不超過1，把完成AVDEVTC所用的最少顏色稱為圖的鄰點可區別均勻V-全色數(AVDEVTCN)。針對圖的AVDEVTC問題，提出了一種基于多目標優化的染色算法。設計了一個總目標函數和四個子目標函數，在染色矩陣上通過每個點的顏色集合的迭代交換操作，使得每個子目標函數都達到最優，進而滿足總目標函數的要求，完成染色。經過理論分析和實驗對比表明，8個頂點以內的所有簡單連通圖都存在AVDEVTC，且圖的AVDEVTCN介于最大度加1與最大度加2之間。實驗結果表明，該染色算法能夠在較短的時間內正確地計算出1 000個頂點以內的圖的AVDEVTCN。

染色算法；目標函數；多目標優化；鄰點可區別均勻V-全染色；鄰點可區別均勻V-全色數

0 引言

圖染色是圖論中具有重要實際價值和理論意義的課題之一，起源于著名的“四色猜想”，計算機通信、交通定向、物品存儲、組合優化等現實生活中的很多問題都可以用圖染色的方法來解決，具有很好的應用價值，而均勻染色特別地被用來解決一些如任務調度、分區和負載平衡等有均勻要求的問題。近現代以來，一些數學工作者著力研究了圖的染色問題, 文獻[1-5]在點可區別邊染色的基礎上提出了鄰點可區別全染色、點可區別全染色、距離為β的點可區別全染色、鄰點可區別均勻全染色、鄰點可區別均勻V-全染色(AdjacentVertex-DistinguishingEquitableV-TotalColoring,AVDEVTC)等一系列的概念與猜想，同時還有其他相關概念和研究成果[6-16]。圖的染色問題一般都是NP問題，常見的智能算法如遺傳算法、蟻群算法、神經網絡等應用于解決圖的染色問題時，一般僅限于解決單一約束條件的圖染色問題，而面對如鄰點可區別均勻V-全染色[4-5]這樣的多約束條件的圖染色問題時，普通智能算法就表現出了很大的局限性。目前筆者還未在公開發表的文章中找到利用計算機算法來解決圖的鄰點可區別均勻V-全染色問題的介紹，因此在以往的研究基礎上，提出一種改進的基于多目標優化的染色算法來解決新的問題：即圖G的鄰點可區別均勻V-全染色問題。算法設計了一個總目標函數和四個子目標函數來對應AVDEVTC的多個約束條件，在染色矩陣上通過每個點的顏色集合的迭代交換操作，使得每個子目標函數都達到最優，進而滿足總目標函數的要求。通過大量的實驗和分析表明，該算法有著很高的計算效率且能夠正確地得到鄰點可區別均勻V-全色數(AdjacentVertex-DistinguishingEquitableV-TotalChromaticNumber,AVDEVTCN)[4-5]和染色后的圖的鄰接矩陣。最后還給出了大量的測試結果，為以后的圖的染色相關定理或猜想的證明提供了基礎研究數據。

定義1[5]設G(V,E)是階數不小于2的簡單連通圖G，k為正整數，f是從V(G)∪E(G)到C={1,2,…,k}的映射，如果f滿足如下條件：

1)?uv∈E(G),u≠v，f(u)≠f(uv),f(v)≠f(uv)；

2)?uv,uw∈E(G)，v≠w，有f(uv)≠f(uw)；

3)?uv∈E(G)，C(u)≠C(v)；

則稱f是圖G的k-鄰點可區別V-全染色，簡記為k-AVDVTC，并將χvt(G)=min{k|k-AVDVTC ofG}稱為圖G的鄰點可區別V-全色數,其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}。

猜想1 對于簡單圖G，Δ+1≤χavdevtc(G)≤Δ+2。

1 圖的鄰點可區別均勻V-全染色算法

1.1 算法描述

本文算法的基本思想是：先給頂點隨機地染色，任意兩點所染顏色可以相同；頂點染色完成以后，剔除頂點已經使用的顏色，用剩下的顏色再給頂點相關聯的邊隨機染色，并利用目標函數判斷染色結果是否正確，若不滿足，按照算法的規則逐步調整存在沖突的染色結果。算法統計了迭代次數并檢驗了染色結果，經過有限次的顏色調整和交換，最終的染色結果能滿足目標函數的要求。具體描述如下：

算法 鄰點可區別均勻V-全染色算法。

輸入 圖G的鄰接矩陣；

輸出 圖G的AVDEVTC矩陣。

1)給頂點隨機染色。

2)剔除頂點染色已經用過的顏色，用剩下的顏色給頂點相關聯的邊隨機染色，顯然點和相關聯的邊所染顏色是不同的，即f2(x2)。

3)解決邊染色沖突。根據每個頂點的色補集合數量的大小生成排序集arrsort[],依次從arrsort[]中取出一個頂點vi與其后的所有頂點vj，一一比較兩個頂點的色集合，若滿足以下要求：

a)兩點之間有邊，即color[vi][vj]≠0,vi≠vj;

b)vi與vj的色補集合有交集，即C(vi)∩C(vj)≠?；

計算f3(x3)是否為0，如果不為0，重復步驟4),再次生成排序集，解決色集合沖突，直到f3(x3)=0。

a)兩點之間有邊；

b)兩點之間的顏色為使用最多的顏色maxcol；

c)兩點的色補集合有交集，且交集中的元素含有使用次數最少的顏色mincol；

則將滿足條件的兩點之間的邊顏色maxcol替換為mincol，并修改色補集合。重復步驟6),直至f4(x4)=0。

7)計算總目標函數F(X)若等于0，則圖G的AVDEVTC成功，輸出結果集，否則重復上述染色步驟。

利用圖的鄰點可區別均勻V-全染色算法能夠實現隨機圖的AVDEVTC。

1.2 構建多目標優化模型

多目標優化算法流程如圖1所示。

圖1 多目標優化算法流程

根據圖G的AVDEVTC的定義，該算法必須滿足如下幾個子目標：①相鄰邊染不同色；②頂點與其關聯邊染不同色； ③相鄰頂點的色集合不同；④任意兩種顏色的使用次數相差不超過1。由以上4個條件可以構造出算法的多目標函數：

F(X)=f1(x1)+f2(x2)+f3(x3)+f4(x4)

決策向量為:

X=(X1,X2,X3,X4)。

決策變量X1、X2、X3、X4如下：

1)根據條件①，圖G一共包含m條邊(e1,e2,…,em)，因此決策變量X1=(e1,e2,…,em)。

2)根據條件②，圖G一共包含n個頂點(v1,v2,…,vn)，因此決策變量X2=(v1,v2,…,vn)。

3)根據條件③，圖G共有n個頂點，色補集合(C1,C2,…,Cn),因此決策變量X3=(C1,C2,…,Cn)。

4)根據條件④，完成染色所需的顏色分別為(1,2,…,k)，因此決策變量X4=(1,2,…,k)。

決策變量上下界分別為：u=(m,n,n,k)，l=(1,1,1,1)。

下面構建目標函數：

1)邊染色目標函數。

對任意相鄰的兩條邊e1,e2∈E(G)，令：

2)點邊目標函數。

對任意邊uv∈E(G)，令：

3)色集合目標函數。

對于相鄰的兩點u,v∈V(G)，有C(u)≠C(v)。色集合約束函數定義如下：

4)均勻目標函數。

均勻目標函數的約束條件是任意兩個顏色的使用次數相差小于或等于1。設f為E(G)到色集合C={1,2，…，k}的映射；Ti表示圖G的染色中i色使用次數，Ti={f(uv)|f(uv)=i,uv∈E(G)}；Tj表示圖G的染色中j色的使用次數，Tj={f(uv)|f(uv)=j,uv∈E(G)}。所以均勻目標函數定義如下：對任意兩點構成的邊uv∈E(G)，令

5)總目標函數。

Qavdevtc=minF(X)

其中F(X)=f1(x1)+f2(x2)+f3(x3)+f4(x4)。F(X)代表所染顏色不滿足AVDEVTC四個條件的總數量，當且僅當F(X)=0時總目標得到最優解，即染色成功。

2 染色實例

本文選取了一個8個頂點的隨機圖來進行測試。

2.1 初始化隨機圖G

生成8個頂點的隨機圖的鄰接矩陣，如表1所示，其中d(vi)表示頂點i的度。

表1 初始圖的鄰接矩陣

統計各個頂點的度，并確定初始色數k，由于圖中最大度為Δ=7, 而7度頂點的個數為1，則全染色所需顏色數k=Δ+1=7+1=8。各個頂點的度為7、5、4、3的個數分別為1、2、2、3。

2.2 頂點染色

首先按規則給頂點染色，從1～8中隨機地選擇顏色為各個頂點進行染色，頂點的顏色可以相同。

2.3 邊預染色

在點染色完成后對邊隨機地預染色，剔除頂點染色用的顏色，用剩下的顏色給頂點相關聯的邊染色。初始染色矩陣如表2所示。

表2 初始染色矩陣

2.4 查找沖突集

2.5 調整染色沖突

經過本輪變換，conflict[0][0](沖突集個數)=0，經檢測，點和邊、邊和邊、相鄰頂點的色集合的染色沖突已經解決。染色結果如表4所示。

表3 沖突集查找

表4 鄰點可區別非均勻V-全染色結果

2.6 檢驗色數是否均勻

檢驗顏色使用情況是否均勻，顏色為6、7、1、2、3、4、5、8的使用次數分別為4、4、3、3、3、3、3、2。可以看出，顏色使用不均勻，則按照算法規則繼續調整。顏色6使用了4次，顏色8使用了2次，因此嘗試將一個邊的顏色由6改為8。按照算法，找到了邊v7v6的顏色為6，將其顏色調整為8，即f(v7v6):6→8。

再次檢驗各個顏色的使用情況，顏色7、6、1、2、3、4、5、8的使用次數分別為4、3、3、3、3、3、3、3。可以看出，各個顏色的使用次數相差不超過1，即f4(x4)=0；再次檢驗染色結果是否滿足AVDEVTC的所有條件，經檢驗：F(X)=f1(x1)+f2(x2)+f3(x3)+f4(x4)=0+0+0+0=0，由此可得AVDEVTC成功。最終的染色結果如表5所示。

表5 鄰點可區別均勻V-全染色最終結果

3 實驗結果數據集

利用該算法得到了大量的實驗結果，一方面用來驗證相關猜想的成立，另一方面也為相關的研究提供基礎數據支持。測試結果主要包括以下5部分：

1)在1 000個點以內，測試了110萬個圖，其色數為Δ、Δ+1、Δ+2、Δ+3的圖的數量如表6所示。

表6 1 000點以內的110萬個圖的測試結果

2)對3≤n≤8內的所有圖進行了測試，如表7所示，其中：3至7個頂點內的所有圖為經過多方面人工校對過的非同構圖最新數量，頂點8的圖為包括同構圖在內的由圖生成算法生成的所有簡單連通圖數量。

表7 3～8個頂點的若干個圖的染色結果

3)鑒于篇幅限制，只從5～8個點選擇了20個圖測試了度序列與色數和邊數。在表8中，每一行代表一個圖，“度序列”下的數字指的是該圖中的頂點度分布，“均勻染色”下的數字指的是該色數的使用次數。

表8 度序列、色數測試結果

4)從20到400個點之間測試了100萬個圖，由于篇幅限制，僅列舉了72個圖的染色結果，色數和邊密度的變化曲線如圖2所示。

圖2 色數-邊密度變化曲線

從圖2可以看出，色數隨著邊密度和點數的增大而增大。

通過對表6～8的結果分析，可得到如下結論：

結論 1 8個頂點以內的所有簡單連通圖都存在AVDEVTC。

結論2 對于簡單圖G，當3≤n≤8時，Δ+1≤χavdevtc(G)≤Δ+2。

結論3 結合圖2、表6～8的測試結果，猜想1成立。

5)運行時間計算。使用此算法對500～1 000個頂點的隨機圖進行了測試，由于篇幅所限，僅列舉了邊密度為0.1時運行部分單個圖的運行時間(由于最終的染色矩陣要寫進txt文件，所以程序運行時間略有延長)，點數為500、600、700、800、900、1 000的時間分別為16.225s、19.382s、121.025s、135.116s、320.026s、420.359s。同時測試了7個頂點以內的所有非同構圖以及8個頂點的所有圖，運行時間如表9所示。可以得出，該算法能夠在較短的時間內得到染色結果。

表9 8個頂點以內所有圖的運算時間 s

4 算法時間復雜度分析

依據算法步驟，影響算法時間復雜度的因素主要包括以下幾點(n代表圖G的點數)：

1)生成隨機圖。算法用m與n的矩陣存儲隨機圖，所以該步最壞的時間復雜度是：T1(n)=O(n2)。

2) 給頂點染色。依據染色規則，每個頂點僅染色一次，因此點染色的時間復雜度是：T2(n)=O(n)。

3)邊的預染色。此步驟的時間復雜度取決于邊的個數，在最壞的情況下，邊的個數為n階完全圖的個數，所以這一步最壞的時間復雜度是：T3(n)=O(n2)。

4)解決邊染色沖突。依據arrsort[]數組中頂點的順序逐步迭代交換，使得圖中所有邊的染色均達到正常，這一步最壞的時間復雜度為：T4(n)=O(n3)。

5)調整色集合沖突。通過調用preexchange()函數得到最佳的處理色集合沖突的交換方式，這一步最壞的時間復雜度為：T5(n)=O(n3)。

6)解決均勻染色問題，對于n個頂點的隨機圖G，令調整的最大次數為max，一般情況下max不超過n，則最壞復雜度為T6(n)=O(max×n2)。

綜合上述分析，本算法的時間復雜度為O(n3)。

5 結語

本文提出了一種啟發式優化算法來解決新問題：即圖的鄰點可區別均勻V-全染色問題。算法設計了一個總目標函數和四個子目標函數來對應AVDEVTC的多個約束條件，在染色矩陣上通過每個點的顏色集合的迭代交換操作，使得每個子目標函數都達到最優，直到滿足總目標函數的要求。本算法較以往的人工染色而言節約了大量的人力和時間成本，而且能夠在很短的時間內正確得到人工染色所得不到的上百個頂點以上圖的染色結果。利用該算法，可以快速地獲得大量的研究數據，驗證了G的鄰點可區別均勻V-全染色的一些相關猜想，為G的鄰點可區別均勻V-全染色其他的相關定理和猜想的證明提供了基礎數據支持，未來將會繼續實現算法來解決圖G的相關可區別染色問題。

)

[1]ZHANGZ,LIUL,WANGJ.Adjacentstrongedgecoloringofgraphs[J].AppliedMathematicsLetters, 2002, 15(5): 623-626.

[2]ZHANGZ,QIUP,XUB,etal.Vertex-distinguishingtotalcoloringofgraphs[J].ArsCombinatoria, 2008, 87: 33-45.

[3]BURRISAC.Vertex-distinguishingedge-colorings[D].Memphis:MemphisStateUniversity, 1993： 1-9.

[4]ZHANGZ,CHENX,LIJ,etal.Onadjacent-vertex-distinguishingtotalcoloringofgraphs[J].ScienceinChinaSeriesA:Mathematics, 2005, 48(3): 289-299.

[5] 王雙莉，張荔，李沐春.若干冠圖的鄰點可區別的V-全染色[J].蘭州交通大學學報，2012,31(4):138-141.(WANGSL,ZHANGL,LIMC.TheadjacentvertexdistinguishingV-totalcoloringofsomecoronagraphs[J].JournalofLanzhouJiaotongUniversity, 2012, 31(4): 138-141.)

[6] 馬剛.一些積圖的點可區別均勻邊色數[J].數學雜志,2014,34(5):1005-1009.(MAG.Onthevertex-distinguishing-equitableedgecharomaticnumberofsomeproductgraphs[J].JournalofMathematics, 2014, 34(5): 1005-1009.)

[7] 林銼云，董家禮.多目標優化的方法與理論[M].長春：吉林教育出版社，1992:1-16.(LINCY,DONGJL.Multi-objectiveOptimizationMethodandTheory[M].Changchun：JilinEducationPublishingHouse, 1992: 1-16.)

[8] 嚴謙泰，姚艷紅.圖的一般鄰點可區別均勻邊染色和均勻全染色[J].數學的實踐與認識,2015,45(10):179-184.(YANQT,YAOYH.Ontheadjacentspectralradiusofcycleswithfixedweightsets[J].MathematicsinPracticeandTheory, 2015, 45(10): 179-184.)

[9] 宋慧敏,龍和平,吳建良.Halin圖的均勻邊染色[J].山東大學學報:理學版,2003,38(2):32-34,46.(SONGHM,LONGHP,WUJL.Theequitableedge-coloringofHalingraphs[J].JournalofShandongUniversity(NaturalScience), 2003, 38(2): 32-34, 46.)

[10]BONDYJA,MURTYSR.GraphTheorywithApplications[M].Oxford,UK:ElsevierScience, 1976: 10-35.

[11] 馬小姝，李宇龍，嚴浪.傳統多目標優化方法和多目標遺傳算法的比較綜述[J].電氣傳動自動化,2010, 32(3): 48-50, 53.(MAXS,LIYL,YANL.Comparsionreviewoftraditionalmulti-objectiveoptimizationmethodsandmulti-objectivegeneticalgorithm[J].ElectricalDriveAutomation, 2010, 32(3): 48-50, 53.)

[12] 李世玲，陳祥恩，王治文.完全二部圖K3,n(3≤n≤17)的點可區別E-全染色[J].吉林大學學報(理學版),2015,53(6):1171-1176.(LI S L, CHEN X E, WANG Z W.Vertex-distinguishingE-total coloring of complete bipartite graphK3,nwith 3≤n≤17 [J].Journal of Jilin University (Science Edition), 2015, 53(6): 1171-1176.)

[13] 孟獻青.立方圖的鄰點可區別全染色及一般鄰點可區別全染色[J].內蒙古師范大學學報(自然科學漢文版),2015,44(1):4-7,11.(MENG X Q.On the neighbor-distinguishing total coloring and the general neighbor-distinguishing total coloring of cubic chart [J].Journal of Inner Mongolia Normal University (Natural Science Edition), 2015, 44(1): 4-7, 11.)

[14] 劉秀麗.若干Mycielski圖的鄰點可區別V-全染色[J].西南師范大學學報(自然科學版),2015,40(12):12-16.(LIU X L.Adjacent vertex-distinguishing V-total coloring on some Mycielski’s graphs [J].Journal of Southwest China Normal University (Natural Science Edition), 2015, 40(12): 12-16.)

[15] 盧永紅，康淑瑰，孟獻青，等.若干冠圖的鄰點可區別V-全染色[J].數學的實踐與認識,2014,44(8):170-179.(LU Y H, KANG S G, MENG X Q, et al.Adjacent vertex-distinguishing V-total coloring of several categories of corona graphs [J].Mathematics in Practice and Theory, 2014, 44(8): 170-179.)

[16] 楊超，姚兵，王宏宇，等.小度數圖的鄰點可區別全染色[J].數學雜志,2014,34(2):295-302.(YANG C, YAO B, WANG H Y, et al.Adjacent vertex distinguishing total colorings of graphs with smaller degrees [J].Journal of Mathematics, 2014, 34(2): 295-302.)

This work is partially supported by the National Natural Science Foundation of China (11461038, 61163010, 61163037), the Youth Fund of Lanzhou Jiaotong University (2016014).

CAO Daotong, born in 1990, M.S.candidate.His research interests include intelligent computing, combinatorial optimization.

LI Jingwen, born in 1965, professor.His research interests include graph theory and its application.

JIANG Hongdou, born in 1991, M.S.candidate.Her research interests include intelligent computing, combinatorial optimization.

WEN Fei, born in 1984, Ph.D., lecturer.His research interests include graph theory and its application.

Adjacent vertex-distinguishing equitable V-total coloring algorithm of graph based on multi-objective optimization

CAO Daotong1*，LI Jingwen1，JIANG Hongdou1，WEN Fei2

(1.SchoolofElectronicandInformationEngineering,LanzhouJiaotongUniversity,LanzhouGansu730070,China；2.InstituteofAppliedMathematics,LanzhouJiaotongUniversity,LanzhouGansu730070,China)

Adjacent Vertex-Distinguishing Equitable V-Total Coloring (AVDEVTC) of a graph means on the basis of adjacent vertex-distinguishing V-total coloring, the differences between every two colors used in coloring are no more than one.The minimum number of colors used for completing AVDEVTC is called Adjacent Vertex-Distinguishing Equitable V-Total Chromatic Number (AVDEVTCN).A multi-objective optimization coloring algorithm was proposed to resolve the problem of AVDEVTC of the graph.A main objective function and four subobjective functions were designed according to the conditions of AVDEVTC.Every subobjective function was optimized to meet the requirements of the main objective function by the iterative exchange operation of the color set of every vertex on the coloring matrix, thus completed the coloring.Theoretical analysis and experimental comparison show that all of the simple connected graphs within eight vertices have the AVDEVTC, and their AVDEVTCN are between the maximum degree plus 1 and the maximum degree plus 2.The experimental result indicates that the proposed coloring algorithm can correctly calculate the AVDEVTCN of graphs within 1 000 vertices in a short period of time.

coloring algorithm; objective function; multi-objective optimization; Adjacent Vertex-Distinguishing Equitable V-Total Coloring (AVDEVTC); Adjacent Vertex-Distinguishing Equitable V-Total Chromatic Number (AVDEVTCN)

2016- 06- 15;

2016- 08- 03。

國家自然科學基金資助項目(11461038，61163010，61163037)；蘭州交通大學青年基金資助項目(2016014)。

曹道通(1990—)，男，江蘇徐州人，碩士研究生，主要研究方向：智能計算、組合優化； 李敬文(1965—)，男，遼寧沈陽人，教授，CCF會員，主要研究方向：圖論及應用； 江紅豆(1991—)，女，甘肅慶陽人，碩士研究生，主要研究方向：智能計算、組合優化； 文飛(1984—)，男，甘肅天水人，講師，博士，主要研究方向：圖論及應用。

1001- 9081(2017)02- 0457- 06

10.11772/j.issn.1001- 9081.2017.02.0457

TP

A