隨機圖的點可區別V-全染色算法

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

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

1 引言

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

2 相關定義

定義1.1[15]對于階數至少為2的簡單連通圖G，f是從V(G)∪E(G)到正整數集 {1，2，…，k}的映射，而C(u)={f(u)}∪{f(uv)|uv∈E(G)}稱為點u的色集合，稱為點u的色補集合，點u的度數記作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點可區別V-全染色，簡記為k-VDVTC（k-vertex-distinguishing V-total coloring），(G)=min{k|G存在k-VDVTC}為圖G的點可區別V-全色數。

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

猜想[15]對于簡單圖G，有。

3 點可區別V-全染色算法

點可區別V-全染色必須滿足條件如下：（1）相鄰邊染色不同；（2）頂點與其關聯邊染色不同；（3）所有點的色集合不同，由此三個條件可以構造出算法的約束函數。

3.1 構建點可區別V-全染色算法的目標函數

（1）邊約束函數

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

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

（2）點邊約束函數

（3）色集合約束函數

（4）總體目標函數

由上述三個染色條件的約束函數，給出總體目標函數：Yvdvtc=Yae+Yve+Yc。

3.2 點可區別V-全染色的算法步驟

算法：點可區別V-全染色算法

輸入：給定圖的鄰接矩陣，或者給定圖的頂點數。

算法步驟：

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

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

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

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

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

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

步驟4檢測度相同的頂點的色集合是否相同，若都不同則進入步驟5。

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

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

4 點可區別V-全染色算法測試

本文選取9個點的圖進行測試，其鄰接矩陣如矩陣（1）所示：

詳細染色步驟為：

（1）邊預染色。由鄰接矩陣可知，度為5、6、7、8的頂點個數分別為3、4、1、1，由全組合度猜想顏色數k=9。利用random（）函數產生9組1到9的隨機數，根據染色規則對邊預染色。邊預染色結果如矩陣（2）所示：

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

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

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

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

本文從800以內的點數中選取了99個測試案例，測試環境：操作系統為Win7，內存為4 GB。在點可區別V-全染色中，點數、色數、邊密度、平均度之間的關系如圖1、2、3所示。

圖1 點數、色數、邊密度關系圖

圖2 點數、色數、邊密度關系圖

圖3 點數、色數、平均度關系圖

5 點可區別V-全染色算法復雜度分析

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

6 結論

本文給出了針對隨機圖的點可區別V-全染色算法，該算法借助染色矩陣及色補集合逐步迭代交換以實現目標函數設定的目標。文中還對算法的時間復雜度進行了分析，其時間復雜度為T(n)=O(n3)，但該算法的空間復雜度較高，當圖的頂點個數比較多時（超過2 000左右），測試出現問題，不能完成染色。本算法已經過大量測試，求出了8個點內（179 404 840個）和800個點內隨機抽取的5億個簡單連通圖的點可區別V-全色數，給出了點數、色數、邊密度和平均度之間的關系曲線圖（因畫圖限制，挑選了99個有代表性的圖如圖1、2），為進一步證明圖的點可區別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.