覆盖 (图论)

图的覆盖是一個顶点的集合,使图中的每一条边都至少連結該集合中的一个顶点。寻找最小的顶点覆盖的问题称为顶点覆盖问题Vertex cover英语Vertex cover),它是一个NP完全问题。

左上图红色顶点覆盖了四条(标记为绿色),剩余两条黑边未覆盖。
右上图红色顶点覆盖了三条,剩余三条边未覆盖。
下图用两个红色顶点完成了所有边的覆盖。

顶点覆盖和边覆盖分别与独立集合匹配问题有关。

定义

G顶点覆盖是一个顶点集合V,使得G中的每一条边都接触V中的至少一个顶点。我们称集合V覆盖了G的边。最小顶点覆盖是用最少的顶点来覆盖所有的边。顶点覆盖数 是最小顶点覆盖的大小。

相应地,图G边覆盖是一个边集合E,使得G中的每一个顶点都接触E中的至少一条边。

如果只说覆盖,则通常是指顶点覆盖,而不是边覆盖。

例子

  • 任何一个图的顶点集合都覆盖了它的边集合。如果图中不含有零度顶点,则反过来也成立。
  • 完全二部图Km,n的顶点覆盖数为min(m, n),边覆盖数为max(m, n)。

性质

  • 图的顶点数目等于顶点覆盖数与最大独立集合的大小之和(Gallai 1959)。

参考文献

  • Gallai, Tibor "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2, 133-138, 1959.