覆蓋 (圖論)

圖的覆蓋是一個頂點的集合,使圖中的每一條邊都至少連結該集合中的一個頂點。尋找最小的頂點覆蓋的問題稱為頂點覆蓋問題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.