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

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

0 引 言

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

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

1 邊著色圖上最大弱適當(dāng)樹問題

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

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

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

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

圖1 s=6時(shí)，3層結(jié)構(gòu)圖Gc

2 MWT問題的算法設(shè)計(jì)與分析

通過研究圖1的結(jié)構(gòu)，以貪婪迭代為基礎(chǔ)得到求解MWT問題的近似算法——貪婪算法GA。貪婪算法GA是1個(gè)多項(xiàng)式時(shí)間的近似算法，其主要步驟如下。

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

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

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

(4)重復(fù)步驟3，直到到s個(gè)三角形所對應(yīng)的s個(gè)組合都出現(xiàn)在生成樹T中，算法停止。

(5)輸出T。

圖2 三角形結(jié)構(gòu)

證明因?yàn)檫呏念伾挥屑t藍(lán)2種顏色，所以三角形有2種結(jié)構(gòu)，如圖2所示。

綜上，引理1得證。

圖3 三角形可能組合

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

(1)

(2)

當(dāng)s=k-1時(shí)，則有

(3)

綜上，引理2得證。

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

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

圖4 貪婪算法GA的緊例

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

3 結(jié)束語

本文提出了頂點(diǎn)個(gè)數(shù)最多的邊著色圖上弱適當(dāng)樹問題的多項(xiàng)式時(shí)間近似算法，并證明算法的最壞情況界為2。邊著色圖的圖結(jié)構(gòu)以及著色的顏色數(shù)是設(shè)計(jì)近似算法和得到最壞情況界的關(guān)鍵因素，后續(xù)將針對這2個(gè)因素，即在顏色數(shù)為一般情況、圖結(jié)構(gòu)是完全圖或二部圖時(shí)，對邊著色MWT問題近似算法的設(shè)計(jì)展開進(jìn)一步研究。