周 圓，陳光亭，陳 永，張 安

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

0 引 言

頂點(diǎn)著色圖在多個(gè)學(xué)科領(lǐng)域有著十分重要的作用，文獻(xiàn)[1]介紹了其在生物信息學(xué)中的應(yīng)用。文獻(xiàn)[2]給出了在一般圖中找最大獨(dú)立集問(wèn)題是NP-hard。文獻(xiàn)[3]提出限制奇偶度時(shí)的有界度圖上的近似算法，對(duì)于一些特殊的圖，文獻(xiàn)[4-6]分別提出在無(wú)爪圖(claw-free graph)、無(wú)P5路的圖(P5-free graph)和完美圖(perfect graph)中，尋找最大獨(dú)立及問(wèn)題(Maximum Independent Problem，MIP)是多項(xiàng)式時(shí)間內(nèi)可解的，文獻(xiàn)[7]提出，對(duì)于余圖(cograph)和弦圖(chordal graph)，可在線(xiàn)性時(shí)間內(nèi)解出MIP問(wèn)題。當(dāng)前對(duì)顏色數(shù)最多的獨(dú)立集問(wèn)題(Maximum Colorful Independent Set Problem，MCISP)的研究中，文獻(xiàn)[8]提出聚類(lèi)圖(cluster grpah)和樹(shù)(tree)中的MCISP問(wèn)題是多項(xiàng)式時(shí)間內(nèi)可解并給出相關(guān)算法，而在無(wú)P5路(P5-free graph)圖和余圖(cogrpah)中，求解MCISP問(wèn)題是NP-hard。

1 一般二部圖上的MCISP問(wèn)題

定義1給定任意圖G=(V,E)，將圖G中的頂點(diǎn)集V分為兩部分，分別是V1和V2且V1和V2都是獨(dú)立集，圖G中的邊集E由V1中的頂點(diǎn)到V2中的頂點(diǎn)的連線(xiàn)組成的圖稱(chēng)為二部圖[10],記作G=(V1,V2,E)。

定義2給定任意二部圖G=(V1,V2,E)，V1中的每一個(gè)頂點(diǎn)與V2中的每一個(gè)頂點(diǎn)之間都有邊的圖稱(chēng)為完全二部圖[10]，記作KV1,V2。

定義3給定任意二部圖G=(V1,V2,E)和顏色集C，使得G中每個(gè)頂點(diǎn)都著有C中至少一種顏色的圖為頂點(diǎn)著色圖[8]，其中C中的顏色由自然數(shù)N表示，不同的自然數(shù)i表示不同的顏色，i∈N。|C(Vi)|表示不同集合的不同顏色數(shù)，i∈{1,2}，記作Gc=(V1,V2,E)。

對(duì)于任意給定的頂點(diǎn)著色二部圖Gc=(V1,V2,E)，在圖G上找到一個(gè)包含G中頂點(diǎn)顏色數(shù)最多的獨(dú)立集S，其中集合S記作算法解得到的不同顏色頂點(diǎn)組成的集合，S*表示最優(yōu)解中顏色不同的頂點(diǎn)組成的集合，這一問(wèn)題叫做二部圖上的MCISP問(wèn)題。

下面給出求解MCISP問(wèn)題的一個(gè)多項(xiàng)式時(shí)間近似算法。

算法1:一般二部圖上的近似算法輸入:1個(gè)簡(jiǎn)單二部圖Gc=(V1,V2,E)輸出:Gc中包含顏色最多的獨(dú)立集S步驟:令S=?,比較集合V1與V2中的顏色種類(lèi),若C(V1)≥C(V2),則令S=V1,否則令S=V2,結(jié)束算法。

定理1算法1的最差情況界為2且是緊的。

證明不妨假設(shè)C(V1)≥C(V2)，即S=C(V1)，則由二部圖的性質(zhì)知，C(V1)+C(V2)≥S*，從而2C(V1)≥S*，故2S≥S*。證畢。

圖1 算法1的緊例

2 完全二部圖塊上的MCISP問(wèn)題

給定任意的完全二部圖塊Gc=(U,V,E)和顏色集C，i∈{1,2,…,n}。G中恰有3個(gè)頂點(diǎn)著有相同顏色且每一個(gè)Gi中的頂點(diǎn)顏色都不同，此時(shí)在G中找到一個(gè)獨(dú)立集S并使得其中所包含的顏色種類(lèi)最多。這一問(wèn)題是完全二部圖塊上的MCISP問(wèn)題。

下面給出求解MCISP問(wèn)題的多項(xiàng)式時(shí)間近似算法。

