顶点覆盖问题

输入：无向图G(V，E)

输出：C属于V，C中点数最小，满足E中任意一条边中的两个顶点至少有一个在C中

APPROX_Vertex_Cover(G)

1    C=空集

2    E‘ = E

3    While E‘ != 空集 Do

4        任选{u,v}属于E‘

5        C = C U {u,v}

6        删除E‘中所有与u,v相连的边

7    Return C

Ratio Bound(近似比)

设A为算法第四步中选中的边集，由算法第六步可知，A中无邻接边

第五步中每次增加两个节点到C，因此|C| = 2|A|

设C*是优化解，则C*必须覆盖A

由于A中无邻接边，C*至少包含A中每条边的一个节点，

于是|A|<=|C*|,|C| = 2|A| <= 2|C*|

即|C| / |C*| <= 2.

因此，算法近似比为2.

顶点覆盖问题

原文：http://blog.csdn.net/k76853/article/details/50040053