隨機(jī)圖的點(diǎn)可區(qū)別V-全染色算法

胡騰云，尹 波，代素敏，李敬文

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

1 引言

圖的染色問題一直是圖論中的一個(gè)重要的研究課題，具有重要的理論和現(xiàn)實(shí)意義，組合優(yōu)化、資源分配、交通運(yùn)輸?shù)葐栴}都可以轉(zhuǎn)化為圖的染色問題來解決。圖染色問題起源于著名的“四色猜想”，20世紀(jì)初期，一些數(shù)學(xué)工作者著力于研究圖的點(diǎn)染色、邊染色，直到后來提出了點(diǎn)可區(qū)別正常邊染色。1965年，M.Behzad和V.G.Vizing分別獨(dú)立地提出了著名的全染色猜想[1-2]；2002年，張忠輔在點(diǎn)可區(qū)別正常邊染色的基礎(chǔ)上提出了圖的鄰強(qiáng)（點(diǎn)可區(qū)別）邊染色[3]的概念和猜想，國(guó)內(nèi)外專家也做了大量研究[4-9]；隨后張忠輔等人又相繼提出了鄰點(diǎn)可區(qū)別全染色、點(diǎn)可區(qū)別全染色、距離為β的點(diǎn)可區(qū)別邊染色、距離為β的點(diǎn)可區(qū)別全染色等概念和猜想[10-13]，受到了國(guó)內(nèi)外的廣泛關(guān)注。目前所獲得的關(guān)于圖的可區(qū)別染色的大部分結(jié)果都是針對(duì)特殊圖的，如路、圈、星、扇、輪、完全二部圖、樹以及它們的聯(lián)圖等，但現(xiàn)實(shí)中的問題轉(zhuǎn)換成圖運(yùn)用圖染色方法解決時(shí)，面對(duì)的絕大多數(shù)都是隨機(jī)圖，本文設(shè)計(jì)了一種算法，能夠求出2 000個(gè)點(diǎn)以內(nèi)簡(jiǎn)單連通圖的點(diǎn)可區(qū)別V-全色數(shù)，文中給出算法測(cè)試案例的詳細(xì)執(zhí)行步驟，并給出了部分圖的點(diǎn)數(shù)、色數(shù)、邊密度和平均度的曲線關(guān)系圖。本文所研究的圖為簡(jiǎn)單連通圖，文中所用術(shù)語(yǔ)及符號(hào)參見文獻(xiàn)[14]。

2 相關(guān)定義

定義1.1[15]對(duì)于階數(shù)至少為2的簡(jiǎn)單連通圖G，f是從V(G)∪E(G)到正整數(shù)集 {1，2，…，k}的映射，而C(u)={f(u)}∪{f(uv)|uv∈E(G)}稱為點(diǎn)u的色集合，稱為點(diǎn)u的色補(bǔ)集合，點(diǎn)u的度數(shù)記作d(u)。如果

（1）?uv∈E(G)，有f(u)≠f(uv)，f(v)≠f(uv)；

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

（3）?u，v∈V(G)，有C(u)≠C(v)。

則稱f是圖G的k點(diǎn)可區(qū)別V-全染色，簡(jiǎn)記為k-VDVTC（k-vertex-distinguishing V-total coloring），(G)=min{k|G存在k-VDVTC}為圖G的點(diǎn)可區(qū)別V-全色數(shù)。

定義1.2[15]設(shè)G(V，E)是一個(gè)簡(jiǎn)單圖，ni為V(G)中度為i的點(diǎn)的個(gè)數(shù)，稱δ(G)≤i≤ Δ(G)}為G的組合全度，其中δ(G)和Δ(G)分別為G的最小度和最大度。

猜想[15]對(duì)于簡(jiǎn)單圖G，有。

3 點(diǎn)可區(qū)別V-全染色算法

點(diǎn)可區(qū)別V-全染色必須滿足條件如下：（1）相鄰邊染色不同；（2）頂點(diǎn)與其關(guān)聯(lián)邊染色不同；（3）所有點(diǎn)的色集合不同，由此三個(gè)條件可以構(gòu)造出算法的約束函數(shù)。

3.1 構(gòu)建點(diǎn)可區(qū)別V-全染色算法的目標(biāo)函數(shù)

（1）邊約束函數(shù)

相鄰的邊必須染不同的顏色。邊約束函數(shù)定義如下：

其中兩電平VSC的接地需求包括2個(gè)方面：(1)交流側(cè)濾波器的接地需求；(2)直流側(cè)電容的接地需求。由于VSC電平數(shù)少，采用高頻脈寬調(diào)試方式，開關(guān)頻率高，換流器出口將含有較大的高次諧波，需在變壓器閥側(cè)加裝較小容量的高頻諧波濾波器。VSC在直流線路上有集中電容，可采取電容中點(diǎn)直接接地或通過組件接地的方式，如圖1所示。

（2）點(diǎn)邊約束函數(shù)

（3）色集合約束函數(shù)

（4）總體目標(biāo)函數(shù)

