二分圖比對相關概念及内容

這裡的概念比較多容易混淆，而且出題時這種可能會針對這些内容直接出結論題，整理一下

二分圖的概念

如果一個圖可以将其頂點分成兩個互不相交的子集，且圖中的每條邊所連的兩個點分屬這兩個子集，那麼這個圖可以稱作二分圖。

一個無向圖為二分圖的充要條件是，至少有兩個頂點，且其所有回路的長度均為偶數。是以說判斷奇環也就是判斷二分圖。二分圖的判斷可以用二分圖染色，就是使左邊的點集是一個顔色右邊的點集是一個顔色，和都可以實作。

二分圖最大比對

二分圖比對就是求出一個原圖的子圖使得任意兩條邊不連在同一個頂點上。

最大比對就是一個使得子圖邊數最多的比對。

匈牙利算法是在二分圖問題中很常用的一種算法，作用就是來求最大比對。

主要流程如下：

枚舉左側的點看這個點是否有連向右側的邊，如果有并且連向的這個點沒有被比對，那麼标記這兩個點比對成功；如果右側有邊的點已經被比對了，那就“協商”，讓這個比對右側點的左側點再去比對另一個右側點，看是不是能給目前點空出位置來，如果可以那麼就讓去比對，來比對，思想就是如此。

可以發現已經比對的點不會在接下來的算法流程中失配，最多隻會更換比對的對象。

算法中首先需要周遊每個點，然後再讓每個點找連向右側的邊，複雜度。

由于經常會周遊到沒有比對的點或沒有邊連向的點，是以普遍是跑不滿的。

#include <bits/stdc++.h>
#define

using namespace std;
int g[A], n, m, e, ans; bool f[A][A], vis[A];
int find(int x) {
  for (int i = 1; i <= m; i++)
    if (f[x][i] and !vis[i]) { //如果有邊連向這個點并且這個點沒有被通路過
      vis[i] = 1; //标記通路，已經比對過的點就不用再比對了
      if (!g[i] or find(g[i])) { //如果它還沒有被比對或協商之後可以給x騰出位置
        g[i] = x; //标記與哪個點比對了
        return true;
      }
    }
  return false;
}
int main(int argc, char const *argv[]) {
  cin >> n >> m >> e; //n,m,e分别為左圖點數，右圖點數和總邊數
  for (int i = 1, x, y; i <= e; i++) cin >> x >> y, f[x][y] = 1; //有邊就标記為1
  for (int i = 1; i <= n; i++) if (find(i)) memset(vis, 0, sizeof vis), ans++; //對每個點找比對對象
  cout << ans << endl; //vis要每次清空，vis标記的是一個右側點是否被比對過
}      

二分圖的最大比對還可以直接用網絡流來做，的話複雜度。

具體做法就是在左邊建立超級源點，在右邊建立超級彙點，超級源點向左側點連邊，右側點向超級彙點連邊，中間的邊不變，邊的流量都是，這個圖的最大流就是二分圖的最大比對。

二分圖比對中還有一個概念叫增廣路。

增廣路是指，從一個未比對點開始，經過若幹個比對點，最後到達對面集合的一個未比對點的路徑。即這條路徑将兩個不同集合的兩個未比對點通過一系列比對點相連。将增廣路與原比對的邊取反後可以得到一個更大的比對，這裡的取反就是增廣路中的邊變成比對的，之前比對的邊變成未比對的。

增廣路的路徑長度必定為奇數，第一條邊和最後一條邊都不屬于目前比對。奇數邊比偶數邊多一條，于是當我們把所有奇數邊都加到比對子圖并把偶數邊都删除，比對數就會增加。

一個子圖為原圖的最大比對當且僅當不存在的增廣路徑。

帶權二分圖比對

上面的二分圖最大比對可以看成每條邊的權值都是，我們需要找到一個權值最大的比對。

對于帶權的二分圖，它的最優比對一定是一個完備比對，就是說比對到的點數是左右側點數的最小值。

由于是完備比對，是以原先沒有的邊需要連上，邊權為即可。

專門求解帶權二分圖最優比對的一種算法叫算法，可惜我并沒有學過，是以我會選擇用費用流來做帶權二分圖比對。

二分圖問題是網絡流問題的特殊模型，是以基本都可以用網絡流的知識來做。

最大獨立集

一個圖的獨立集是一個點集，其中這些點兩兩之間沒有邊相連。點數最多的獨立集叫這個圖的最大獨立集。

再介紹一個引申概念，圖的團。圖的團就是一些點兩兩之間都有邊相連。最大團就是點數最多的團。

一般圖的最大獨立集是問題，現在還沒有通用解法。但是對于特殊的二分圖就有做法。

下面是一些定理，也是結論，題目中可能會用到：

1. 無向圖的最大團 = 這個圖補圖的最大獨立集
2. 最大獨立集 = 點的總數 – 最小點覆寫（最大比對）

最小支配集

支配集是一個點的集合，這些點與剩下的點之間都有邊相連，點數最少的支配集叫最小支配集。

用處不大，可以來看一下這個題​​​P2899 手機網絡​​

最小點覆寫

點覆寫是一個點的集合，使得所有邊都至少有一端與是點集中的點，點數最少的點覆寫叫最小點覆寫。

二分圖的最小點覆寫 = 最大比對

就不給證明了，記住結論也沒什麼不妥，網上也有不少證明，還是一個了解性的問題。

最小路徑覆寫