覆盖 (图论)
(重定向自頂點覆盖問題)
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/6/69/Vertex_covers.svg/220px-Vertex_covers.svg.png)
右上图红色顶点覆盖了三条边,剩余三条边未覆盖。
下图用两个红色顶点完成了所有边的覆盖。
图的覆盖是一個顶点的集合,使图中的每一条边都至少連結該集合中的一个顶点。寻找最小的顶点覆盖的问题称为顶点覆盖问题(Vertex cover),它是一个NP完全问题。
定义
图G的顶点覆盖是一个顶点集合V,使得G中的每一条边都接触V中的至少一个顶点。我们称集合V覆盖了G的边。最小顶点覆盖是用最少的顶点来覆盖所有的边。顶点覆盖数是最小顶点覆盖的大小。
相应地,图G的边覆盖是一个边集合E,使得G中的每一个顶点都接触E中的至少一条边。
如果只说覆盖,则通常是指顶点覆盖,而不是边覆盖。
例子
性质
- 图的顶点数目等于顶点覆盖数与最大独立集合的大小之和(Gallai 1959)。
参考文献
- Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.