顶点覆盖问题
最后更新于：2022-04-01 20:31:19
输入：无向图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.
';