圖的頂點數目等於頂點覆蓋數與最大獨立集合的大小之和（Gallai 1959）。

參考文獻[編輯]. Gallai, Tibor "Über extreme Punkt- und Kantenmengen ...覆蓋(圖論)維基百科，自由的百科全書跳至導覽跳至搜尋左上圖紅色頂點覆蓋了四條邊（標記為綠色），剩餘兩條黑邊未覆蓋。

右上圖紅色頂點覆蓋了三條邊，剩餘三條邊未覆蓋。

下圖用兩個紅色頂點完成了所有邊的覆蓋。

圖的覆蓋是一些頂點（或邊）的集合，使得圖中的每一條邊（每一個頂點）都至少接觸集合中的一個頂點（邊）。

尋找最小的頂點覆蓋的問題稱為頂點覆蓋問題，它是一個NP完全問題。

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

目次1定義2例子3性質4參考文獻定義[編輯]圖G的頂點覆蓋是一個頂點集合V，使得G中的每一條邊都接觸V中的至少一個頂點。

我們稱集合V覆蓋了G的邊。

最小頂點覆蓋是用最少的頂點來覆蓋所有的邊。

頂點覆蓋數τ{\displaystyle\tau}是最小頂點覆蓋的大小。

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

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

例子[編輯]任何一個圖的頂點集合都覆蓋了它的邊集合。

如果圖中不含有零度頂點，則反過來也成立。

完全二部圖Km,n的頂點覆蓋數為min(m,n)，邊覆蓋數為max(m,n)。

性質[編輯]圖的頂點數目等於頂點覆蓋數與最大獨立集合的大小之和（Gallai1959）。

參考文獻[編輯]Gallai,Tibor"ÜberextremePunkt-undKantenmengen."Ann.Univ.Sci.Budapest,EotvosSect.Math.2,133-138,1959.取自「https://zh.wikipedia.org/w/index.php?title=覆盖_(图论)&oldid=56222469」分類：圖論導覽選單個人工具沒有登入討論貢獻建立帳號登入命名空間條目討論臺灣正體已展開已摺疊不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體查看閱讀編輯檢視歷史更多已展開已摺疊搜尋導航首頁分類索引特色內容新聞動態近期變更隨機條目資助維基百科說明說明維基社群方針與指引互助客棧知識問答字詞轉換IRC即時聊天聯絡我們關於維基百科工具連結至此的頁面相關變更上傳檔案特殊頁面靜態連結頁面資訊引用此頁面維基數據項目列印/匯出下載為PDF可列印版其他專案維基共享資源其他語言DeutschفارسیFrançaisעבריתBahasaIndonesiaItaliano日本語PolskiРусскийСрпски/srpskiTürkçe編輯連結