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

顶点覆盖问题的NP完全证明和顶点覆盖优化问题的近似算法顶点覆盖（VERTEXCOVER）给定一个无向图),(EVG和一个正整数k，若存在VV'，kV'，使得对任意的Evu),(，都有'Vu或'Vv，则称'V为图G的一个大小为k的顶点覆盖。顶点覆盖问题的描述判定问题：VERTEXCOVER输入：无向图),(EVG，正整数k问题：G中是否存在一个大小为k的顶点覆盖，这是一个NP完全问题顶点覆盖的NP完全性证明NP性的证明：对给定的无向图),(EVG，若顶点VV'是图G的一个大小为k顶点的覆盖，则可以构造一个确定性的算法，以多项式的时间验证kV'，及对所有的Evu),(，是否有'Vu或'Vv。因此顶点覆盖问题是一个NP问题。完全性的证明：我们已知团集（CLIQUE）问题是一个NP完全问题，若团集问题归约于顶点覆盖问题，即VERTEXCLIQUEpolyCOVER，则顶点覆盖问题就是一个NP完全问题。我们可以利用无向图的补图来说明这个问题。若向图),(EVG，则G的补图),(EVG，其中}),(|),{(EvuvuE。例如，图1(b)是图1(a)的补图。在图1(a)中有一个大小为3的团集},,{yvu，在图1(b)中，则有一个大小为2的顶点覆盖},{wv。显然可以在多项式时间里构造图G的补图G。因此，只要证明图),(EVG有一个大小为kV||的团集，当且仅当它的补图G有一个大小为k的顶点覆盖。uvwyxuvwyx(a)(b)图1无向图及补图必要性：如果G中有一个大小为kV||的团集，则它具有一个大小为kV||个顶点的完全子图，令这kV||个顶点集合为'V。令),(vu是E中的任意一条边，则Evu),(。所以),(vu中必有一个顶点不属于'V，即),(vu中必有一个顶点属于'VV，也就是边),(vu被'VV覆盖。因为),(vu是E中的任意一条边，因此，E中的边都被覆盖，所以，'VV是G的一个大小为kVV|'|的顶点覆盖。充分性：如果G中有一个大小为k的顶点覆盖，令这个顶点覆盖为'V，),(vu是E中的任意一条边，则u和v至少有一个顶点属于'V。因此，对于任意的顶点u和v，若'VVu并且'VVv，则必然有Evu),(，即'VV是G中一个大小为的kV||的团集。综上所述，团集（CLIQUE）问题归约于顶点覆盖（VERTEXCOVER）问题，即VERTEXCLIQUEpolyCOVER。所以，顶点覆盖问题是一个NP完全问题。顶点覆盖优化问题的近似算法上面已经证得，顶点覆盖问题是一个NP完全问题，因此，没有一个确定性的多项式时间算法来解它。顶点覆盖的优化问题是找出图中的最小顶点覆盖。为了用近似算法解决这个问题，假设顶点用1,...,1,0n编号，并用下面的邻接表来存放顶点与顶点之间的关联边。struct{_listadj/*邻接表结点的数据结构*/int;_numv/*邻接结点的编号*/structlistadj_;next/*下一个邻接顶点*/};typedefstructlistadj_;NODENODE];[nV/*图G的邻接表头结点*/则顶点覆盖问题的近似算法的求解步骤可以叙述如下：（1）顶点的初始编号0u；（2）如果顶点u存在关联边，转到步骤（3），否则，转到步骤（5）；（3）令关联边为),(vu，把顶点u和顶点v登记到顶点覆盖C中；（4）删去与顶点u和顶点v关联的所有边；（5）1uu，如果nu，转到步骤（2），否则，算法结束。算法的实现过程叙述如下：算法名称：顶点覆盖优化问题的近似算法；输入：无向图G的邻接表[]V，顶点个数为n；输出：图G的顶点覆盖[]C，C中的顶点个数为m。NODEappervertex(_cov_.1int[],Vint,nint[],C)&m.{2.3;1,ppNODE.4;,intvu.5;0m.6){;;0(unuufor.7;][nextuVp.8){!(NULLpif/*如果u存在关联边*/.9;2;_]1[;][mnumvpvmCumC.10){!(NULLpwhile/*则选取边),(vu的顶点*/.11);,_(_unumvpedelete/*删去与u有关联的所有边*/.12;nextpp.13}.14;][NULLnextuV.15;][1nextvVp.16){!(NULLpwhile/*删去与v关联的所有边*/.17);,_(_vnumvpedelete.18;nextpp.19}.20;][NULLnextvV.21}.22}算法说明：这个算法用数组C来存放顶点覆盖中的各个顶点，用变量m来存放数组C中的顶点个数。开始时，把变量m初始化为0，把顶点的编号u初始化为0。然后从顶点u开始，如果顶点u存在着关联边，就把顶点u及其一个邻接点v登记到数组C中。并删去与顶点u和顶点v的所有关联边。其中，第11行的函数),_(_unumvpedelete用来删去顶点numvp_与顶点u相邻接的登记项；第17行函数),_(_vnumvpedelete用来删去顶点numvp_与顶点v相邻接的登记项；第14行和20行分别把顶点u和顶点v的邻接表头结点的链指针置为空，从而分别删去这两个顶点与其他顶点相邻接的所有登记项。经过这样的处理，就把顶点u及顶点v的所有关联边删去。这种处理一直进行，直到图G中的所有边都被删去为止。最后，在数组C中存放着图G的顶点覆盖中的各个顶点编号，变量m表示数组C中登记的顶点个数。图2表示了这种处理过程。图2(a)表示图G的初始状态；图2(b)表示选择边),(ba，把关联边的顶点a及b放进数组C中，并删去顶点a及顶点b相关联的所有边，这里删去边),(ba，),(ga及),(ja；图2(c)表示选择边),(dc，把关联该边的顶点c和顶点d放进数组C中，并删去边),(dc，),(gc及),(id；这个过程一直进行，图2(g)表示最后得到的结果。整个处理过程共选择了6条边上的12个顶点，作为图的一个顶点覆盖，他们是mlkjhgfedcba,,,,,,,,,,,。可以看到，它不是图G的最小的顶点覆盖。图2(h)表示图G的一个最小的顶点覆盖，它有7个顶点，分别是lkihfca,,,,,,。abgkjhidcefmlabgkjhidcefml(a)(b)abgkjhidcefmlabgkjhidcefml(c)(d)abgkjhidcefmlabgkjhidcefml(e)(f)abgkjhidcefmlabgkjhidcefml(g)(h)图2算法处理过程图算法近似性能估计：下面来估计这个算法的近似性能。假定算法所选取的边集为'E，则这些边的关联边顶点被作为顶点覆盖中的顶点，放进数组C中。因为一旦选择了某条边，例如边),(ba，则与顶点a和顶点b相关联的所有边均删去。再次选择第2条边时，第2条边与第1条边将不会具有公共顶点，则边集中的所有的边都不会具有公共顶点。这样放进数组中的顶点个数为|'|2E，即|'|2||EC。另一方面，图G的任何一个顶点覆盖，至少包含'E中各条边中的一个顶点。若图G的最小顶点覆盖为*C，则有|'||*|EC。所以有：2|'||'|2|*|||EECC由此可以得到，这个算法的性能比率小于或等于2。