覆蓋 (圖論)

圖的覆蓋是一個頂點的集合，使圖中的每一條邊都至少連結該集合中的一個頂點。尋找最小的頂點覆蓋的問題稱為頂點覆蓋問題（Vertex cover），它是一個NP完全問題。

左上圖紅色頂點覆蓋了四條邊（標記為綠色），剩餘兩條黑邊未覆蓋。
右上圖紅色頂點覆蓋了三條邊，剩餘三條邊未覆蓋。
下圖用兩個紅色頂點完成了所有邊的覆蓋。

頂點覆蓋和邊覆蓋分別與獨立集合和匹配問題有關。

定義

圖G的頂點覆蓋是一個頂點集合V，使得G中的每一條邊都接觸V中的至少一個頂點。我們稱集合V覆蓋了G的邊。最小頂點覆蓋是用最少的頂點來覆蓋所有的邊。頂點覆蓋數$\tau$是最小頂點覆蓋的大小。

相應地，圖G的邊覆蓋是一個邊集合E，使得G中的每一個頂點都接觸E中的至少一條邊。

如果只說覆蓋，則通常是指頂點覆蓋，而不是邊覆蓋。

例子

• 任何一個圖的頂點集合都覆蓋了它的邊集合。如果圖中不含有零度頂點，則反過來也成立。
• 完全二部圖K_m,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.