输入：无向图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.