[科普中國]-二分圖

定義

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

辨析示例區(qū)別二分圖，關(guān)鍵是看點(diǎn)集是否能分成兩個(gè)獨(dú)立的點(diǎn)集。1

上圖中U和V構(gòu)造的點(diǎn)集所形成的循環(huán)圈不為奇數(shù)，所以是二分圖。

上圖中U和V和W構(gòu)造的點(diǎn)集所形成的的循環(huán)圈為奇數(shù)，所以不是二分圖。

充要條件無向圖G為二分圖的充分必要條件是，G至少有兩個(gè)頂點(diǎn)，且其所有回路的長度均為偶數(shù)。

證先證必要性。

設(shè)G為二分圖。由于X，Y非空，故G至少有兩個(gè)頂點(diǎn)。若C為G中任一回路，令

C = (v0,v 1,v2，…，v l-1,v l = v0)

其中諸vi (i = 0,1，…，l）必定相間出現(xiàn)于X及Y中，不妨設(shè)

{v0,v2,v4，…，v l = v0} í X

{v1,v3,v5，…，v l-1} í Y

因此l必為偶數(shù)，從而C中有偶數(shù)條邊。

再證充分性。

設(shè)G的所有回路具有偶數(shù)長度，并設(shè)G為連通圖（不失一般性，若G不連通，則可對G的各連通分支作下述討論）。

令G的頂點(diǎn)集為V，邊集為E，現(xiàn)構(gòu)作X，Y，使 = G。取v0?V，置

X = {v | v= v0或v到v0有偶數(shù)長度的通路}

Y = V-X

X顯然非空?，F(xiàn)需證Y非空，且沒有任何邊的兩個(gè)端點(diǎn)都在X中或都在Y中。

由于|V|≥2并且G為一連通圖，因此v0必定有相鄰頂點(diǎn)，設(shè)為v1，那么v1?Y；故Y不空。

設(shè)有邊（u,v），使u?X，v?X。那么，v0到u有偶數(shù)長度的通路，或u = v0；v0到v有偶數(shù)長度的通路，或v = v0。無論何種情況，均有一條從v0到v0的奇數(shù)長度的閉路徑，因而有從v0到v0的奇數(shù)長度的回路（因從閉路徑上可能刪去的回路長度總為偶數(shù)），與題設(shè)矛盾。故不可能有邊（u,v）使u,v均在X中。

“沒有任何邊的兩個(gè)端點(diǎn)全在Y中”的證明可仿上進(jìn)行，請讀者思考2。

最大匹配求二分圖最大匹配可以用最大流或者匈牙利算法。

最大匹配

給定一個(gè)二分圖G，在G的一個(gè)子圖M中，M的邊集中的任意兩條邊都不依附于同一個(gè)頂點(diǎn)，則稱M是一個(gè)匹配.

選擇這樣的邊數(shù)最大的子集稱為圖的最大匹配問題（maximal matching problem)

如果一個(gè)匹配中，圖中的每個(gè)頂點(diǎn)都和圖中某條邊相關(guān)聯(lián)，則稱此匹配為完全匹配，也稱作完備匹配。

算法

求最大匹配的一種顯而易見的算法是:先找出全部匹配，然后保留匹配數(shù)最多的。但是這個(gè)算法的復(fù)雜度為邊數(shù)的指數(shù)級(jí)函數(shù)。因此，需要尋求一種更加高效的算法。

增廣路的定義（也稱增廣軌或交錯(cuò)軌）：

若P是圖G中一條連通兩個(gè)未匹配頂點(diǎn)的路徑，并且屬M(fèi)的邊和不屬M(fèi)的邊（即已匹配和待匹配的邊）在P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑.

由增廣路的定義可以推出下述三個(gè)結(jié)論：

1-P的路徑長度必定為奇數(shù)，第一條邊和最后一條邊都不屬于M.

2-P經(jīng)過取反操作可以得到一個(gè)更大的匹配M'.

3-M為G的最大匹配當(dāng)且僅當(dāng)不存在相對于M的增廣路徑.

匈牙利算法

用增廣路求最大匹配（稱作匈牙利算法，匈牙利數(shù)學(xué)家Edmonds于1965年提出）

算法輪廓：

⑴置M為空

⑵找出一條增廣路徑P，通過取反操作獲得更大的匹配M'代替M

⑶重復(fù)⑵操作直到找不出增廣路徑為止

g:array[1..maxn,1..maxm]of boolean;y:array[1..maxm]of boolean;link:array[1..maxm]of longint;function find(v:longint):boolean;var i:longint;beginfor i:=1 to m doif g[v,i] and (not y[ i ]) thenbeginy[ i ]:=true;if (link[ i ]=0)or find(link[ i ]) thenbeginlink[ i ]:=v;find:=true;exit;end;end;find:=false;end;begin//read the graph into array g[][]for i:=1 to n dobeginfillchar(y,sizeof(y),0);if find(i) then inc(ans);end;其中n,m分別為2部圖兩邊節(jié)點(diǎn)的個(gè)數(shù)，兩邊的節(jié)點(diǎn)分別用1..n,1..m編號(hào)

