點覆蓋

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

最小點覆蓋：就是中點的個數最少的S集合。普通圖的最小點覆蓋數只能用搜索解。

結論：二分圖的最小點覆蓋數=該二分圖的最大匹配數。

邊覆蓋的概念定義：邊覆蓋是圖的一個邊子集，使該圖上每一節點都與這個邊子集中的一條邊關聯，只有含孤立點的圖沒有邊覆蓋，邊覆蓋也稱為邊覆蓋集，圖G的最小邊覆蓋就是指邊數最少的覆蓋，圖G的最小邊覆蓋的邊數稱為G的邊覆蓋數。

結論：二分圖的最小邊覆蓋數=圖中的頂點數-（最小點覆蓋數）該二分圖的最大匹配數。

匹配：在圖論中，一個「匹配」（matching）是一個邊的集合，其中任意兩條邊都沒有公共頂點。

最大匹配：一個圖所有匹配中，所含匹配邊數最多的匹配，稱為這個圖的最大匹配。

算法：匈牙利算法求二分圖的最大匹配。

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

最大獨立集：在N個點的圖G中選出m個點，使這m個點兩兩之間沒有邊的點中，m的最大值。

結論：二分圖的最大點獨立數=點的個數-最小點覆蓋數（最大匹配） 。

證明：除過最小點覆蓋集，剩下的點全部都是互相獨立的，因為它們任意兩個點之間都沒有直接的連邊。

我們用反證法來證明一下，設最小點覆蓋集為V，假如有兩個沒在V中的點之間有一條邊，那麼這條邊就不會被V中的點所覆蓋，那麼V就不是最小點覆蓋集，又因為V是最小點覆蓋集，所以剛才假設的兩個點時不存在的，除過V之外的點都是兩兩相互獨立的。