邊著色圖上最大弱適當樹問題近似算法

金世豪，陳光亭，陳 永，張 安

(1.杭州電子科技大學理學院，浙江 杭州 310018；2.臺州學院電子與信息工程學院，浙江 臺州 318000)

0 引 言

圖的著色理論是圖論的重要分支之一，是圖論研究中最活躍的方向之一。邊著色圖上的生成樹問題在生物信息學、網絡設計和網絡通信等領域中有著重要應用[1]。邊著色圖上的生成樹問題可以從實際問題中提煉出普適性的理論問題，使用數學的形式表達設計高效算法以解決問題。圖著色中最基本的問題是把顏色分配給邊，相鄰的邊著不同的顏色。

早期關于邊著色圖的研究工作都是考慮每對邊顏色都不相同的生成樹問題即彩虹生成樹[2-4]，文獻[5-6]證明了完全圖或完全二部圖的任意邊著色中多種顏色生成樹的存在性；文獻[7]指出，當頂點的鄰邊顏色數大于等于頂點個數一半時，存在適當生成樹；文獻[8]指出，增加顏色的個數，邊著色中存在適當路徑和適當圈的概率越大；文獻[9]給出了在邊著色圖中，把單色子圖頂點劃分的方法。最近關于邊著色圖中適當邊著色(Proper Edge-colored)問題，文獻[10]給出了沒有適當著色圈的完全邊著色圖的算法，此算法的時間復雜度為O(n2)，同時證明了當顏色數c≥2時，最大弱適當樹(Maximum Weak Proper Tree，MWT)問題是NP-hard。基于此，本文重點研究顏色數c=2時求解最大弱適當樹問題的近似算法設計及其理論分析。

1 邊著色圖上最大弱適當樹問題

定義1設T是邊著色圖Gc的1個子圖，將子圖邊著色，使得每個頂點的鄰邊著不同的顏色。如果子圖為1個路徑，則稱為適當路徑(Proper Path)。

定義2如果子圖是1棵樹，即這個子圖是連通且無圈子圖，當子圖覆蓋Gc的所有頂點則稱樹為Gc的生成樹，在生成樹上固定一個頂點為樹的根，根到樹的任何葉子都是適當路徑，但樹頂點的鄰邊能著相同顏色，則稱為弱適當樹。

對于邊著色圖Gc，在圖Gc上找到包含頂點最多的弱適當樹，這一問題稱為最大弱適當樹(Maximum Weak Proper Tree，MWT)。下面給出1個顏色數c=2的邊著色圖例子。

給出3層結構的邊著色圖Gc的例子如圖1所示，本文所有圖中虛線代表紅線，實線代表藍線。圖1中，第1層只有1個根節點r，第2層每2個頂點ai1,ai2(i∈{1,…,s},s=6)為一組，ai1,ai2之間有邊并隨機著紅或藍1種顏色，組與組之間沒有邊，根r到每1組的2個頂點ai1,ai2(i∈{1,…,s})都有邊，所有的從根r到ai1,ai2(i∈{1,…,s})的邊隨機著紅或藍1種顏色，根r與每2個頂點ai1,ai2構成1個三角形，因此有s個這樣的三角形。因為只能選取其中2條邊，所以共有以下3種組合：{rai1，rai2}，{rai1，ai1ai2}，{rai2，ai2ai1}。第3層有n個頂點(c1,c2,…,cn)，每個頂點只能和任意3個三角形有邊，且只能連接每個三角形第2層的1個頂點，邊的顏色以相同的概率著紅或藍其中1種顏色。

圖1 s=6時，3層結構圖Gc

2 MWT問題的算法設計與分析

通過研究圖1的結構，以貪婪迭代為基礎得到求解MWT問題的近似算法——貪婪算法GA。貪婪算法GA是1個多項式時間的近似算法，其主要步驟如下。

(1)選擇頂點r為生成樹T的根。

(2)進行預處理。依據三角形3種可能組合：{rai1,rai2},{rai1,ai1ai2},{rai2,ai2ai1},刪除第2層與第3層之間不可行的邊，即刪除不能連接上述3種情況中的任意1種的邊。

(3)選取點。生成樹T選取第2層的所有點；對每個三角形的3種組合，選擇連接到第3層頂點數量最多的組合到生成樹T中，以及選取所連接的第3層的頂點到生成樹T中。

(4)重復步驟3，直到到s個三角形所對應的s個組合都出現在生成樹T中，算法停止。

(5)輸出T。

圖2 三角形結構

證明因為邊著色的顏色只有紅藍2種顏色，所以三角形有2種結構，如圖2所示。

綜上，引理1得證。

圖3 三角形可能組合

證明對實例I進行預處理之后，用nj表示前j個三角形與第3層相鄰頂點個數總和(ns=n),nij表示第j個三角形與前i個三角形共有頂點個數(i

(1)

(2)

當s=k-1時，則有

(3)

綜上，引理2得證。

定理1貪婪算法GA的最壞情況界為2，且該界是緊的。

下面通過1個緊例來驗證貪婪算法GA的最壞情況界為2。通過貪婪算法GA刪去不可選取的邊得到實例如圖4所示，第1層1個頂點r，第2層的頂點為ai1,ai2(i∈{1,2,3,4,5,6})，第3層共有4n-4個頂點。把第3層的所有頂點分成8個頂點族，分別為A，B，C，D，E，F，G，H。

圖4 貪婪算法GA的緊例

根據貪婪算法GA從第1個三角開始遍歷，選取{ra11,ra12}，因為B和C的頂點族加起來大于A和D的頂點族，所以選取{ra21，a21a22，a21B，a22C}，依次下去算法解為{ra31,ra32}，{ra41,a41a42,a41F,a42G}，{ra51,ra52},{ra61,ra62}，共13+2n個頂點，即GA(I)=13+2n，而最優解可以選取到全部頂點共OPT(I)=13+4n-4。

3 結束語

本文提出了頂點個數最多的邊著色圖上弱適當樹問題的多項式時間近似算法，并證明算法的最壞情況界為2。邊著色圖的圖結構以及著色的顏色數是設計近似算法和得到最壞情況界的關鍵因素，后續將針對這2個因素，即在顏色數為一般情況、圖結構是完全圖或二部圖時，對邊著色MWT問題近似算法的設計展開進一步研究。