參考鏈接

定義

二分圖就是頂點(diǎn)集V可分割為兩個(gè)互不相交的子集，并且圖中每條邊依附的兩個(gè)頂點(diǎn)都分屬于這兩個(gè)互不相交的子集，兩個(gè)子集內(nèi)的頂點(diǎn)不相鄰。

二分圖判斷方法

染色法：兩種顏色給頂點(diǎn)逐個(gè)染色，相鄰頂點(diǎn)具有不同的顏色。

引理

在最大匹配中，每條匹配邊連接的兩個(gè)頂點(diǎn) (u, v) 最多只有一個(gè)與非匹配點(diǎn)有連邊。

最小頂點(diǎn)覆蓋

選了一個(gè)點(diǎn)就相當(dāng)于覆蓋了以它為端點(diǎn)的所有邊。最小頂點(diǎn)覆蓋就是選擇最少的點(diǎn)來覆蓋所有的邊。

上圖中，最小頂點(diǎn)覆蓋是： (2, 4, 6)

K ?onig’s lemma：二分圖的最大覆蓋大小=最小點(diǎn)覆蓋大小

證明：
對于二分圖 G，以及匹配圖 M，最大匹配數(shù)為 m；
1）我們可以構(gòu)造一個(gè)點(diǎn)集，這個(gè)點(diǎn)集是從最大匹配 M 里面取出來的，對于每一條匹配邊，選擇那個(gè)與非匹配點(diǎn)有連邊的點(diǎn)（根據(jù)引理1，這個(gè)點(diǎn)最多只有一個(gè)）加入點(diǎn)集 V；如果不存在，則隨便選一個(gè)，總共選擇 m 個(gè)點(diǎn)。
如圖所示：三條匹配邊 (1,6) (2,5) (4,7)；點(diǎn)集 V 構(gòu)造的時(shí)候，(1,6) 這條邊選擇 6 這個(gè)點(diǎn)，(2,5) 這條邊選擇 2 這個(gè)點(diǎn)， (4,7) 這條邊選擇 4 這個(gè)點(diǎn)；這個(gè)點(diǎn)集至少可以覆蓋 M，即最小頂點(diǎn)覆蓋≥m；
2）如果 G 中的邊除了 M 中匹配邊以外沒有其它非匹配邊，那么最小頂點(diǎn)覆蓋=m；
3）否則，還存在非匹配邊，如果這條非匹配邊的兩個(gè)端點(diǎn)都在非匹配點(diǎn)上，那么可以構(gòu)成一條新的匹配邊，從而和最大匹配矛盾；所以這些非匹配邊一定是其中一個(gè)端點(diǎn)在匹配點(diǎn)上，另一個(gè)端點(diǎn)在非匹配點(diǎn)上；
4）令一條非匹配邊上的一個(gè)端點(diǎn)為 u ，且 u 在非匹配點(diǎn)上，那么如果存在一條邊 (u, v)，點(diǎn) v 必定是在我們構(gòu)造出來的點(diǎn)集 V 中的，于是邊 (u, v) 一定可以被這個(gè)點(diǎn)集覆蓋，所以 最小頂點(diǎn)覆蓋 = m；

最小頂點(diǎn)覆蓋問題

給定一個(gè)n×n的棋盤，黑白格子組成，白色格子可以放置棋子，黑色格子不能放置棋子，如果一行或者一列上有其它棋子，并且中間沒有任何黑色格子，那么這樣的放置是非法的，求盡量放置最多的棋子（類似國際象棋中的 “車”）

按照行分塊：

按照列分塊：

每個(gè)格子屬于一個(gè)行分塊和列分塊。
假設(shè)格子(r,c)，行分塊為x，列分塊為y。
把一個(gè)能夠放置棋子的點(diǎn)看成二分圖的邊，選擇最少的行列分塊（對應(yīng)二分圖的點(diǎn)）覆蓋所有格子，轉(zhuǎn)換成最下頂點(diǎn)覆蓋問題，求構(gòu)造后的圖的最大匹配即可。

最小邊覆蓋

選了一條邊就相當(dāng)于覆蓋了它的兩個(gè)端點(diǎn)。最小邊覆蓋就是選擇最少的邊集，覆蓋所有的點(diǎn)集。

上圖中，最小邊覆蓋 E = {(2,9), (3, 8), (5, 10), (4, 9), (3, 11)}，答案是5

二分圖的最小邊覆蓋=頂點(diǎn)總數(shù)-孤立點(diǎn)數(shù)-最大匹配

最小獨(dú)立集

選取最多的點(diǎn)，使任意兩點(diǎn)都沒有關(guān)系。

上圖中，最大獨(dú)立集V = {1, 3, 5, 7, 8}

二分圖罪最大獨(dú)立集=頂點(diǎn)總數(shù)-最小頂點(diǎn)覆蓋

最大完全子圖

選取最多的點(diǎn)使圖中任意兩點(diǎn)都有關(guān)系。

二分圖的最大完全子圖=補(bǔ)圖的最大獨(dú)立集

（不相交）有向無環(huán)圖的最小路徑覆蓋

選擇一些路徑覆蓋所有點(diǎn)集，各路徑的點(diǎn)集之間沒有交集，要求路徑數(shù)最少。

上圖中，最小路徑覆蓋：1-2-4-5、6-7、3，答案是3