參考鏈接

定義

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

二分圖判斷方法

染色法：兩種顏色給頂點逐個染色，相鄰頂點具有不同的顏色。

引理

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

最小頂點覆蓋

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

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

K ?onig’s lemma：二分圖的最大覆蓋大小=最小點覆蓋大小

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

最小頂點覆蓋問題

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

按照行分塊：

按照列分塊：

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

最小邊覆蓋

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

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

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

最小獨立集

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

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

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

最大完全子圖

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

二分圖的最大完全子圖=補圖的最大獨立集

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

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

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