图G的顶点覆盖是一组顶点, 使得G中的每个边均入射到这些顶点中的至少一个顶点上。
决策顶点覆盖问题已被证明是NPC。现在, 我们要解决顶点覆盖问题的最佳版本, 即, 我们要找到给定图的最小尺寸的顶点覆盖。我们称这种顶点覆盖为最佳顶点覆盖C *。
文章图片
顶点覆盖的近似算法：
Approx-Vertex-Cover (G = (V, E)){C = empty-set;
E'= E;
While E' is not empty do{Let (u, v) be any edge in E': (*)Add u and v to C;
Remove from E' all edges incident tou or v;
}Return C;
}【近似算法（顶点覆盖）】这个想法是一个接一个的边缘（u, v）, 将两个顶点都放到C上, 然后移除所有入射到u或v的边缘。我们继续进行直到所有边缘都被移除为止。 C是VC。但是C有多好？
文章图片
VC = {b, c, d, e, f, g}
推荐阅读
- 如何降低IT成本（优化预算的11种策略和方法）
- 加速WordPress网站的25个性能和优化技巧合集
- 选择最佳云服务提供商要知道的12件事（技巧和方法）
- 30种云监控工具合集介绍（最新权威指南）
- Pulumi与Terraform主要差异比较（有什么区别（））
- 5种云部署模型的差异比较（它们有什么不同（））
- Web服务器与应用服务器有什么区别（选择哪个？）
- 根服务器是啥？详解IPv6的根服务器！
- 磁盘空间占用查看器SpaceSniffer运用技巧