顶点覆盖问题的NP完全证明和近似算法求解

1、顶点覆盖问题的NP完全证明和顶点覆盖优化问题的近似算法顶点覆盖(VERTEX COVER给定一个无向图G (V,E)和一个正整数k ,若存在V' V, V' k ,使得对 任意的(u,v) E，都有u V'或v V'，则称V'为图G的一个大小为k的顶点覆 盖。顶点覆盖问题的描述判定问题：VERTEX COVER输 入：无向图G (V,E)，正整数k问 题：G中是否存在一个大小为k的顶点覆盖，这是一个NP完全问题 顶点覆盖的NP完全性证明NP性的证明：对给定的无向图G (V,E)，若顶点V' V是图G的一个大小为k顶点的覆 盖，则可以构造一个确定性

2、的算法，以多项式的时间验证 V' k，及对所有的 (u, v) E，是否有u V'或v V'。因此顶点覆盖冋题是一个 NP冋题。完全性的证明：我们已知团集(CLIQUE问题是一个NP完全问题，若团集问题归约于顶点 覆盖问题，即CLIQUE VERTEX COVER，则顶点覆盖问题就是一个 NP完全 问题。我们可以利用无向图的补图来说明这个问题。若向图 G (V,E)，则G的补 图G (V, E)，其中E (u,v)|(u,v) E。例如，图1(b)是图1(a)的补图。在图 1(a)中有一个大小为3的团集u,v, y，在图1(b)中，则有一个大小为2的顶点 覆盖v,w。显

3、然可以在多项式时间里构造图 G的补图G。因此，只要证明图G (V,E)有一个大小为|V | k的团集，当且仅当它的补图 G有一个大小为k的 顶点覆盖。图1无向图及补图必要性：如果G中有一个大小为|V| k的团集，则它具有一个大小为|V | k个顶点的完全子图，令这|V | k个顶点集合为V'。令(u,v)是E中的任意一条边, 则(u,v) E。所以(u,v)中必有一个顶点不属于V'，即(u,v)中必有一个顶点属于V V'，也就是边(u,v)被V V'覆盖。因为(u,v)是E中的任意一条边，因此，E中的边都被覆盖，所以，V V'是G的一个大小为|V V&#

4、39;| k的顶点覆盖充分性：如果G中有一个大小为k的顶点覆盖，令这个顶点覆盖为V' , (u,v)是E中的任意一条边，则u和v至少有一个顶点属于V'。因此，对于任意的顶点 u和v,若u V V'并且v V V'，则必然有(u,v) E，即V V'是G中一个大 小为的 |V | k 的团集。综上所述，团集(CLIQUE问题归约于顶点覆盖(VERTE；COVER问题，即 CLIQUE poiyVERTEX COVER。所以，顶点覆盖问题是一个 NP完全问题。顶点覆盖优化问题的近似算法上面已经证得，顶点覆盖问题是一个 NP完全问题，因此，没有一个确定性的多项

5、式时间算法来解它。 顶点覆盖的优化问题是找出图中的最小顶点覆盖。 为了用近似算法解决这个问题，假设顶点用 存放顶点与顶点之间的关联边。struct adj _ list /*int v_num;/*struct adj _list next;0,1,.,n 1编号，并用下面的邻接表来邻接表结点的数据结构 */ 邻接结点的编号 */*下一个邻接顶点 */; typedef struct adj _list NODE;NODEVn;/*图G的邻接表头结点*/则顶点覆盖问题的近似算法的求解步骤可以叙述如下：1) 顶点的初始编号 u 0；2) 如果顶点 u 存在关联边，转到步骤( 3)，否则，转到步骤

6、( 5)；(3) 令关联边为(u,v)，把顶点u和顶点v登记到顶点覆盖C中；(4) 删去与顶点u和顶点v关联的所有边；(5) u u 1，如果u n，转到步骤(2)，否则，算法结束。 算法的实现过程叙述如下： 算法名称：顶点覆盖优化问题的近似算法；输 入：无向图G的邻接表V，顶点个数为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 存在关联边 */9.Cm u;Cm 1v p v_num;m 2;10.while ( p! NULL )/*则选取边(u,v)的顶点*/11.delet

7、e _e( pv_num,u);/* 删去与 u 有关联的所有边 */12.p p next;输 出：图G的顶点覆盖C，C中的顶点个数为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关联的所有边*/17. delete_e( p v_num,v);18. p p n ext;19. 20. Vv nextNULL;21. 22. 算法说明：这个算法用数组C来存放顶点覆盖中的各个顶点，用变量m来存放数组C中

8、的顶点个数。开始时，把变量 m初始化为0,把顶点的编号u初始化为0。然后 从顶点u开始，如果顶点u存在着关联边，就把顶点u及其一个邻接点v登记到 数组C中。并删去与顶点u和顶点v的所有关联边。其中，第 11行的函数delete_e( p v_num,u)用来删去顶点p v_num与顶点u相邻接的登记项；第 17行函数delete_e(p v_num, v)用来删去顶点p v_num与顶点v相邻接的 登记项；第14行和20行分别把顶点u和顶点v的邻接表头结点的链指针置为空， 从而分别删去这两个顶点与其他顶点相邻接的所有登记项。经过这样的处理，就把顶点u及顶点v的所有关联边删去。这种处理一直进行，

9、直到图G中的所有边都被删去为止。最后，在数组C中存放着图G的顶点覆盖中的各个顶点编号，变 量m表示数组C中登记的顶点个数。图2表示了这种处理过程。图2(a)表示图G的初始状态；图2(b)表示选择 边(a,b)，把关联边的顶点a及b放进数组C中，并删去顶点a及顶点b相关联的 所有边，这里删去边(a,b)，(a,g)及(a, j)；图2(c)表示选择边(c,d)，把关联该 边的顶点c和顶点d放进数组C中，并删去边(c,d)， (c,g)及(d, i);这个过程一 直进行，图2(g)表示最后得到的结果。整个处理过程共选择了 6条边上的12个 顶点，作为图的一个顶点覆盖，他们是 a,b,c,d,e, f, g,h, j ,k,l ,m。可以看到，它 不是图G的最小的顶点覆盖。图2(h)表示图G的一个最小的顶点覆盖，它有 7 个顶点，分别是a,c, f ,h,i ,k,l。(b)s q (Ikm(e)(f)(g)(h)图2算法处理过程图算法近似性能估计：下面来估计这个算法的近似性能。假定算法所选取的边集为E'，则这些边 的关联边顶点被作为顶点覆盖中的顶点，放进数组C中。因为一旦选择了某条边， 例如边（a,b），则与顶点a和顶点b相关联的所有边均删去。再次选择第2条边时， 第2条边与第1条边将不会具有公共顶点，则边集中的所有的边都不会具有公共 顶点。这样放进数组