清华大学出版社 TSINGHUA UNIVERSITY PRESS 92顶点覆盖问题的近似算法 图(a)~(e)说明 a 了算法的运行过程 及结果。(e)表示 算法产生的近似最 优顶点覆盖cset, a((a(ef 它由顶点 c,d,e,f,g所组 (d) 成。(f)是图G的 个最小顶点覆盖, 它只含有3个顶点: b,d和e。 a e g (e) 算法 approx Vertex Cover的性能比为2。5 9.2 顶点覆盖问题的近似算法 图(a)～(e)说明 了算法的运行过程 及结果。(e)表示 算法产生的近似最 优顶点覆盖cset， 它由顶点 b,c,d,e,f,g所组 成。(f)是图G的一 个最小顶点覆盖， 它只含有3个顶点： b,d和e。 算法approxVertexCover的性能比为2