由上述三個(gè)染色條件的約束函數(shù)，給出總體目標(biāo)函數(shù)：Yvdvtc=Yae+Yve+Yc。

3.2 點(diǎn)可區(qū)別V-全染色的算法步驟

算法：點(diǎn)可區(qū)別V-全染色算法

輸入：給定圖的鄰接矩陣，或者給定圖的頂點(diǎn)數(shù)。

算法步驟：

步驟1接收給定的鄰接矩陣，或者接收?qǐng)D的點(diǎn)數(shù)n，生成n×n的空矩陣，由random（）隨機(jī)地生成邊的總個(gè)數(shù)，并將矩陣的主對(duì)角線上方的n×(n-1)/2位置上隨機(jī)地放置1；若主對(duì)角線上方元素中的每一行或者每一列至少有一個(gè)1，則將主對(duì)角線下方元素對(duì)稱補(bǔ)充完整，主對(duì)角線的元素全放置元素0，輸出鄰接矩陣，否則重新生成。

步驟2將圖的鄰接矩陣存儲(chǔ)在color[][]中，計(jì)算各頂點(diǎn)的度d(vi)，并由組合全度定義計(jì)算所需要的色數(shù)k，并由random（）生成n組1到k之間的隨機(jī)數(shù)對(duì)G的邊預(yù)染色，保證對(duì)于頂點(diǎn)vi，color[i][i+1]至color[i][n]中的顏色互不相同，并且所取的顏色不是color[i][1]至color[i][i-1]中的任何一個(gè)。

步驟3檢測(cè)頂點(diǎn)vi的度d(vi)與其色補(bǔ)集合中元素個(gè)數(shù)之和是否等于k，若則順序檢測(cè)下一個(gè)頂點(diǎn)，否則做如下檢測(cè)：

①若f(uv)=f(uw)且，則令f(uv)=f(vu)=a1，修改，計(jì)算。

②若f(uv)=f(uw)且，則令f(uw)=f(wu)=b1，修改，計(jì)算。

③若f(uv)=f(uw)且則設(shè)，如果存在m∈{1，2，…，i}使得f(vp)=km且 ，則 令f(vp)=f(pv)=c1，f(uv)=km，并修改，計(jì)算；重復(fù)以上步驟直至。

步驟4檢測(cè)度相同的頂點(diǎn)的色集合是否相同，若都不同則進(jìn)入步驟5。

步驟5選擇頂點(diǎn)染色，將各頂點(diǎn)按照其色補(bǔ)集合中的元素個(gè)數(shù)從小到大排序，設(shè)當(dāng)前待染定點(diǎn)為{k1，k2，…，kx} ，依次取出一個(gè)元素km(m∈{1，2，…，x})給當(dāng)前頂點(diǎn)染色，若存在頂點(diǎn)vj使得，說明頂點(diǎn)色集合相同，令m+1，否則令f(vi)=km；直至所有頂點(diǎn)染色完畢。

步驟6染色完成，判斷結(jié)果集是否正確，若出現(xiàn)頂點(diǎn)色集合相同，將k增加1返回步驟2，否則輸出正確結(jié)果。

4 點(diǎn)可區(qū)別V-全染色算法測(cè)試

本文選取9個(gè)點(diǎn)的圖進(jìn)行測(cè)試，其鄰接矩陣如矩陣（1）所示：

詳細(xì)染色步驟為：

（1）邊預(yù)染色。由鄰接矩陣可知，度為5、6、7、8的頂點(diǎn)個(gè)數(shù)分別為3、4、1、1，由全組合度猜想顏色數(shù)k=9。利用random（）函數(shù)產(chǎn)生9組1到9的隨機(jī)數(shù)，根據(jù)染色規(guī)則對(duì)邊預(yù)染色。邊預(yù)染色結(jié)果如矩陣（2）所示：

（3）進(jìn)入算法步驟4，檢測(cè)度相同的頂點(diǎn)的色集合是否相同，由（2）中（i從1到9）可知，不存在頂點(diǎn)色集合沖突的情形，因此進(jìn)入頂點(diǎn)染色的步驟。

（4）給頂點(diǎn)染色。將各頂點(diǎn)按照其色補(bǔ)集合中的元素個(gè)數(shù)從小到大排序，順序依次為：v4，v2，v3，v5，v6，v9，v1，v7，v8按照步驟 5給頂點(diǎn)染色，染色結(jié)果如矩陣（4）所示：

Yvdvtc=Yae+Yve+Yc=0，染色成功。

由以上結(jié)果可知，k=9即，由于μT(G)=9，所以本結(jié)果符合點(diǎn)可區(qū)別V-全染色猜想：μT(G)≤χvvt(G)≤μT(G)+1。

本文從800以內(nèi)的點(diǎn)數(shù)中選取了99個(gè)測(cè)試案例，測(cè)試環(huán)境：操作系統(tǒng)為Win7，內(nèi)存為4 GB。在點(diǎn)可區(qū)別V-全染色中，點(diǎn)數(shù)、色數(shù)、邊密度、平均度之間的關(guān)系如圖1、2、3所示。

