一.二分圖

二分圖又稱作二部圖，是圖論中的一種特殊模型。 設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯的兩個頂點i和j分別屬于這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。當且僅當無向圖G的每一個回路的次數均是偶數時，G才是一個二分圖。如果無回路，相當于任一回路的次數為0，故也視為二分圖。—— 故二分圖判定用染色法。

二.二分圖匹配

給定一個二分圖G，在G的一個子圖M中，M的邊集{E}中的任意兩條邊都不依附于同一個頂點，則稱M是一個匹配。 選擇邊數最大的子圖稱為圖的最大匹配問題(maximal matching problem) 如果一個匹配中，圖中的每個頂點都和圖中某條邊相關聯，則稱此匹配為完全匹配，也稱作完備匹配。

三.匈牙利算法——用增廣路求最大匹配(稱作匈牙利算法，匈牙利數學家Edmonds于1965年提出)

先介紹一個概念：增廣路徑 如果從x部的一個未匹配的點出發，經過未匹配的邊，再經過匹配過的邊，再經過未匹配的邊，以此類推，知道抵達y部的一個未匹配的點。其有三條性質： 1.增廣路徑長度為奇數，且未匹配的邊比已匹配的邊多一條 2.將增廣路取反，得到一條（匹配數+1）的路徑 3.有且僅有當不再存在增廣路徑時，匹配數達到最大。

代碼:

bool dfs(int u) {vis[u]=true;for(node *p=adj[u];p;p=p->next){int v=p->v;if(!vis[v]){vis[v]=true;if(cy[v]==-1||dfs(cy[v])){cx[u]=v,cy[v]=u;return true;}}}return false; } void maxmatch() {memset(cx,-1,sizeof cx);memset(cy,-1,sizeof cy);match=0;for(int i=1;i<=cnt1;i++)if(cx[i]==-1){memset(vis,0,sizeof vis);if(dfs(i)) match++;} }

四.最小點覆蓋

最小點覆蓋=最大匹配 會證明了來更新。。。

五.最大點獨立集

對于任意圖中，有最大點獨立集與最小點覆蓋集互成補集。

轉載于:https://www.cnblogs.com/katarinayuan/p/6572872.html

總結

以上是生活随笔為你收集整理的二分图----最大匹配，最小点覆盖，最大点独立集的全部內容，希望文章能夠幫你解決所遇到的問題。

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