二分圖基礎知識
首先什麼是二分圖
顧名思義就是能分成兩個部分的圖
要注意的是,‘分’的是點并且這兩個集合(這裡我們稱作X集合和Y集合)内部所有的點之間沒有邊相連,也就是說X集合中任何兩點之間都不會有邊相連, Y亦然
定理1:無向圖G為二分圖的一個充要條件是 1、G中至少包含兩個頂點 2、G中所有的回路長度都必須是偶數
接下來是一些概念:
比對:設G=<V, E>為二分圖,如果 M⊆E,并且 M 中兩點沒有任何兩點有公共端點(被其他比對的邊共用),則成M為G的一個比對。【也就是說比對的實質是一些邊的集合。】
最大比對:邊數最多的比對
完備比對與完全比對:若 X 中所有的頂點都是比對 M 中的端點。則稱 M 為X的完備比對。 若M既是 X-完備比對又是 Y-完備比對,則稱M 為 G 的完全比對。
最小點覆寫:用盡可能少的點去覆寫所有的邊【最小點覆寫集是點的集合,其個數為最小點覆寫數】
最大點獨立:跟網絡流中的最大點權獨立集有點類似,這裡指的是最大獨立的個數
接下來是二分圖的一些性質:
設無向圖G有n個頂點,并且沒有孤立頂點,那麼,
1、點覆寫數 + 點獨立數 = n
2、最小點覆寫數 = 二分圖的最大比對
3、最大點獨立數 = n - 最小點覆寫數 = n - 最大比對
二分圖的判定:
判斷一個圖是不是二分圖有兩條1、n>= 2 2、不存在奇圈
我們可以用黑白染色的方法進行判斷
(
交叉染色法
下面着重介紹下交叉染色法的定義與原理
首先任意取出一個頂點進行染色,和該節點相鄰的點有三種情況:
1.未染色 那麼繼續染色此節點(染色為另一種顔色)
2.已染色但和目前節點顔色不同 跳過該點
3.已染色并且和目前節點顔色相同 傳回失敗(該圖不是二分圖)
下面在拓展兩個概念:
(1) 如果一個雙連通分量内的某些頂點在一個奇圈中(即雙連通分量含有奇圈),那麼這個雙連通分量的其他頂點也在某個奇圈中;
第一個條件的證明:我們假設有一個奇圈,因為是點雙,沒有割點,必然有緊挨着的圈,假設這個是偶數圈,則,這個偶數圈必然能和原來的奇圈組成新的奇圈(因為:新的圈=(奇數圈-k)+(偶數圈-k)=奇數+偶數-偶數=奇數,k是共同邊上的點數
(2) 如果一個雙連通分量含有奇圈,則他必定不是一個二分圖。反過來也成立,這是一個充要條件。
)
const int maxn = 105;
int col[maxn];
bool is_bi(int u) {
for(int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if(col[v] == col[u]) return false;
if(!col[v]) {
col[v] = 3 - col[u];
if(!is_bi(v)) return false;
}
}
return true;
}
二分圖的最大比對、完美比對和匈牙利算法
二分圖:簡單來說,如果圖中點可以被分為兩組,并且使得所有邊都跨越組的邊界,則這就是一個二分圖。準确地說:把一個圖的頂點劃分為兩個不相交集 UU 和VV ,使得每一條邊都分别連接配接UU、VV中的頂點。如果存在這樣的劃分,則此圖為一個二分圖。二分圖的一個等價定義是:不含有「含奇數條邊的環」的圖。圖 1 是一個二分圖。為了清晰,我們以後都把它畫成圖 2 的形式。
比對:在圖論中,一個「比對」(matching)是一個邊的集合,其中任意兩條邊都沒有公共頂點。例如,圖 3、圖 4 中紅色的邊就是圖 2 的比對。
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI0gTMx81dsQWZ4lmZf1GLlpXazVmcvwFciV2dsQXYtJ3bm9CX9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCMy81dvRWYoNHLwEzX5xCMx8FesU2cfdGLwMzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5COwMjMxcDN5QTM1gzM4U2YxYzX3UzMxITMxMzLcJTMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.png)
我們定義比對點、比對邊、未比對點、非比對邊,它們的含義非常顯然。例如圖 3 中 1、4、5、7 為比對點,其他頂點為未比對點;1-5、4-7為比對邊,其他邊為非比對邊。
最大比對:一個圖所有比對中,所含比對邊數最多的比對,稱為這個圖的最大比對。圖 4 是一個最大比對,它包含 4 條比對邊。
完美比對:如果一個圖的某個比對中,所有的頂點都是比對點,那麼它就是一個完美比對。圖 4 是一個完美比對。顯然,完美比對一定是最大比對(完美比對的任何一個點都已經比對,添加一條新的比對邊一定會與已有的比對邊沖突)。但并非每個圖都存在完美比對。
舉例來說:如下圖所示,如果在某一對男孩和女孩之間存在相連的邊,就意味着他們彼此喜歡。是否可能讓所有男孩和女孩兩兩配對,使得每對兒都互相喜歡呢?圖論中,這就是完美比對問題。如果換一個說法:最多有多少互相喜歡的男孩/女孩可以配對兒?這就是最大比對問題。
基本概念講完了。求解最大比對問題的一個算法是匈牙利算法,下面講的概念都為這個算法服務。
交替路:從一個未比對點出發,依次經過非比對邊、比對邊、非比對邊…形成的路徑叫交替路。
增廣路:從一個未比對點出發,走交替路,如果途徑另一個未比對點(出發的點不算),則這條交替路稱為增廣路(agumenting path)。例如,圖 5 中的一條增廣路如圖 6 所示(圖中的比對點均用紅色标出):
增廣路有一個重要特點:非比對邊比比對邊多一條。是以,研究增廣路的意義是改進比對。隻要把增廣路中的比對邊和非比對邊的身份交換即可。由于中間的比對節點不存在其他相連的比對邊,是以這樣做不會破壞比對的性質。交換後,圖中的比對邊數目比原來多了 1 條。
我們可以通過不停地找增廣路來增加比對中的比對邊和比對點。找不到增廣路時,達到最大比對(這是增廣路定理)。匈牙利算法正是這麼做的。在給出匈牙利算法 DFS 和 BFS 版本的代碼之前,先講一下匈牙利樹。
匈牙利樹一般由 BFS 構造(類似于 BFS 樹)。從一個未比對點出發運作 BFS(唯一的限制是,必須走交替路),直到不能再擴充為止。例如,由圖 7,可以得到如圖 8 的一棵 BFS 樹:
這棵樹存在一個葉子節點為非比對點(7 号),但是匈牙利樹要求所有葉子節點均為比對點,是以這不是一棵匈牙利樹。如果原圖中根本不含 7 号節點,那麼從 2 号節點出發就會得到一棵匈牙利樹。這種情況如圖 9 所示(順便說一句,圖 8 中根節點 2 到非比對葉子節點 7 顯然是一條增廣路,沿這條增廣路擴充後将得到一個完美比對)。
下面給出匈牙利算法的 DFS 和 BFS 版本的代碼:
// 頂點、邊的編号均從 0 開始
// 鄰接表儲存
struct Edge
{
int from;
int to;
int weight;
Edge(int f, int t, int w):from(f), to(t), weight(w) {}
};
vector<int> G[__maxNodes]; /* G[i] 存儲頂點 i 出發的邊的編号 */
vector<Edge> edges;
typedef vector<int>::iterator iterator_t;
int num_nodes;
int num_left;
int num_right;
int num_edges;
int matching[__maxNodes]; /* 存儲求解結果 */
int check[__maxNodes];
bool dfs(int u)
{
for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 對 u 的每個鄰接點
int v = edges[*i].to;
if (!check[v]) { // 要求不在交替路中
check[v] = true; // 放入交替路
if (matching[v] == -1 || dfs(matching[v])) {
// 如果是未蓋點,說明交替路為增廣路,則交換路徑,并傳回成功
matching[v] = u;
matching[u] = v;
return true;
}
}
}
return false; // 不存在增廣路,傳回失敗
}
int hungarian()
{
int ans = 0;
memset(matching, -1, sizeof(matching));
for (int u=0; u < num_left; ++u) {
if (matching[u] == -1) {
memset(check, 0, sizeof(check));
if (dfs(u))
++ans;
}
}
return ans;
}
queue<int> Q;
int prev[__maxNodes];
int Hungarian()
{
int ans = 0;
memset(matching, -1, sizeof(matching));
memset(check, -1, sizeof(check));
for (int i=0; i<num_left; ++i) {
if (matching[i] == -1) {
while (!Q.empty()) Q.pop();
Q.push(i);
prev[i] = -1; // 設 i 為路徑起點
bool flag = false; // 尚未找到增廣路
while (!Q.empty() && !flag) {
int u = Q.front();
for (iterator_t ix = G[u].begin(); ix != G[u].end() && !flag; ++ix) {
int v = edges[*ix].to;
if (check[v] != i) {
check[v] = i;
Q.push(matching[v]);
if (matching[v] >= 0) { // 此點為比對點
prev[matching[v]] = u;
} else { // 找到未比對點,交替路變為增廣路
flag = true;
int d=u, e=v;
while (d != -1) {
int t = matching[d];
matching[d] = e;
matching[e] = d;
d = prev[d];
e = t;
}
}
}
}
Q.pop();
}
if (matching[i] != -1) ++ans;
}
}
return ans;
}
匈牙利算法的要點如下
-
- 從左邊第 1 個頂點開始,挑選未比對點進行搜尋,尋找增廣路。
-
- 如果經過一個未比對點,說明尋找成功。更新路徑資訊,比對邊數 +1,停止搜尋。
- 如果一直沒有找到增廣路,則不再從這個點開始搜尋。事實上,此時搜尋後會形成一棵匈牙利樹。我們可以永久性地把它從圖中删去,而不影響結果。
- 由于找到增廣路之後需要沿着路徑更新比對,是以我們需要一個結構來記錄路徑上的點。DFS 版本通過函數調用隐式地使用一個棧,而 BFS 版本使用
數組。prev
性能比較
兩個版本的時間複雜度均為O(V⋅E)O(V⋅E)。DFS 的優點是思路清晰、代碼量少,但是性能不如 BFS。我測試了兩種算法的性能。對于稀疏圖,BFS 版本明顯快于 DFS 版本;而對于稠密圖兩者則不相上下。在完全随機資料 9000 個頂點 4,0000 條邊時前者領先後者大約 97.6%,9000 個頂點 100,0000 條邊時前者領先後者 8.6%, 而達到 500,0000 條邊時 BFS 僅領先 0.85%。
補充定義和定理:
最大比對數:最大比對的比對邊的數目
最小點覆寫數:選取最少的點,使任意一條邊至少有一個端點被選擇
最大獨立數:選取最多的點,使任意所選兩點均不相連
最小路徑覆寫數:對于一個 DAG(有向無環圖),選取最少條路徑,使得每個頂點屬于且僅屬于一條路徑。路徑長可以為 0(即單個點)。
定理1:最大比對數 = 最小點覆寫數(這是 Konig 定理)
定理2:最大比對數 = 最大獨立數