-
二分圖
鎖定
二分圖又稱作二部圖，是圖論中的一種特殊模型。 設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，並且圖中的每條邊（i，j）所關聯的兩個頂點i和j分別屬於這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。
- 中文名
- 二分圖
- 外文名
- Bipartite Graph
- 別 名
- 二部圖
- 性 質
- 圖論中的一種特殊模型
- 所屬領域
- 數學專業術語
- 應 用
- 數學
二分圖定義
簡而言之，就是頂點集V可分割為兩個互不相交的子集，並且圖中每條邊依附的兩個頂點都分屬於這兩個互不相交的子集，兩個子集內的頂點不相鄰。
二分圖辨析示例
區別二分圖，關鍵是看點集是否能分成兩個獨立的點集。
圖1
圖1中U和V構造的點集所形成的循環圈不為奇數，所以是二分圖。
圖2
圖2中U和V和W構造的點集所形成的的循環圈為奇數，所以不是二分圖。
二分圖充要條件
無向圖G為二分圖的充分必要條件是，G至少有兩個頂點，且其所有迴路的長度均為偶數。
證先證必要性。
設G為二分圖<X，E，Y>。由於X，Y非空，故G至少有兩個頂點。若C為G中任一回路，令
C = (v0,v 1,v2，…，v l-1,v l = v0)
其中諸vi (i = 0,1，…，l）必定相間出現於X及Y中，不妨設
{v0,v2,v4，…，v l = v0} Í X
{v1,v3,v5，…，v l-1} Í Y
因此l必為偶數，從而C中有偶數條邊。
再證充分性。
設G的所有迴路具有偶數長度，並設G為連通圖（不失一般性，若G不連通，則可對G的各連通分支作下述討論）。
令G的頂點集為V，邊集為E，現構作X，Y，使<X，E，Y> = G。取v0ÎV，置
X = {v | v= v0或v到v0有偶數長度的通路}
Y = V-X
X顯然非空。現需證Y非空，且沒有任何邊的兩個端點都在X中或都在Y中。
由於|V|≥2並且G為一連通圖，因此v0必定有相鄰頂點，設為v1，那麼v1ÎY；故Y不空。
設有邊（u,v），使uÎX，vÎX。那麼，v0到u有偶數長度的通路，或u = v0；v0到v有偶數長度的通路，或v = v0。無論何種情況，均有一條從v0到v0的奇數長度的閉路徑，因而有從v0到v0的奇數長度的迴路（因從閉路徑上可能刪去的迴路長度總為偶數），與題設矛盾。故不可能有邊（u,v）使u,v均在X中。
二分圖最大匹配
求二分圖最大匹配可以用最大流或者匈牙利算法。
最大匹配
給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附於同一個頂點，則稱M是一個匹配.
選擇這樣的邊數最大的子集稱為圖的最大匹配問題（maximal matching problem）
如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯，則稱此匹配為完全匹配，也稱作完備匹配。
算法
求最大匹配的一種顯而易見的算法是:先找出全部匹配，然後保留匹配數最多的。但是這個算法的複雜度為邊數的指數級函數。因此，需要尋求一種更加高效的算法。
增廣路的定義（也稱增廣軌或交錯軌）：
若P是圖G中一條連通兩個未匹配頂點的路徑，並且屬M的邊和不屬M的邊（即已匹配和待匹配的邊）在P上交替出現，則稱P為相對於M的一條增廣路徑.
由增廣路的定義可以推出下述三個結論：
1-P的路徑長度必定為奇數，第一條邊和最後一條邊都不屬於M.
2-P經過取反操作可以得到一個更大的匹配M'.
3-M為G的最大匹配當且僅當不存在相對於M的增廣路徑.
匈牙利算法
用增廣路求最大匹配（稱作匈牙利算法，匈牙利數學家Edmonds於1965年提出）
算法輪廓：
⑴置M為空
⑵找出一條增廣路徑P，通過取反操作獲得更大的匹配M'代替M
⑶重複⑵操作直到找不出增廣路徑為止
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; begin for i:=1 to m do if g[v,i] and (not y[ i ]) then begin y[ i ]:=true; if (link[ i ]=0)or find(link[ i ]) then begin link[ i ]:=v; find:=true; exit; end; end; find:=false; end; begin //read the graph into array g[][] for i:=1 to n do begin fillchar(y,sizeof(y),0); if find(i) then inc(ans); end;
其中n,m分別為2部圖兩邊節點的個數，兩邊的節點分別用1..n,1..m編號
g[x][y]=true表示x,y兩個點之間有邊相連
link[y]記錄的是當前與y節點相連的x節點
y記錄的是y中的i節點是否被訪問過.
算法的思路是不停的找增廣軌，並增加匹配的個數，增廣軌顧名思義是指一條可以使匹配數變多的路徑，在匹配問題中，增廣軌的表現形式是一條"交錯軌",也就是説這條由圖的邊組成的路徑，它的第一條邊是還沒有參與匹配的，第二條邊參與了匹配，第三條邊沒有..最後一條邊沒有參與匹配，並且始點和終點還沒有被選擇過.這樣交錯進行，顯然他有奇數條邊.那麼對於這樣一條路徑，我們可以將第一條邊改為已匹配，第二條邊改為未匹配...以此類推.也就是將所有的邊進行"反色",容易發現這樣修改以後，匹配仍然是合法的，但是匹配數增加了一對.另外，單獨的一條連接兩個未匹配點的邊顯然也是交錯軌.可以證明，當不能再找到增廣軌時，就得到了一個最大匹配.這也就是匈牙利算法的思路.
代碼中find（i）就是尋找有沒有從x點i開始的增廣軌，如果有就進行上述操作，代碼是遞歸的，所以看起來不是很顯然，畫個圖試試就很清楚了。
二分圖性質
二分圖中，點覆蓋數是匹配數。
（1）二分圖的最大匹配數等於最小覆蓋數，即求最少的點使得每條邊都至少和其中的一個點相關聯，很顯然直接取最大匹配的一段節點即可。
（2）二分圖的獨立數等於頂點數減去最大匹配數，很顯然的把最大匹配兩端的點都從頂點集中去掉這個時候剩餘的點是獨立集，這是|V|-2*|M|，同時必然可以從每條匹配邊的兩端取一個點加入獨立集並且保持其獨立集性質。
（3）DAG的最小路徑覆蓋，將每個點拆點後作最大匹配，結果為n-m，求具體路徑的時候順着匹配邊走就可以，匹配邊i→j',j→k',k→l'....構成一條有向路徑。
（4）最大匹配數=左邊匹配點+右邊未匹配點。因為在最大匹配集中的任意一條邊，如果他的左邊沒標記，右邊被標記了，那麼我們就可找到一條新的增廣路，所以每一條邊都至少被一個點覆蓋。
（5）最小邊覆蓋=圖中點的個數-最大匹配數=最大獨立集。
二分圖判定
二分圖是這樣一個圖： 有兩頂點集且圖中每條邊的的兩個頂點分別位於兩個頂點集中，每個頂點集中沒有邊直接相連接！
無向圖G為二分圖的充分必要條件是，G至少有兩個頂點,且其所有迴路的長度均為偶數。
判斷二分圖的常見方法是染色法： 開始對任意一未染色的頂點染色，之後判斷其相鄰的頂點中，若未染色則將其染上和相鄰頂點不同的顏色， 若已經染色且顏色和相鄰頂點的顏色相同則説明不是二分圖，若顏色不同則繼續判斷，bfs和dfs可以搞定！
二分圖C語言實例
//其中n,m分別為2部圖兩邊節點的個數，兩邊的節點分別用0..n-1,0..m-1編號
bool g[n][m];//g[x][y]表示x,y兩個點之間有邊相連
bool y[m];//y[i]記錄的是y中的i節點是否被訪問過.
int link[m];//link[y]記錄的是當前與y節點相連的x節點
bool find(int v)
{
int i;
for(i=0;i<m;i++)
{
if(g[v][i]&&!y[i])
{
y[i]=true;
if(link[i]==-1||find(link[i]))
{
link[i]=v;
return true;
}
}
}
return false;
}
int main()
{
//read the graph int array g[][]
memset(link,-1,sizeof(link));
for(i=0;i<n;i++)
{
memset(y,0,sizeof(y));
if(find(i)) ans++;
}
return 0;
}
- 參考資料
-
- 1. 基於二分圖的温度網絡拓撲性質研究 ．中國知網[引用日期2017-03-12]
- 2. 二分圖頂點覆蓋問題的求解及應用 ．中國知網[引用日期2017-03-12]
