頂點(diǎn)覆蓋問題的NP完全證明和近似算法求解

1、頂點(diǎn)覆蓋問題的NP完全證明和頂點(diǎn)覆蓋優(yōu)化問題的近似算法頂點(diǎn)覆蓋(VERTEXCOVER給定一個無向圖G=(V,E)和一個正整數(shù)k,若存在V'EV,V'=k,使得對任意的(u,v)wE,都有uwV'或vwV',則稱V'為圖G的一個大小為k的頂點(diǎn)覆蓋。頂點(diǎn)覆蓋問題的描述判定問題：VERTEXCOVER輸入：無向圖G=(V,E),正整數(shù)k問題：G中是否存在一個大小為k的頂點(diǎn)覆蓋，這是一個NP完全問題頂點(diǎn)覆蓋的NP完全性證明NP性的證明：對給定的無向圖G=(V,E),若頂點(diǎn)VRV是圖G的一個大小為k頂點(diǎn)的覆蓋，則可以構(gòu)造一個確定性的算法，以多項式的時間驗(yàn)證V&#

2、39;=k,及對所有的(u,v)WE,是否有口力或丫守。因此頂點(diǎn)覆蓋問題是一個NP問題。完全性的證明：我們已知團(tuán)集(CLIQUE問題是一個NP完全問題，若團(tuán)集問題歸約于頂點(diǎn)覆蓋問題，即CLIQUEapolyVERTEXCOVER,則頂點(diǎn)覆蓋問題就是一個NP完全p5y問題。我們可以利用無向圖的補(bǔ)圖來說明這個問題。若向圖G=(V,E),則G的補(bǔ)圖G=(V,E),其中E=(u,v)|(u,v)正E。例如，圖1(b)是圖1(a)的補(bǔ)圖。在圖1(a)中有一個大小為3的團(tuán)集u,v,y,在圖1(b)中，則有一個大小為2的頂點(diǎn)覆蓋v,wo顯然可以在多項式時間里構(gòu)造圖G的補(bǔ)圖Go因此，只要證明圖G=(V,E)有

3、一個大小為|V|-k的團(tuán)集，當(dāng)且僅當(dāng)它的補(bǔ)圖G有一個大小為k的頂點(diǎn)覆蓋。圖1無向圖及補(bǔ)圖必要性：如果G中有一個大小為|V|-k的團(tuán)集，則它具有一個大小為|V|-k個頂點(diǎn)的完全子圖，令這|V|*個頂點(diǎn)集合為V'o令(u,v)是E中的任意一條邊，則(u,v)里E。所以(u,v)中必有一個頂點(diǎn)不屬于V',即(u,v)中必有一個頂點(diǎn)屬于V-V,也就是邊(u,v)被V-V'覆蓋。因?yàn)?u,v)是E中的任意一條邊，因此，E中的邊都被覆蓋，所以，VV'是G的一個大小為|VV'|=k的頂點(diǎn)覆蓋。充分性：如果G中有一個大小為k的頂點(diǎn)覆蓋，令這個頂點(diǎn)覆蓋為V',（u

4、,v）是E中的任意一條邊，則u和v至少有一個頂點(diǎn)屬于V'o因此，對于任意的頂點(diǎn)u和v,若uWVV'并且VWV-V',則必然有（u,v）wE,即V-V'是G中一個大小為的|V|k的團(tuán)集。綜上所述，團(tuán)集（CLIQUE問題歸約于頂點(diǎn)覆蓋（VERTEKOVEJR問題，即CLIQUEapoiyVERTEXCOVER0所以，頂點(diǎn)覆蓋問題是一個NP完全問題。頂點(diǎn)覆蓋優(yōu)化問題的近似算法上面已經(jīng)證得，頂點(diǎn)覆蓋問題是一個NP完全問題，因此，沒有一個確定性的多項式時間算法來解它。頂點(diǎn)覆蓋的優(yōu)化問題是找出圖中的最小頂點(diǎn)覆蓋。為了用近似算法解決這個問題，假設(shè)頂點(diǎn)用0,1,n1編號，并用下

5、面的鄰接表來/*/*/*鄰接表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)*/鄰接結(jié)點(diǎn)的編號*/下一個鄰接頂點(diǎn)*/存放頂點(diǎn)與頂點(diǎn)之間的關(guān)聯(lián)邊。structadj_listintvnum;structadj_list*next;typedefstructadj_listNODE;NODEVn;/*圖G的鄰接表頭結(jié)點(diǎn)*/則頂點(diǎn)覆蓋問題的近似算法的求解步驟可以敘述如下:(1)(2)(3)(4)(5)頂點(diǎn)的初始編號u=0；如果頂點(diǎn)u存在關(guān)聯(lián)邊，轉(zhuǎn)到步驟（3）,否則，轉(zhuǎn)到步驟（5）;令關(guān)聯(lián)邊為（u,v）,把頂點(diǎn)u和頂點(diǎn)v登記到頂點(diǎn)覆蓋C中；刪去與頂點(diǎn)u和頂點(diǎn)v關(guān)聯(lián)的所有邊；u=u+1,如果u<n,轉(zhuǎn)到步驟（2）,否則，算法結(jié)束

6、。算法的實(shí)現(xiàn)過程敘述如下：算法名稱：頂點(diǎn)覆蓋優(yōu)化問題的近似算法；輸入：無向圖G的鄰接表V口，頂點(diǎn)個數(shù)為n；輸出：圖G的頂點(diǎn)覆蓋C口，C中的頂點(diǎn)個數(shù)為m1. .vertex_cover_app(NODE*V,intn,intC,int&m)2. 3. NODEp,p1;4. intu,v;5. m=0;6. for(u=0;u：n;u一，兒7. p=Vunext;8. if(p!=NULL)/*如果u存在關(guān)聯(lián)邊*/9. Cm=u;Cm+1=v=ptv_num;m+2;10. while(p!=NULL)/*則選取邊(u,v)的頂點(diǎn)*/11. delete_e(pTv_num,u);/*刪

7、去與u有關(guān)聯(lián)的所有邊*/12. p=p>next;13. 14. Vunext=NULL;15. pl=Vvnext;16. while(p!=NULL)/*刪去與v關(guān)聯(lián)的所有邊*/17. delete_e(p-»v_num,v);18. p=pnext;19. 20. Vvnext-NULL;21. 22. 算法說明：這個算法用數(shù)組C來存放頂點(diǎn)覆蓋中的各個頂點(diǎn)，用變量m來存放數(shù)組C中的頂點(diǎn)個數(shù)。開始時，把變量m初始化為0,把頂點(diǎn)的編號u初始化為00然后從頂點(diǎn)u開始，如果頂點(diǎn)u存在著關(guān)聯(lián)邊，就把頂點(diǎn)u及其一個鄰接點(diǎn)v登記到數(shù)組C中。并刪去與頂點(diǎn)u和頂點(diǎn)v的所有關(guān)聯(lián)邊。其中，第1

8、1行的函數(shù)delete_e(ptv_num,u)用來刪去頂點(diǎn)pTv_num與頂點(diǎn)u相鄰接的登記項；第17行函數(shù)delete_e(p-»v_num,v)用來刪去頂點(diǎn)pTv_num與頂點(diǎn)v相鄰接的登記項；第14行和20行分別把頂點(diǎn)u和頂點(diǎn)v的鄰接表頭結(jié)點(diǎn)的鏈指針置為空，從而分別刪去這兩個頂點(diǎn)與其他頂點(diǎn)相鄰接的所有登記項。經(jīng)過這樣的處理，就把頂點(diǎn)u及頂點(diǎn)v的所有關(guān)聯(lián)邊刪去。這種處理一直進(jìn)行，直到圖G中的所有邊都被刪去為止。最后，在數(shù)組C中存放著圖G的頂點(diǎn)覆蓋中的各個頂點(diǎn)編號，變量m表示數(shù)組C中登記的頂點(diǎn)個數(shù)。圖2表示了這種處理過程。圖2(a)表示圖G的初始狀態(tài)；圖2(b)表示選擇邊(a,b

9、),把關(guān)聯(lián)邊的頂點(diǎn)a及b放進(jìn)數(shù)組C中，并刪去頂點(diǎn)a及頂點(diǎn)b相關(guān)聯(lián)的所有邊，這里刪去邊(a,b),(a,g)及(a,j);圖2(c)表示選擇邊(c,d),把關(guān)聯(lián)該邊的頂點(diǎn)c和頂點(diǎn)d放進(jìn)數(shù)組C中，并刪去邊(c,d),(c,g)及(d,i)；這個過程一直進(jìn)行，圖2(g)表示最后得到的結(jié)果。整個處理過程共選擇了6條邊上的12個頂點(diǎn)，作為圖的一個頂點(diǎn)覆蓋，他們是a,b,c,d,e,f,g,h,j,k,l,m?？梢钥吹?，它不是圖G的最小的頂點(diǎn)覆蓋。圖2(h)表示圖G的一個最小的頂點(diǎn)覆蓋，它有7個頂點(diǎn)，分別是a,c,f,h,i,k,lo(a)(b)(g)(h)圖2算法處理過程圖算法近似性能估計：下面來估計這個算法的近似性能。假定算法所選取的邊集為E',則這些邊的關(guān)聯(lián)邊頂點(diǎn)被作為頂點(diǎn)覆蓋中的頂點(diǎn)，放進(jìn)數(shù)組C中。因?yàn)橐坏┻x擇了某條邊，例如邊（a,b）,則與頂點(diǎn)a和頂點(diǎn)b相關(guān)聯(lián)的所有邊均刪去。再次選擇第2條邊時，第2條邊與第1條邊將不會具有公共頂點(diǎn)，則邊集中的所有的邊都不會具有公共頂點(diǎn)。這樣放進(jìn)數(shù)組中的頂