1.二分圖的原始模型及相關概念

二分圖又稱作二部圖，是圖論中的一種特殊模型。
設G=(V,E)G=(V,E)是一個無向圖。如頂點集VV 可分割為兩個互不相交的子集，并且圖中每
條邊依附的兩個頂點都分屬兩個不同的子集。則稱圖GG 為二分圖。我們將上邊頂點集合稱
為XX 集合，下邊頂點結合稱為YY 集合，如下圖，就是一個二分圖。

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

???????選擇這樣的邊數最大的子集稱為圖的最大匹配問題（maximal matchingproblem)

???????如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯，則稱此匹配為完全匹配，也稱作完備匹配。

???????如果該二分圖的每條邊都有一個權值且存在完備匹配，那么我們要找出一個所有邊權值和最大的完備匹配的問題叫做二分圖的最優匹配問題。

二分圖的最小覆蓋數：

在二分圖中選取最少數目的點集，使得二分圖任意一邊都至少有一個端點在該點集中。這個點集的大小是二分圖的最小覆蓋數，且二分圖的最小覆蓋數==二分圖的最大匹配數。

二分圖的最大獨立集：

在二分圖中選取最多數目的點集，使得該點集中的任意兩點在二分圖中都不存在一條邊相連。這個點集就是二分圖的最大獨立集。且二分圖的最大獨立集大小==|G|(二分圖頂點數) - 二分圖最大匹配數。

?DAG的最小路徑覆蓋：

即在DAG圖中尋找盡量少的路徑，使得每個節點恰好在一條路徑上(不同的路徑不可能有公共點)。注意：單獨的節點也可以作為一條路徑。

DAG最小路徑覆蓋解法如下：

把所有節點i拆為左邊點集的i和右邊點集的i’，如果DAG圖中有i到j的有向邊，那么添加一條二分圖的i到j’的無向邊。最終DAG的最小路徑覆蓋數==DAG圖的節點數n - 新二分圖的最大匹配數m。注意：該由原DAG圖構建的新二分圖的最大匹配數m<=n-1.

有向圖是否存在有向環覆蓋？把有向圖的所有節點i拆為左邊點集的i和右邊點集的i’，如果有向圖中有i到j的有向邊，那么添加一條二分圖的i到j’的無向邊。最終如果新二分圖的最大匹配數m==有向圖的節點數n，那么說明該有向圖的所有節點能被正好1個或多個不相交(沒有公共節點)的有向環覆蓋。

???????原理類似于DAG的最小路徑覆蓋的解釋，因為每個節點都能找到一個后繼節點繼續往下一直走，所以必然原來有向圖存在環。又因為在一個可行的最大匹配中，每個節點只有一個后繼，所以必然存在不相交的有向環覆蓋。

???????有向圖的最優有向環覆蓋：在有向圖中找到1個或多個點不想交的環，這些環正好覆蓋了有向圖的所有節點且這些環上邊的權值最大。本問題解法：把有向圖的所有節點i拆為左邊點集的i和右邊點集的i’，如果有向圖中有i到j的有向邊，那么添加一條二分圖的i到j’的無向邊。最終計算二分圖的最優完美匹配即可，該二分圖的最優完美匹配的權值和就是有向圖的最優有向環覆蓋的權值和。

2.求解二分圖最大匹配

網絡流算法
使用網絡流算法：
實際上，可以將二分圖最大匹配問題看成是最大流問題的一種特殊情況。
用網絡流算法思想解決最大匹配問題的思路：
首先：建立源點ss 和匯點tt ，從ss 向XX 集合的所有頂點引一條邊，容量為11，從YY 集合
的所有頂點向TT 引一條邊，容量為11。
然后：將二分圖的所有邊看成是從XiXi到YjYj的一條有向邊，容量為1。
求最大匹配就是求ss 到tt 的最大流。
最大流圖中從XiXi 到YjYj 有流量的邊就是匹配集合中的一條邊。

匈牙利算法
發現了一篇寫得非常好的博客，可以看看這里的解釋：趣寫算法系列之–匈牙利算法

3.常見模型

上面已經提到了圖的匹配的概念，此外還有幾個相關的有用的概念，在此我們再介紹除
匹配之外的三個概念：
記圖G=(V,E)G=(V,E)。

匹配：在GG 中兩兩沒有公共端點的邊集合M?EM?E。
邊覆蓋：GG 中的任意頂點都至少是FF 中某條邊的端點的邊集F?EF?E。
獨立集：在GG 中兩兩互不相連的頂點集合S?VS?V。
頂點覆蓋：GG 中的任意邊都有至少一個端點屬于SS 的頂點集合S?VS?V 。

