覆盖 (图论)

维基百科,自由的百科全书
跳转至: 导航搜索
图中的两个顶点(红色)以及它们覆盖的边(蓝色);这是一个顶点覆盖。

图的覆盖是一些顶点(或边)的集合,使得图中的每一条边(每一个顶点)都至少接触集合中的一个顶点(边)。寻找最小的顶点覆盖的问题称为顶点覆盖问题,它是一个NP完全问题。

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

定义[编辑]

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

相应地,图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.