圖1 點(diǎn)數(shù)、色數(shù)、邊密度關(guān)系圖

圖2 點(diǎn)數(shù)、色數(shù)、邊密度關(guān)系圖

圖3 點(diǎn)數(shù)、色數(shù)、平均度關(guān)系圖

5 點(diǎn)可區(qū)別V-全染色算法復(fù)雜度分析

由于本算法采用的n×n鄰接矩陣來存儲(chǔ)頂點(diǎn)和邊的顏色，所以算法步驟1和步驟2在生成圖和邊預(yù)染色方面算法的時(shí)間復(fù)雜度都為O(n2)；步驟3和步驟4調(diào)整色集合沖突，其最壞復(fù)雜度為O(n3)；步驟5給n個(gè)頂點(diǎn)染色，首先必須將頂點(diǎn)按其色補(bǔ)集合元素個(gè)數(shù)從小到大排序，其最壞時(shí)間復(fù)雜度為O(n2)，給頂點(diǎn)染色的時(shí)間復(fù)雜度為O(n)。綜合分析，總算法的時(shí)間復(fù)雜度為T(n)=O(n3)。

6 結(jié)論

本文給出了針對(duì)隨機(jī)圖的點(diǎn)可區(qū)別V-全染色算法，該算法借助染色矩陣及色補(bǔ)集合逐步迭代交換以實(shí)現(xiàn)目標(biāo)函數(shù)設(shè)定的目標(biāo)。文中還對(duì)算法的時(shí)間復(fù)雜度進(jìn)行了分析，其時(shí)間復(fù)雜度為T(n)=O(n3)，但該算法的空間復(fù)雜度較高，當(dāng)圖的頂點(diǎn)個(gè)數(shù)比較多時(shí)（超過2 000左右），測(cè)試出現(xiàn)問題，不能完成染色。本算法已經(jīng)過大量測(cè)試，求出了8個(gè)點(diǎn)內(nèi)（179 404 840個(gè)）和800個(gè)點(diǎn)內(nèi)隨機(jī)抽取的5億個(gè)簡(jiǎn)單連通圖的點(diǎn)可區(qū)別V-全色數(shù)，給出了點(diǎn)數(shù)、色數(shù)、邊密度和平均度之間的關(guān)系曲線圖（因畫圖限制，挑選了99個(gè)有代表性的圖如圖1、2），為進(jìn)一步證明圖的點(diǎn)可區(qū)別V-全染色猜想提供新思路。

[1]Vizing V G.On an estimate of the chromatic class of a p-graph（Russian）[J].Discret Analiz，1964，3：25-30.

[2]Behzad M.Graphs and their chromatic numbers[D].Michigan：Michigan State University，1965.

[3]Zhang Zhongfu，Liu Linzhong，Wang Jianfang.Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters，2002，15（3）：623-626.

[4]Balister P N，Gy?ri E，Lehel J，et al.Adjacent vertex distinguishing edge colorings[J].Discrete Math，2006，1（21）：237-250.

[5]Wang Weifan，Wang Yiqiao.Adjacent vertex distinguishing edge-colorings of graphs with smaller maximum average degree[J].Journal of Combinatorial Optimization，2008，19（4）：471-485.

[6]Hocquard H，Montassier M.Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five[J].Electronic Notes in Discrete Mathematics，2011，38：457-462.

[7]Wang Weifan，Wang Yiqiao.Adjacent vertex-distinguishing edge colorings of K4-minor free graphs[J].Applied Mathematics Letters，2011，24（12）：2034-2037.

[8]Akbari S，Bidkhhori H，Nosratir N.Strong edge colorings of graphs[J].Discrete Mathetics，2006，306（23）：3005-3010.

[9]Hatami H.Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J].J Combin Theory：Series B，2005，95（2）：246-256.

[10]Zhang Zhongfu，Chen Xiangen，Li Jingwen et al.On adjacent vertex distinguishing total coloring of graphs[J].Science in China Ser A：Mathematics，2005，48（3）：289-299.

[11]Zhang Zhongfu，Qiu Pengxiang，Xu Baogen，et al.Vertex distinguishing total coloring of graphs[J].Ars Combinatoria，2008，87（2）：33-45.

[12]Zhang Zhongfu，Li Jingwen.D(β)-vertex distinguishing edge coloring of graphs[J].Journal of Mathematics，2006，49（3）：703-708.

[13]Zhang Zhongfu，Li Jingwen，Chen Xiangen，et al.D(β)-vertex distinguishing total coloring of graphs[J].Science in China Series A：Mathematics，2006，49（10）：1430-1440.

[14]Chen Xiangen，Gao Yuping，Yao Bing.Not necessarily proper total colorings which are adjacent vertex distinguishing[J].InternationalJournalofComputerMathematics，2013，90（11）：2298-2307.

[15]Bondy J A，Murty U S R.Graph theory with applications[M].New York：The Macmillan Press Ltd，1976.