相應的也有：最大匹配，最小邊覆蓋，最大獨立集，最小頂點覆蓋。
例如下圖中，最大匹配為{e1,e3}{e1,e3}，最小邊覆蓋為{e1,e3,e4}{e1,e3,e4}，最大獨立集為{v2,v4,v5}{v2,v4,v5}，

三個重要等式：
在二分圖中滿足：
(1) 對于不存在孤立點的圖， 最大匹配 + 最小邊覆蓋 =VV
證明:通過最大匹配加邊得到最小邊覆蓋。

(2) 最大獨立集 +最小頂點覆蓋=VV
證明:獨立集中若存在邊，那么頂點覆蓋不能覆蓋完所有邊，矛盾。

(3)|最大匹配| = |最小頂點覆蓋|。
具體證明參考：百度百科:Konig定理
二分圖的最小頂點覆蓋 最大獨立集 最大團

有向圖中應用二分匹配
求有向圖最小路徑覆蓋：
對于有向圖的最小路徑覆蓋，先拆點，將每個點分為兩個點，左邊是1-n個點，右邊是1-n個點
然后每一條有向邊對應左邊的點指向右邊的點。對此圖求最大匹配，再用n-最大匹配即可。

證明：
將圖中頂點看做n條邊，每次加入一條有向邊相當于合并兩條邊，又因為一個點只能經過一次，與匹配的性質一樣。

例題
POJ3041(求最小點覆蓋)

將所有x行視為一個點集，所有y列視為一個點集，那么（x，y）就表示x和y之間有一條邊了。而這題所求是最小點覆蓋，即最大匹配。

#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int n,map[510][510],flag[510],vis[510]; int find(int k); int main() {int i,j,k,sum,m,x,y;memset(map,0,sizeof(map));memset(flag,0,sizeof(flag));scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d",&x,&y);map[x][y]=1;}sum=0;for(i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(find(i))sum+=1;}printf("%d\n",sum);return 0; } int find(int k) {int i,j;for(j=1;j<=n;j++){if(map[k][j] && !vis[j]){vis[j]=1;if(!flag[j] || find(flag[j])){flag[j]=k;return 1;}}}return 0; }

POJ1422(有向圖最小路徑覆蓋)

?其實每個傘兵走的就是一條有向的簡單路徑。我們要求的就是該DAG圖的最少可以用多少條簡單路徑覆蓋所有節點且任意兩條路徑不會有重復的節點。 這就是DAG的最小路徑覆蓋問題。

?DAG最小路徑覆蓋問題的解 = 節點數-二分圖的最大匹配。

?首先要把DAG中的每個點在二分圖的左右點集都保存一遍，然后對于DAG中的邊i->j， 那么就在二分圖中添加邊左i->右j。 之后求該二分圖的最大匹配邊數即可。

#include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxn=120+5;struct Max_Match {int n;vector<int> g[maxn];bool vis[maxn];int left[maxn];void init(int n){this->n=n;for(int i=1; i<=n; ++i) g[i].clear();memset(left,-1,sizeof(left));}bool match(int u){for(int i=0;i<g[u].size();++i){int v=g[u][i];if(!vis[v]){vis[v]=true;if(left[v]==-1 || match(left[v])){left[v]=u;return true;}}}return false;}int solve(){int ans=0;for(int i=1; i<=n; ++i){memset(vis,0,sizeof(vis));if(match(i)) ++ans;}return ans;} }MM;int main() {int T; scanf("%d",&T);while(T--){int n,m;scanf("%d%d",&n,&m);MM.init(n);while(m--){int u,v;scanf("%d%d",&u,&v);MM.g[u].push_back(v);}printf("%d\n",n-MM.solve());}return 0; }

POJ1486Sorting Slides(判斷唯一匹配)

其實就是二分圖最大匹配問題.左邊點集用幻燈片編號表示,右邊點集用數字表示. 如果某個幻燈片i包含了數字j,那么從左邊i到右邊j就存在一條邊.

???????首先我們求出這個圖的最大匹配數x, 根據題意這x值一定是等于n(幻燈片數的). 然后我們記錄目前求到的最大匹配的各個邊.

