清华大学出版社 TSINGHUA UNIVERSITY PRESS 92顶点覆盖问题的近似算法 问题描述:无向图G=(VE)的顶点覆盖是它的顶点集V的 个子集vsV,使得若(u,)是G的一条边,则v∈V或 u∈V。顶点覆盖V的大小是它所包含的顶点个数V Vertex Set approx Vertex Cover( Graph g cset=0 Cset用来存储顶点 el=ge i 覆盖中的各顶点。初 始为空,不断从边集 while(el!=0)i e1中选取一边(u,v), 从e1中任取一条边(u,V); 将边的端点加入cset cset=cset∪uUV} 中,并将e1中已被u 从e1中删去与u和M相关联的所有边; 和v覆盖的边删去, 直至cset已覆盖所有 边。即e1为空 return c 44 9.2 顶点覆盖问题的近似算法 问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的 一个子集V’V，使得若(u,v)是G的一条边，则v∈V’或 u∈V’ 。顶点覆盖V’的大小是它所包含的顶点个数|V’|。 VertexSet approxVertexCover ( Graph g ) { cset=； e1=g.e； while (e1 != ) { 从e1中任取一条边(u,v)； cset=cset∪{u,v}； 从e1中删去与u和v相关联的所有边； } return c } Cset用来存储顶点 覆盖中的各顶点。初 始为空，不断从边集 e1中选取一边(u,v)， 将边的端点加入cset 中，并将e1中已被u 和v覆盖的边删去， 直至cset已覆盖所有 边。即e1为空