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

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

顶点覆盖（VERTEX COVER）
给定一个无向图和一个正整数，若存在，，使得对任意的，都有或，则称为图的一个大小为的顶点覆盖。
顶点覆盖问题的描述
判定问题：VERTEX COVER
输 入：无向图，正整数
问 题：中是否存在一个大小为的顶点覆盖，这是一个NP完全问题
顶点覆盖的NP完全性证明
NP性的证明：
对给定的无向图，若顶点是图的一个大小为顶点的覆盖，则可以构造一个确定性的算法，以多项式的时间验证，及对所有的，是否有或。因此顶点覆盖问题是一个NP问题。
完全性的证明：
我们已知团集（CLIQUE）问题是一个NP完全问题，若团集问题归约于顶点覆盖问题，即，则顶点覆盖问题就是一个NP完全问题。
我们可以利用无向图的补图来说明这个问题。若向图，则的补图，其中。例如，图1(b)是图1(a)的补图。在图1(a)中有一个大小为3的团集，在图1(b)中，则有一个大小为2的顶点覆盖。显然可以在多项式时间里构造图的补图。因此，只要证明图有一个大小为的团集，当且仅当它的补图有一个大小为的顶点覆盖。

(a) (b)
图1无向图及补图
必要性：如果中有一个大小为的团集，则它具有一个大小为个顶点的完全子图，令这个顶点集合为。令是中的任意一条边，则。所以中必有一个顶点不属于，即中必有一个顶点属于，也就是边被覆盖。因为是中的任意一条边，因此，中的边都被覆盖，所以，是的一个大小为的顶点覆盖。
充分性：如果中有一个大小为的顶点覆盖，令这个顶点覆盖为，是中的任意一条边，则和至少有一个顶点属于。因此，对于任意的顶点和，若并且，则必然有，即是中一个大小为的的团集。
综上所述，团集（CLIQUE）问题归约于顶点覆盖（VERTEX COVER）问题，即。所以，顶点覆盖问题是一个NP完全问题。

顶点覆盖优化问题的近似算法
上面已经证得，顶点覆盖问题是一个NP完全问题，因此，没有一个确定性的多项式时间算法来解它。顶点覆盖的优化问题是找出图中的最小顶点覆盖。为了用近似算法解决这个问题，假设顶点用编号，并用下面的邻接表来存放顶点与顶点之间的关联边。
/*邻接表结点的数据结构*/
/*邻接结点的编号*/
/*下一个邻接顶点*/

/*图的邻接表头结点*/
则顶点覆盖问题的近似算法的求解步骤可以叙述如下：
（1）顶点的初始编号；
（2）如果顶点存在关联边，转到步骤（3否则，转到步骤（5）；
（3）令关联边为，把顶点和顶点登记到顶点覆盖中；
（4）删去与顶点和顶点关联的所有边；
（5），如果，转到步骤（2），否则，算法结束。
算法的实现过程叙述如下：
算法名称：顶点覆盖优化问题的近似算法；
输 入：无向图的邻接表，顶点个数为；
输 出：图的顶点覆盖，中的顶点个数为。

/*如果存在关联边*/

/*则选取边的顶点*/
/*删去与有关联的所有边*/

/*删去与关联的所有边*/

算法说明：
这个算法用数组来存放顶点覆盖中的各个顶点，用变量来存放数组中的顶点个数。开始时，把变量初始化为0，把顶点的编号初始化为0。然后从顶点开始，如果顶点存在着关联边，就把顶点及其一个邻接点登记到数组中。并删去与顶点和顶点的所有关联边。其中，第11行的函数用来删去顶点与顶点相邻接的登记项第17行函数用来删去顶点与顶点相邻接的登记项；第14行和20行分别把顶点和顶点的邻接表头结点的链指针置为空，从而分别删去这两个顶点与其他顶点相邻接的所有登记项。经过这样的处理，就把顶点及顶点的所有关联边删去。这种处理一直进行，直到图中的所有边都被删去为止。最后，在数组中存放着图的顶点覆盖中的各个顶点编号，变量表示数组中登记的顶点个数。
图2表示了这种处理过程。图2(a)表示图的初始状态；图2(b)表示选择边，把关联边的顶点及放进数组中，并删去顶点及顶点相关联的所有边，这里删去边，及；图2(c)表示选择边，把关联该边的顶点和顶点放进数组中，并删去边，及；这个过程一直进行，图2(g)表示最后得到的结果。整个处理过程共选择了6条边上的12个顶点，作为图的一个顶点覆盖，他们是。可以看到，它不是图的最小的顶点覆盖。图2(h)表示图的一个最小的顶点覆盖，它有7个顶点，分别是。

(a) (b)

(c) (d)

(e) (f)

(g) (h)

图2 算法处理过程图
算法近似性能估计：
下面来估计这个算法的近似性能。假定算法所选取的边集为，则这些边的关联边顶点被作为顶点覆盖中的顶点，放进数组中。因为一旦选择了某条边，例如边，则与顶点和顶点相关联的所有边均删去。再次选择第2条边时，第2条边与第1条边将不会具有公共顶点，则边集中的所有的边都不会具有公共顶点。这样放进数组中的顶点个数为，即。另一方面，图的任何一个顶点覆盖，至少包含中各条边中的一个顶点。若图的最小顶点覆盖为，则有。所以有：

由此可以得到，这个算法的性能比率小于或等于2。