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

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

2、的算法，以多項(xiàng)式的時(shí)間驗(yàn)證 V' k，及對(duì)所有的 (u, v) E，是否有u V'或v V'。因此頂點(diǎn)覆蓋冋題是一個(gè) NP冋題。完全性的證明：我們已知團(tuán)集(CLIQUE問題是一個(gè)NP完全問題，若團(tuán)集問題歸約于頂點(diǎn) 覆蓋問題，即CLIQUE VERTEX COVER，則頂點(diǎn)覆蓋問題就是一個(gè) NP完全 問題。我們可以利用無向圖的補(bǔ)圖來說明這個(gè)問題。若向圖 G (V,E)，則G的補(bǔ) 圖G (V, E)，其中E (u,v)|(u,v) E。例如，圖1(b)是圖1(a)的補(bǔ)圖。在圖 1(a)中有一個(gè)大小為3的團(tuán)集u,v, y，在圖1(b)中，則有一個(gè)大小為2的頂點(diǎn) 覆蓋v,w。顯

3、然可以在多項(xiàng)式時(shí)間里構(gòu)造圖 G的補(bǔ)圖G。因此，只要證明圖G (V,E)有一個(gè)大小為|V | k的團(tuán)集，當(dāng)且僅當(dāng)它的補(bǔ)圖 G有一個(gè)大小為k的 頂點(diǎn)覆蓋。圖1無向圖及補(bǔ)圖必要性：如果G中有一個(gè)大小為|V| k的團(tuán)集，則它具有一個(gè)大小為|V | k個(gè)頂點(diǎn)的完全子圖，令這|V | k個(gè)頂點(diǎn)集合為V'。令(u,v)是E中的任意一條邊, 則(u,v) E。所以(u,v)中必有一個(gè)頂點(diǎn)不屬于V'，即(u,v)中必有一個(gè)頂點(diǎn)屬于V V'，也就是邊(u,v)被V V'覆蓋。因?yàn)?u,v)是E中的任意一條邊，因此，E中的邊都被覆蓋，所以，V V'是G的一個(gè)大小為|V V&#

4、39;| k的頂點(diǎn)覆蓋充分性：如果G中有一個(gè)大小為k的頂點(diǎn)覆蓋，令這個(gè)頂點(diǎn)覆蓋為V' , (u,v)是E中的任意一條邊，則u和v至少有一個(gè)頂點(diǎn)屬于V'。因此，對(duì)于任意的頂點(diǎn) u和v,若u V V'并且v V V'，則必然有(u,v) E，即V V'是G中一個(gè)大 小為的 |V | k 的團(tuán)集。綜上所述，團(tuán)集(CLIQUE問題歸約于頂點(diǎn)覆蓋(VERTE；COVER問題，即 CLIQUE poiyVERTEX COVER。所以，頂點(diǎn)覆蓋問題是一個(gè) NP完全問題。頂點(diǎn)覆蓋優(yōu)化問題的近似算法上面已經(jīng)證得，頂點(diǎn)覆蓋問題是一個(gè) NP完全問題，因此，沒有一個(gè)確定性的多項(xiàng)

5、式時(shí)間算法來解它。 頂點(diǎn)覆蓋的優(yōu)化問題是找出圖中的最小頂點(diǎn)覆蓋。 為了用近似算法解決這個(gè)問題，假設(shè)頂點(diǎn)用 存放頂點(diǎn)與頂點(diǎn)之間的關(guān)聯(lián)邊。struct adj _ list /*int v_num;/*struct adj _list next;0,1,.,n 1編號(hào)，并用下面的鄰接表來鄰接表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu) */ 鄰接結(jié)點(diǎn)的編號(hào) */*下一個(gè)鄰接頂點(diǎn) */; typedef struct adj _list NODE;NODEVn;/*圖G的鄰接表頭結(jié)點(diǎn)*/則頂點(diǎn)覆蓋問題的近似算法的求解步驟可以敘述如下：1) 頂點(diǎn)的初始編號(hào) u 0；2) 如果頂點(diǎn) u 存在關(guān)聯(lián)邊，轉(zhuǎn)到步驟( 3)，否則，轉(zhuǎn)到步驟