算法2:完全二部圖塊上的近似算法 輸入:1個(gè)簡(jiǎn)單完全二部圖塊Gc=(U,V,E)輸出:G中包含顏色最多的獨(dú)立集S步驟1:令S=?,從任意的完全二部子圖Gcii=(U,V,E)開(kāi)始,其中i∈{1,2,…,n}。比較Gcii中的頂點(diǎn)集Ui和Vi,當(dāng)C(Ui)≥C(Vi)時(shí),令S=Ui,反之令S=Vi;步驟2:對(duì)每個(gè)Gcrr,比較Gcrr中Ur和Vr可在當(dāng)前S中增加的顏色類(lèi),當(dāng)C(Ur∪S)≥C(Vr∪S)時(shí),令S=Ur∪S。反之令S=Vr∪S。其中r≠i,r=1,2,…,n。結(jié)束算法。

當(dāng)A=?時(shí)，S=S*，結(jié)論成立；

當(dāng)A≠?時(shí)，假設(shè)A中至少存在一個(gè)頂點(diǎn)αmp，使得αmp至多對(duì)應(yīng)于S中2個(gè)顏色不同的頂點(diǎn)。其中m,t,p,q∈{1,2,…,n}，m,t表示顏色不同的頂點(diǎn)，p,q表示其所在二部圖分支被選入集合S中的順序。

若αmp對(duì)應(yīng)于S中0個(gè)頂點(diǎn)，但αmp與A中至少一個(gè)頂點(diǎn)αtq所對(duì)應(yīng)的顏色在同一個(gè)二部圖分支中但p≤q，此時(shí)顏色是C(αmp)的頂點(diǎn)所在的原二部圖分支中，除C(αmp)之外只包含C(S)中的顏色，即這些顏色在這一二部圖分支之前已被選入C(S)中，則由算法2可知，C(αmp)∈C(S)與A的定義矛盾。若顏色是C(αmp)的頂點(diǎn)與C(S)中的顏色所在頂點(diǎn)均不在同一二部圖分支上，則顏色是C(αmp)的頂點(diǎn)與顏色是C(S)的頂點(diǎn)在不同的二部圖分支上，此時(shí)可向S中添加包含新顏色的點(diǎn)或者C(αmp)∈C(S)，與S是算法2的解矛盾。

若αmp對(duì)應(yīng)于S中1個(gè)頂點(diǎn)，當(dāng)αmp與A中某些頂點(diǎn)對(duì)應(yīng)于相同顏色的頂點(diǎn)，同理可得，則至少有一個(gè)與αmp顏色相同的頂點(diǎn)所在的二部圖分支，使得這個(gè)二部圖分支中其它頂點(diǎn)的顏色已對(duì)應(yīng)于A中某些頂點(diǎn)，即這些頂點(diǎn)所著顏色已被選入S。故由算法2得出C(αmp)∈(S)，與S是算法2的解矛盾。若αmp與A中所有頂點(diǎn)所對(duì)應(yīng)顏色都不同，而C(αmp)這一顏色恰在原圖中出現(xiàn)3次，則此時(shí)必至少有一個(gè)C(αmp)所在的二部圖分支中所包含顏色均不在其中，與S是算法2的解矛盾。

若αmp對(duì)應(yīng)于S中2個(gè)頂點(diǎn)，則C(αmp)所在原二部圖分支中，要么恰有一個(gè)顏色是C(αmp)的頂點(diǎn)所在二部圖分支，使得算法2運(yùn)行到這一個(gè)二部圖分支時(shí)，包含了此時(shí)C(S)中兩種尚無(wú)對(duì)應(yīng)的不同顏色的頂點(diǎn)。要么只有兩種顏色是C(αmp)的頂點(diǎn)所在的二部圖分支在當(dāng)前算法2運(yùn)行到這兩個(gè)二部圖分支時(shí)，各對(duì)應(yīng)了此時(shí)C(S)中不同顏色所在的頂點(diǎn)。若αmp與A中某些頂點(diǎn)所對(duì)應(yīng)的顏色相同，同理可得，則必至少有一個(gè)αmp或與αmp顏色相同的頂點(diǎn)所在的二部圖分支中只有已選入S中的點(diǎn)，與S是算法2的解矛盾。當(dāng)αmp與A中其它任意一個(gè)頂點(diǎn)所對(duì)應(yīng)頂點(diǎn)顏色都不相同時(shí)，同理可得，與S是算法2的解矛盾。即f:A→S且A中每個(gè)頂點(diǎn)在對(duì)應(yīng)關(guān)系f下至少映S中3個(gè)頂點(diǎn)，3|A|≤|S|≤|S*|。

圖2 算法2的緊例

3 結(jié)束語(yǔ)