顶点覆盖问题的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顶点的覆盖，则可以构造一个确定性的算法，以多项式的时间验证V'?k，及对所有的
(u,v)?E，是否有u?V'或v?V'。因此顶点覆盖问题是一个NP问题。
完全性的证明：
我们已知团集（CLIQUE）问题是一个NP完全问题，若团集问题归约于顶点覆盖问题，即CLIQUE?polyVERTEXCOVER，则顶点覆盖问题就是一个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}。显然可以在多项式时间里构造图G的补图G。因此，只要证明图
G?(V,E)有一个大小为|V|?k的团集，当且仅当它的补图G有一个大小为k的顶点覆盖。
uvuv?????wwxyxy(a) (b)
图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'|?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）问题归约于顶点覆盖（VERTEX COVER）问题，即CLIQUE?polyVERTEXCOVER。所以，顶点覆盖问题是一个NP完全问题。
顶点覆盖优化问题的近似算法
上面已经证得，顶点覆盖问题是一个NP完全问题，因此，没有一个确定性的多项式时间算法来解它。顶点覆盖的优化问题是找出图中的最小顶点覆盖。为了用近似算法解决这个问题，假设顶点用0,1,...,n?1编号，并用下面的邻接表来存放顶点与顶点之间的关联边。
struct adj_list{ /*邻接表结点的数据结构*/ intv_num; /*邻接结点的编号*/ struct adj_list?next; /*下一个邻接顶点*/ };
typedef struct adj_list NODE;
NODE ?V[n]; /*图G的邻接表头结点*/ 则顶点覆盖问题的近似算法的求解步骤可以叙述如下： （1）顶点的初始编号u?0；
（2）如果顶点u存在关联边，转到步骤（3），否则，转到步骤（5）； （3）令关联边为(u,v)，把顶点u和顶点v登记到顶点覆盖C中； （4）删去与顶点u和顶点v关联的所有边；
（5）u?u?1，如果u?n，转到步骤（2），否则，算法结束。 算法的实现过程叙述如下：
算法名称：顶点覆盖优化问题的近似算法；
输 入：无向图G的邻接表V[]，顶点个数为n；
输 出：图G的顶点覆盖C[]，C中的顶点个数为m。 1.vertex_cover_app(NODE?V[],intn,intC[],int&m) 2.{
3. NODE?p,p1; 4. intu,v; 5. m?0;
6. for(u?0;u?n;u??){ 7. p?V[u]?next;
8. if(p!?NULL){ /*如果u存在关联边*/ 9. C[m]?u;C[m?1]?v?p?v_num;m?2;
10. while(p!?NULL){ /*则选取边(u,v)的顶点*/ 11. delete_e(p?v_num,u); /*删去与u有关联的所有边*/ 12. p?p?next;
???13. }
14. V[u]?next?NULL; 15. p1?V[v]?next;
16. while(p!?NULL){ /*删去与v关联的所有边*/ 17. delete_e(p?v_num,v); 18. p?p?next; 19. }
20. V[v]?next?NULL; 21. } 22.}
算法说明：
这个算法用数组C来存放顶点覆盖中的各个顶点，用变量m来存放数组C中的顶点个数。开始时，把变量m初始化为0，把顶点的编号u初始化为0。然后从顶点u开始，如果顶点u存在着关联边，就把顶点u及其一个邻接点v登记到数组C中。并删去与顶点u和顶点v的所有关联边。其中，第11行的函数delete_e(p?v_num,u)用来删去顶点p?v_num与顶点u相邻接的登记项；第
,v)用来删去顶点p?v_num与顶点v相邻接的17行函数delete_e(p?v_num登记项；第14行和20行分别把顶点u和顶点v的邻接表头结点的链指针置为空，从而分别删去这两个顶点与其他顶点相邻接的所有登记项。经过这样的处理，就把顶点u及顶点v的所有关联边删去。这种处理一直进行，直到图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。
abcdefabcdefghighijklmjklm
(a) (b)