二分圖整理

一.二分圖的定義：

二分圖又稱作二部圖，是圖論中的一種特殊模型。 設G=(V,E)是一個無向圖，如果頂點V可分割為兩個互不相交的子集(A,B)，并且圖中的每條邊（i，j）所關聯的兩個頂點i和j分别屬于這兩個不同的頂點集(i in A,j in B)，則稱圖G為一個二分圖。

二.判斷一個圖是否為二分圖

結論1：無向圖G為二分圖的充分必要條件是，G至少有兩個頂點，且其所有回路的長度均為偶數。

結論2：任何無回路的的圖均是二分圖

判斷二分圖的常見方法是染色法： 開始對任意一未染色的頂點染色，之後判斷其相鄰的頂點中，若未染色則将其染上和相鄰頂點不同的顔色， 若已經染色且顔色和相鄰頂點的顔色相同則說明不是二分圖，若顔色不同則繼續判斷，bfs和dfs可以搞定。

三.什麼是二分圖最大比對

給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附于同一個頂點，則稱M是一個比對.選擇這樣的邊數最大的子集稱為圖的最大比對問題（maximal matching problem)

四.二分圖最大比對涉及的術語

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

增廣路徑：若P是圖G中一條連通兩個未比對頂點的路徑，并且屬M的邊和不屬M的邊（即已比對和待比對的邊）在P上交替出現，則稱P為相對于M的一條增廣路徑.

若P為一條增廣路徑則有

P的路徑長度必定為奇數，第一條邊和最後一條邊都不屬于M.

P經過取反操作可以得到一個更大的比對M’.（M由P的偶數邊構成，所謂取反是指新的M由P的奇數邊構成，這樣邊數會比原來多1）

M為G的最大比對當且僅當不存在相對于M的增廣路徑.

五.如何求解二分圖最大比對

1.匈牙利算法

該算法是用增廣路求最大比對。（十分強悍）

算法輪廓：

(1)置M為空

(2)找出一條增廣路徑P，通過取反操作獲得更大的比對M’代替M

(3)重複(2)操作直到找不出增廣路徑為止

增廣路徑的算法

我們采用DFS的辦法找一條增廣路徑：

從X部一個未比對的頂點u開始，找一個未通路的鄰接點v（ v一定是Y部頂點）。對于v，分兩種情況：

(1)如果v未比對，則已經找到一條增廣路

(2)如果v已經比對，則取出v的比對頂點w(w一定是X部頂點)，邊(w,v)目前是比對的，根據“取反”的想法，要将(w,v)改為未比對， (u,v)設為比對，能實作這一點的條件是看從w為起點能否新找到一條增廣路徑P’。如果行，則u-v-P’就是一條以u為起點的增廣路徑。

bool find(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(mp[u][i] && !vis[i])
        {
            vis[i]=1;
            if(!ly[i] || find(ly[i]))
            {
                ly[i]=u;
                return 1;
            }
        }
    }
    return 0;
}
int maxmatch()
{
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(col[i]==0)continue;  //如果不是這種顔色
        memset(vis,0,sizeof(vis));
        ans+=find(i);
    }
    return ans;
}
           

6、二分圖的最小點覆寫

定義：假如選了一個點就相當于覆寫了以它為端點的所有邊。最小頂點覆寫就是選擇最少的點來覆寫所有的邊。

方法：最小點覆寫 = 二分圖的最大比對。

7、二分圖的最大獨立集

最大獨立集：在Ｎ個點的圖G中選出m個點，使這m個點兩兩之間沒有邊的點中，m的最大值。

8、二分圖的最小路徑覆寫

最小邊覆寫：用盡量少的不相交簡單路徑覆寫有向無環圖(DAG)G的所有頂點