???????我們每次判斷最大匹配邊集的某條邊是否是必需邊. 我們只要先刪除這條邊,如果之后求最大匹配數依然==n,那么這條邊不是必需邊.如果之后求最大匹配數依然<n,那么這條邊是必需邊.(做好標記）

#include<cstdio> #include<cstring> using namespace std; const int maxn=26+5;struct Max_Match {int n,m;bool g[maxn][maxn];bool vis[maxn];int left[maxn];void init(int n){this->n=n;memset(g,0,sizeof(g));memset(left,-1,sizeof(left));}bool match(int u){for(int v=1;v<=n;v++)if(g[u][v] && !vis[v]){vis[v]=true;if(left[v]==-1 || match(left[v])){left[v]=u;return true;}}return false;}int solve(){int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(match(i)) ans++;}return ans;} }MM;int xmin[maxn],ymin[maxn],xmax[maxn],ymax[maxn]; struct {int x; // edge[i].x=x 表示第i個矩形配對的數字 是x;bool ok;//標記該邊是否是 必需邊 }edge[maxn];int main() {int n,kase=0;while(scanf("%d",&n)==1&&n){MM.init(n);memset(edge,0,sizeof(edge));for(int i=1;i<=n;i++){scanf("%d%d%d%d",&xmin[i],&xmax[i],&ymin[i],&ymax[i]);}for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);for(int j=1;j<=n;j++){if(xmin[j]<=x&&x<=xmax[j]&&ymin[j]<=y&&y<=ymax[j])MM.g[j][i]=true;}}MM.solve();int edge_num=n;for(int i=1;i<=n;i++){edge[MM.left[i]].x=i;edge[MM.left[i]].ok=true;}for(int i=1;i<=n;i++)//嘗試刪除第i條匹配邊{int j=edge[i].x;MM.g[i][j]=false;//刪除此邊memset(MM.left,-1,sizeof(MM.left));int num = MM.solve();if(num == n)//刪除邊后,匹配數不變{edge[i].ok=false;edge_num--;}MM.g[i][j]=true;//還原此邊}printf("Heap %d\n",++kase);if(edge_num==0) printf("none\n");else{for(int i=1;i<=n;i++)if(edge[i].ok)printf("(%c,%d) ",i-1+'A',edge[i].x);printf("\n");}printf("\n");}return 0; }

poj2724PurifyingMachine(求二分圖最小邊覆蓋)

?也就是給你一些不同的(判重之后)二進制串,每個串可以通過1次操作凈化,也可以把兩個只有1位不同的串通過1次操作聯合凈化.要我們求最少的操作次數.

???????我們把所有串按其中1的個數和是奇還是偶分成左右兩個點集.

對于任意兩個串,如果他們只有1位不同,那么就在他們之間連接一條無向邊.(這兩個串一定分別屬于不同的點集)

???????由于串的總數是固定的,且一個串可以通過單獨凈化也可以通過聯合凈化.而我們向讓凈化的次數最少,我們自然想聯合凈化(即一次可以凈化兩個串)的次數盡量多了. 那么我們最多可以進行多少次聯合凈化呢? 這個數值==我們建立二分圖的最大匹配邊數.(想想是不是,因為一個串最多只能被凈化一次)

??????假設總的不同串有n個,我們建立二分圖的最大匹配數(即聯合凈化最大次數)為ans,那么我們總共需要n-ans次凈化即可.(想想為什么)

???????當然本題也可以不用把串特意分成左右點集(本程序實現就是用的這種方式：未分左右點集),我們只需要把原圖翻倍,然后求翻倍圖的最大匹配數ans,最后用n-ans/2即可。

#include<cstdio> #include<cstring> #include<vector> #include<set> #include<string> #include<iostream> using namespace std; const int maxn=1000+100;struct Max_Match {int n;vector<int> g[maxn];bool vis[maxn];int left[maxn];void init(int n){this->n=n;for(int i=1;i<=n;i++) g[i].clear();memset(left,-1,sizeof(left));}bool match(int u){for(int i=0;i<g[u].size();i++){int v=g[u][i];if(!vis[v]){vis[v]=true;if(left[v]==-1 || match(left[v])){left[v]=u;return true;}}}return false;}int solve(){int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(match(i)) ++ans;}return ans;} }MM;struct Node {string s;bool link(Node& rhs)//判斷兩個string是否只相差1位{int num = 0;for(int i=0;i<s.size(); i++)if(s[i]!=(rhs.s)[i]) ++num;return num==1;} }node[maxn];int main() {int N,M;while(scanf("%d%d",&N,&M)==2 && N){int num=0;set<string> st;//判重stringfor(int i=1;i<=M;i++){string s;cin>>s;if(s.find("*")!=-1){int pos=s.find("*");string s1(s),s2(s);s1[pos]='0';s2[pos]='1';if(st.find(s1) == st.end())//s1與已有string不重復{st.insert(s1);node[++num].s = s1;}if(st.find(s2) == st.end())//s2與已有string不重復{st.insert(s2);node[++num].s = s2;}}else{if(st.find(s) == st.end()){st.insert(s);node[++num].s = s;}}}MM.init(num);for(int i=1;i<=num;i++)for(int j=1;j<=num;j++)if(i!=j)if(node[i].link(node[j]))MM.g[i].push_back(j);printf("%d\n",num-MM.solve()/2);}return 0; }

?

總結

以上是生活随笔為你收集整理的二分图匹配详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。