6、( 5)；(3) 令關(guān)聯(lián)邊為(u,v)，把頂點(diǎn)u和頂點(diǎn)v登記到頂點(diǎn)覆蓋C中；(4) 刪去與頂點(diǎn)u和頂點(diǎn)v關(guān)聯(lián)的所有邊；(5) u u 1，如果u n，轉(zhuǎn)到步驟(2)，否則，算法結(jié)束。 算法的實(shí)現(xiàn)過程敘述如下： 算法名稱：頂點(diǎn)覆蓋優(yōu)化問題的近似算法；輸 入：無向圖G的鄰接表V，頂點(diǎn)個(gè)數(shù)為n ；2.3.NODEp,p1;4.int u,v;5.m 0;6.for(u0;u n;u)7.pVu next;8.if (p! NULL )/*如果 u 存在關(guān)聯(lián)邊 */9.Cm u;Cm 1v p v_num;m 2;10.while ( p! NULL )/*則選取邊(u,v)的頂點(diǎn)*/11.delet

7、e _e( pv_num,u);/* 刪去與 u 有關(guān)聯(lián)的所有邊 */12.p p next;輸 出：圖G的頂點(diǎn)覆蓋C，C中的頂點(diǎn)個(gè)數(shù)為m1.vertex _ cov er _ app( NODE V, intn,int C, int & m)13. 14. Vu next NULL;15. pl Vv next;16. while(p!NULL )/*刪去與v關(guān)聯(lián)的所有邊*/17. delete_e( p v_num,v);18. p p n ext;19. 20. Vv nextNULL;21. 22. 算法說明：這個(gè)算法用數(shù)組C來存放頂點(diǎn)覆蓋中的各個(gè)頂點(diǎn)，用變量m來存放數(shù)組C中

8、的頂點(diǎn)個(gè)數(shù)。開始時(shí)，把變量 m初始化為0,把頂點(diǎn)的編號(hào)u初始化為0。然后 從頂點(diǎn)u開始，如果頂點(diǎn)u存在著關(guān)聯(lián)邊，就把頂點(diǎn)u及其一個(gè)鄰接點(diǎn)v登記到 數(shù)組C中。并刪去與頂點(diǎn)u和頂點(diǎn)v的所有關(guān)聯(lián)邊。其中，第 11行的函數(shù)delete_e( p v_num,u)用來刪去頂點(diǎn)p v_num與頂點(diǎn)u相鄰接的登記項(xiàng)；第 17行函數(shù)delete_e(p v_num, v)用來刪去頂點(diǎn)p v_num與頂點(diǎn)v相鄰接的 登記項(xiàng)；第14行和20行分別把頂點(diǎn)u和頂點(diǎn)v的鄰接表頭結(jié)點(diǎn)的鏈指針置為空， 從而分別刪去這兩個(gè)頂點(diǎn)與其他頂點(diǎn)相鄰接的所有登記項(xiàng)。經(jīng)過這樣的處理，就把頂點(diǎn)u及頂點(diǎn)v的所有關(guān)聯(lián)邊刪去。這種處理一直進(jìn)行，

9、直到圖G中的所有邊都被刪去為止。最后，在數(shù)組C中存放著圖G的頂點(diǎn)覆蓋中的各個(gè)頂點(diǎn)編號(hào)，變 量m表示數(shù)組C中登記的頂點(diǎn)個(gè)數(shù)。圖2表示了這種處理過程。圖2(a)表示圖G的初始狀態(tài)；圖2(b)表示選擇 邊(a,b)，把關(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);這個(gè)過程一 直進(jìn)行，圖2(g)表示最后得到的結(jié)果。整個(gè)處理過程共選擇了 6條邊上的12個(gè) 頂點(diǎn)，作為圖的一個(gè)頂點(diǎn)覆蓋，他們是 a,b,c,d,e, f, g,h, j ,k,l ,m?？梢钥吹?，它 不是圖G的最小的頂點(diǎn)覆蓋。圖2(h)表示圖G的一個(gè)最小的頂點(diǎn)覆蓋，它有 7 個(gè)頂點(diǎn)，分別是a,c, f ,h,i ,k,l。(b)s q (Ikm(e)(f)(g)(h)圖2算法處理過程圖算法近似性能估計(jì)：下面來估計(jì)這個(gè)算法的近似性能。假定算法所選取的邊集為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條邊時(shí)， 第2條邊與第1條邊將不會(huì)具有公共頂點(diǎn)，則邊集中的所有的邊都不會(huì)具有公共 頂點(diǎn)。這樣放進(jìn)數(shù)組