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

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

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

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

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

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

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

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

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

0 引言

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

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

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

1.1 算法描述

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

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

輸入 圖G的鄰接矩陣；

輸出 圖G的AVDEVTC矩陣。

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

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

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

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

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

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

a)兩點(diǎn)之間有邊；

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

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

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

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

利用圖的鄰點(diǎn)可區(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的定義，該算法必須滿足如下幾個(gè)子目標(biāo)：①相鄰邊染不同色；②頂點(diǎn)與其關(guān)聯(lián)邊染不同色； ③相鄰頂點(diǎn)的色集合不同；④任意兩種顏色的使用次數(shù)相差不超過1。由以上4個(gè)條件可以構(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個(gè)頂點(diǎn)(v1,v2,…,vn)，因此決策變量X2=(v1,v2,…,vn)。

3)根據(jù)條件③，圖G共有n個(gè)頂點(diǎn)，色補(bǔ)集合(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)點(diǎn)邊目標(biāo)函數(shù)。

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

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

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

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

均勻目標(biāo)函數(shù)的約束條件是任意兩個(gè)顏色的使用次數(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ù)定義如下：對任意兩點(diǎn)構(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四個(gè)條件的總數(shù)量，當(dāng)且僅當(dāng)F(X)=0時(shí)總目標(biāo)得到最優(yōu)解，即染色成功。

2 染色實(shí)例

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

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

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

表1 初始圖的鄰接矩陣

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

2.2 頂點(diǎn)染色

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

2.3 邊預(yù)染色

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

表2 初始染色矩陣

2.4 查找沖突集

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

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

表3 沖突集查找

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

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

檢驗(yàn)顏色使用情況是否均勻，顏色為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次，因此嘗試將一個(gè)邊的顏色由6改為8。按照算法，找到了邊v7v6的顏色為6，將其顏色調(diào)整為8，即f(v7v6):6→8。

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

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

3 實(shí)驗(yàn)結(jié)果數(shù)據(jù)集

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表9 8個(gè)頂點(diǎn)以內(nèi)所有圖的運(yùn)算時(shí)間 s

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

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

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

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

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

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

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

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

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

5 結(jié)語

本文提出了一種啟發(fā)式優(yōu)化算法來解決新問題：即圖的鄰點(diǎn)可區(qū)別均勻V-全染色問題。算法設(shè)計(jì)了一個(gè)總目標(biāo)函數(shù)和四個(gè)子目標(biāo)函數(shù)來對應(yīng)AVDEVTC的多個(gè)約束條件，在染色矩陣上通過每個(gè)點(diǎn)的顏色集合的迭代交換操作，使得每個(gè)子目標(biāo)函數(shù)都達(dá)到最優(yōu)，直到滿足總目標(biāo)函數(shù)的要求。本算法較以往的人工染色而言節(jié)約了大量的人力和時(shí)間成本，而且能夠在很短的時(shí)間內(nèi)正確得到人工染色所得不到的上百個(gè)頂點(diǎn)以上圖的染色結(jié)果。利用該算法，可以快速地獲得大量的研究數(shù)據(jù)，驗(yàn)證了G的鄰點(diǎn)可區(qū)別均勻V-全染色的一些相關(guān)猜想，為G的鄰點(diǎn)可區(qū)別均勻V-全染色其他的相關(guān)定理和猜想的證明提供了基礎(chǔ)數(shù)據(jù)支持，未來將會繼續(xù)實(shí)現(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] 王雙莉，張荔，李沐春.若干冠圖的鄰點(diǎn)可區(qū)別的V-全染色[J].蘭州交通大學(xué)學(xué)報(bào)，2012,31(4):138-141.(WANGSL,ZHANGL,LIMC.TheadjacentvertexdistinguishingV-totalcoloringofsomecoronagraphs[J].JournalofLanzhouJiaotongUniversity, 2012, 31(4): 138-141.)

[6] 馬剛.一些積圖的點(diǎn)可區(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)謙泰，姚艷紅.圖的一般鄰點(diǎn)可區(qū)別均勻邊染色和均勻全染色[J].數(shù)學(xué)的實(shí)踐與認(rèn)識,2015,45(10):179-184.(YANQT,YAOYH.Ontheadjacentspectralradiusofcycleswithfixedweightsets[J].MathematicsinPracticeandTheory, 2015, 45(10): 179-184.)

[9] 宋慧敏,龍和平,吳建良.Halin圖的均勻邊染色[J].山東大學(xué)學(xué)報(bào):理學(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)的點(diǎn)可區(qū)別E-全染色[J].吉林大學(xué)學(xué)報(bào)(理學(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)青.立方圖的鄰點(diǎn)可區(qū)別全染色及一般鄰點(diǎn)可區(qū)別全染色[J].內(nèi)蒙古師范大學(xué)學(xué)報(bào)(自然科學(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圖的鄰點(diǎn)可區(qū)別V-全染色[J].西南師范大學(xué)學(xué)報(bào)(自然科學(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)青，等.若干冠圖的鄰點(diǎn)可區(qū)別V-全染色[J].數(shù)學(xué)的實(shí)踐與認(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ù)圖的鄰點(diǎn)可區(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é)基金資助項(xiàng)目(11461038，61163010，61163037)；蘭州交通大學(xué)青年基金資助項(xiàng)目(2016014)。

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

1001- 9081(2017)02- 0457- 06

10.11772/j.issn.1001- 9081.2017.02.0457

TP

A