多目標(biāo)優(yōu)化的圖的鄰點可區(qū)別均勻V-全染色算法

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

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

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

多目標(biāo)優(yōu)化的圖的鄰點可區(qū)別均勻V-全染色算法

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

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

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

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

染色算法；目標(biāo)函數(shù)；多目標(biāo)優(yōu)化；鄰點可區(qū)別均勻V-全染色；鄰點可區(qū)別均勻V-全色數(shù)

0 引言

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

定義1[5]設(shè)G(V,E)是階數(shù)不小于2的簡單連通圖G，k為正整數(shù)，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-鄰點可區(qū)別V-全染色，簡記為k-AVDVTC，并將χvt(G)=min{k|k-AVDVTC ofG}稱為圖G的鄰點可區(qū)別V-全色數(shù),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}。

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

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

1.1 算法描述

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

算法 鄰點可區(qū)別均勻V-全染色算法。

輸入 圖G的鄰接矩陣；

輸出 圖G的AVDEVTC矩陣。

1)給頂點隨機(jī)染色。

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

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

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

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

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

a)兩點之間有邊；

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

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

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

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

利用圖的鄰點可區(qū)別均勻V-全染色算法能夠?qū)崿F(xiàn)隨機(jī)圖的AVDEVTC。

1.2 構(gòu)建多目標(biāo)優(yōu)化模型

多目標(biāo)優(yōu)化算法流程如圖1所示。

圖1 多目標(biāo)優(yōu)化算法流程

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

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

決策向量為:

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

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

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

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

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

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

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

下面構(gòu)建目標(biāo)函數(shù)：

1)邊染色目標(biāo)函數(shù)。

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

2)點邊目標(biāo)函數(shù)。

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

3)色集合目標(biāo)函數(shù)。

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

4)均勻目標(biāo)函數(shù)。

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

5)總目標(biāo)函數(shù)。

Qavdevtc=minF(X)

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

2 染色實例

本文選取了一個8個頂點的隨機(jī)圖來進(jìn)行測試。

2.1 初始化隨機(jī)圖G

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

表1 初始圖的鄰接矩陣

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

2.2 頂點染色

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

2.3 邊預(yù)染色

在點染色完成后對邊隨機(jī)地預(yù)染色，剔除頂點染色用的顏色，用剩下的顏色給頂點相關(guān)聯(lián)的邊染色。初始染色矩陣如表2所示。

表2 初始染色矩陣

2.4 查找沖突集

2.5 調(diào)整染色沖突

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

表3 沖突集查找

表4 鄰點可區(qū)別非均勻V-全染色結(jié)果

2.6 檢驗色數(shù)是否均勻

檢驗顏色使用情況是否均勻，顏色為6、7、1、2、3、4、5、8的使用次數(shù)分別為4、4、3、3、3、3、3、2?？梢钥闯?，顏色使用不均勻，則按照算法規(guī)則繼續(xù)調(diào)整。顏色6使用了4次，顏色8使用了2次，因此嘗試將一個邊的顏色由6改為8。按照算法，找到了邊v7v6的顏色為6，將其顏色調(diào)整為8，即f(v7v6):6→8。

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

表5 鄰點可區(qū)別均勻V-全染色最終結(jié)果

3 實驗結(jié)果數(shù)據(jù)集

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

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

表6 1 000點以內(nèi)的110萬個圖的測試結(jié)果

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

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

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

表8 度序列、色數(shù)測試結(jié)果

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

圖2 色數(shù)-邊密度變化曲線

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

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

結(jié)論 1 8個頂點以內(nèi)的所有簡單連通圖都存在AVDEVTC。

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

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

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

表9 8個頂點以內(nèi)所有圖的運算時間 s

4 算法時間復(fù)雜度分析

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

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

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

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

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

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

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

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

5 結(jié)語

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

)

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

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

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

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

[9] 宋慧敏,龍和平,吳建良.Halin圖的均勻邊染色[J].山東大學(xué)學(xué)報:理學(xué)版,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] 馬小姝，李宇龍，嚴(yán)浪.傳統(tǒng)多目標(biāo)優(yōu)化方法和多目標(biāo)遺傳算法的比較綜述[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)的點可區(qū)別E-全染色[J].吉林大學(xué)學(xué)報(理學(xué)版),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] 孟獻(xiàn)青.立方圖的鄰點可區(qū)別全染色及一般鄰點可區(qū)別全染色[J].內(nèi)蒙古師范大學(xué)學(xué)報(自然科學(xué)漢文版),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圖的鄰點可區(qū)別V-全染色[J].西南師范大學(xué)學(xué)報(自然科學(xué)版),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] 盧永紅，康淑瑰，孟獻(xiàn)青，等.若干冠圖的鄰點可區(qū)別V-全染色[J].數(shù)學(xué)的實踐與認(rèn)識,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] 楊超，姚兵，王宏宇，等.小度數(shù)圖的鄰點可區(qū)別全染色[J].數(shù)學(xué)雜志,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。

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

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

1001- 9081(2017)02- 0457- 06

10.11772/j.issn.1001- 9081.2017.02.0457

TP

A