點覆蓋

點覆蓋，在圖論中點覆蓋的概念定義如下：對於圖G=(V,E)中的一個點覆蓋是一個集合S⊆V使得每一條邊至少有一個端點在S中。

基本介紹

• 中文名：點覆蓋
• 相關術語：邊覆蓋
• 定義：每一條邊至少有一個端點在S中
• 學科：圖論
• 領域：圖論
• 頂點覆蓋數：最小頂點覆蓋的大小

定義

在圖論中點覆蓋的概念定義如下：對於圖G=(V,E)中的一個點覆蓋是一個集合S⊆V使得每一條邊至少有一個端點在S中。圖G的頂點覆蓋是一個頂點集合V，使得G中的每一條邊都接觸V中的至少一個頂點。我們稱集合V覆蓋了G的邊。最小頂點覆蓋是用最少的頂點來覆蓋所有的邊。頂點覆蓋數是最小頂點覆蓋的大小。相應地，圖G的邊覆蓋是一個邊集合E，使得G中的每一個頂點都接觸E中的至少一條邊。如果只說覆蓋，則通常是指頂點覆蓋，而不是邊覆蓋。

相關定義

最小點覆蓋

最小點覆蓋：就是中點的個數最少的S集合。普通圖的最小點覆蓋數只能用搜尋解。
結論：二分圖的最小點覆蓋數=該二分圖的最大匹配數。

最小邊覆蓋

邊覆蓋的概念定義：邊覆蓋是圖的一個邊子集，使該圖上每一節點都與這個邊子集中的一條邊關聯，只有含孤立點的圖沒有邊覆蓋，邊覆蓋也稱為邊覆蓋集，圖G的最小邊覆蓋就是指邊數最少的覆蓋，圖G的最小邊覆蓋的邊數稱為G的邊覆蓋數。
結論：二分圖的最小邊覆蓋數=圖中的頂點數-（最小點覆蓋數）該二分圖的最大匹配數。

最大匹配

匹配：在圖論中，一個「匹配」（matching）是一個邊的集合，其中任意兩條邊都沒有公共頂點。
最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。
算法：匈牙利算法求二分圖的最大匹配。

最小路徑覆蓋

DAG圖的最小路徑覆蓋可以轉化為二分圖後求解。

最大獨立集

最大獨立集：在N個點的圖G中選出m個點，使這m個點兩兩之間沒有邊的點中，m的最大值。
結論：二分圖的最大點獨立數=點的個數-最小點覆蓋數（最大匹配） 。
證明：除過最小點覆蓋集，剩下的點全部都是互相獨立的，因為它們任意兩個點之間都沒有直接的連邊。
我們用反證法來證明一下，設最小點覆蓋集為V，假如有兩個沒在V中的點之間有一條邊，那么這條邊就不會被V中的點所覆蓋，那么V就不是最小點覆蓋集，又因為V是最小點覆蓋集，所以剛才假設的兩個點時不存在的，除過V之外的點都是兩兩相互獨立的。

例子

• 任何一個圖的頂點集合都覆蓋了它的邊集合。如果圖中不含有零度頂點，則反過來也成立。
  
• 完全二部圖K_m,n的頂點覆蓋數為min(m,n)，邊覆蓋數為max(m,n)。
  

性質

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