覆盖 (图论)
(重定向自点覆盖问题)
图的覆盖是一个顶点的集合,使图中的每一条边都至少连结该集合中的一个顶点。寻找最小的顶点覆盖的问题称为顶点覆盖问题(Vertex cover),它是一个NP完全问题。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/69/Vertex_covers.svg/220px-Vertex_covers.svg.png)
右上图红色顶点覆盖了三条边,剩余三条边未覆盖。
下图用两个红色顶点完成了所有边的覆盖。
定义
编辑图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.