g[x][y]=true表示x,y兩個(gè)點(diǎn)之間有邊相連

link[y]記錄的是當(dāng)前與y節(jié)點(diǎn)相連的x節(jié)點(diǎn)

y記錄的是y中的i節(jié)點(diǎn)是否被訪問過.

算法的思路是不停的找增廣軌，并增加匹配的個(gè)數(shù)，增廣軌顧名思義是指一條可以使匹配數(shù)變多的路徑，在匹配問題中，增廣軌的表現(xiàn)形式是一條"交錯(cuò)軌",也就是說這條由圖的邊組成的路徑，它的第一條邊是目前還沒有參與匹配的，第二條邊參與了匹配，第三條邊沒有..最后一條邊沒有參與匹配，并且始點(diǎn)和終點(diǎn)還沒有被選擇過.這樣交錯(cuò)進(jìn)行，顯然他有奇數(shù)條邊.那么對于這樣一條路徑，我們可以將第一條邊改為已匹配，第二條邊改為未匹配...以此類推.也就是將所有的邊進(jìn)行"反色",容易發(fā)現(xiàn)這樣修改以后，匹配仍然是合法的，但是匹配數(shù)增加了一對.另外，單獨(dú)的一條連接兩個(gè)未匹配點(diǎn)的邊顯然也是交錯(cuò)軌.可以證明，當(dāng)不能再找到增廣軌時(shí)，就得到了一個(gè)最大匹配.這也就是匈牙利算法的思路.

代碼中find(i）就是尋找有沒有從x點(diǎn)i開始的增廣軌，如果有就進(jìn)行上述操作，代碼是遞歸的，所以看起來不是很顯然，畫個(gè)圖試試就很清楚了。

性質(zhì)二分圖中，點(diǎn)覆蓋數(shù)是匹配數(shù)。
（1）二分圖的最大匹配數(shù)等于最小覆蓋數(shù)，即求最少的點(diǎn)使得每條邊都至少和其中的一個(gè)點(diǎn)相關(guān)聯(lián)，很顯然直接取最大匹配的一段節(jié)點(diǎn)即可。
（2）二分圖的獨(dú)立數(shù)等于頂點(diǎn)數(shù)減去最大匹配數(shù)，很顯然的把最大匹配兩端的點(diǎn)都從頂點(diǎn)集中去掉這個(gè)時(shí)候剩余的點(diǎn)是獨(dú)立集，這是|V|-2*|M|，同時(shí)必然可以從每條匹配邊的兩端取一個(gè)點(diǎn)加入獨(dú)立集并且保持其獨(dú)立集性質(zhì)。
（3）DAG的最小路徑覆蓋，將每個(gè)點(diǎn)拆點(diǎn)后作最大匹配，結(jié)果為n-m，求具體路徑的時(shí)候順著匹配邊走就可以，匹配邊i→j',j→k',k→l'....構(gòu)成一條有向路徑。

（4）最大匹配數(shù)=左邊匹配點(diǎn)+右邊未匹配點(diǎn)。因?yàn)樵谧畲笃ヅ浼械娜我庖粭l邊，如果他的左邊沒標(biāo)記，右邊被標(biāo)記了，那么我們就可找到一條新的增廣路，所以每一條邊都至少被一個(gè)點(diǎn)覆蓋。

（5）最小邊覆蓋=圖中點(diǎn)的個(gè)數(shù)-最大匹配數(shù)=最大獨(dú)立集。

判定二分圖是這樣一個(gè)圖： 有兩頂點(diǎn)集且圖中每條邊的的兩個(gè)頂點(diǎn)分別位于兩個(gè)頂點(diǎn)集中，每個(gè)頂點(diǎn)集中沒有邊直接相連接！

無向圖G為二分圖的充分必要條件是，G至少有兩個(gè)頂點(diǎn),且其所有回路的長度均為偶數(shù)。

判斷二分圖的常見方法是染色法： 開始對任意一未染色的頂點(diǎn)染色，之后判斷其相鄰的頂點(diǎn)中，若未染色則將其染上和相鄰頂點(diǎn)不同的顏色， 若已經(jīng)染色且顏色和相鄰頂點(diǎn)的顏色相同則說明不是二分圖，若顏色不同則繼續(xù)判斷，bfs和dfs可以搞定！

易知：任何無回路的的圖均是二分圖3。

C語言實(shí)例//其中n,m分別為2部圖兩邊節(jié)點(diǎn)的個(gè)數(shù)，兩邊的節(jié)點(diǎn)分別用0..n-1,0..m-1編號(hào)bool g[n][m];//g[x][y]表示x,y兩個(gè)點(diǎn)之間有邊相連bool y[m];//y[i]記錄的是y中的i節(jié)點(diǎn)是否被訪問過.int link[m];//link[y]記錄的是當(dāng)前與y節(jié)點(diǎn)相連的x節(jié)點(diǎn)bool find(int v){ int i; for(i=0;i