二分圖復習

相關概念

• 匹配：

  一個圖是一個匹配，是指這個圖中任意兩條邊都沒有公共頂點，每個頂點至多連出一條邊，而每一條邊都將一對頂點相匹配。

  • 極大匹配

    ? 圖\(G\)的一個極大匹配是這樣的一個匹配，他不可能是圖\(G\)的任何一個匹配的真子圖。如果\(M\)是\(G\)的一個極大匹配，則\(G\)中每一條邊都和\(M\)中的一條邊相鄰，否則就能將該邊加入\(M\)。

  • 最大匹配

    ? 最大匹配中的是指邊數最多的一組匹配，最大匹配可能不止一個，但是最大匹配的邊數是確定的，并且不可能超過圖中頂點的一半（因為每個不存在公共邊，而不同邊對應的公共頂點不同）， 最大匹配中的頂點數稱為圖的配對數， 一般記作\(v(G)\).

    ? 最大匹配顯然都是極大匹配，但是極大匹配不一定是最大匹配， 下圖就是極大匹配，但不是最大匹配。

    

  • 完美匹配

    ? 圖\(G\)的一個完美匹配是一個包括了圖\(G\)中原來的所有頂點的匹配，是最大匹配的一種。下述圖中左右兩個為最大匹配，而中間的是完美匹配，完美匹配同時也是原圖的最小邊數的邊覆蓋（即是用最少的邊包括所有頂點的子圖）。

    

  • 交替路徑（Alternating Path）

    路徑中每一條邊交替的屬于或不屬于\(M\), 比如第1，3， 5條邊屬于\(M\), 而第2，4，6條邊不屬于\(M\)等等。

  • 增廣路徑 (Augumenting Path)

    從\(M\)中沒有用到的頂點開始，并從\(M\)中沒有用到的頂點結束的交替路徑。

• 覆蓋

  • 頂點覆蓋

    圖\(G\)的一個頂點覆蓋是一個頂點集合\(V\), 使得\(G\)中的每一條邊都接觸\(V\)中的至少一個頂點。我們稱集合\(V\)覆蓋了\(G\)的邊

  • 最小頂點覆蓋

    用最小的頂點去覆蓋所有的邊。

    

  • 邊覆蓋

    邊覆蓋是一個邊集合\(E\), 使得圖\(G\)中的每一個頂點都接觸\(E\)中的至少一條邊

  如果只說覆蓋，通常指點覆蓋。

定義

二分圖，又稱二部圖，英文名為Bipartite graph

節點由兩個集合組成，且兩個集合內部沒有邊的圖

換言之，存在一種方案，將節點劃分成滿足以上性質的 集合

性質

• 如果兩個集合中的點分別染成黑色和白色，可以發現二分圖中的每一條邊都一定是連接一個黑色點和一個白色點
• 二分圖不存在長度為 奇數 的環 (二分圖中每條邊都從一個集合走向另一個集合，從一個集合返回該集合只能經過偶數個邊)

? 當然，對于長度不存奇數的環，我們也可以通過染色，將所有點劃分為兩個集合，就形成了二分圖。

二分圖的判斷 (染色法) \(O(V + E)\)

例題: 關押罪犯

#include <bits/stdc++.h>

using i64 = long long;

const int N = 2e4 + 10, M = 2e5 + 10;

int n, m;

int h[N], e[M], ne[M], w[M], idx;

int color[N]; // 0沒有染色， 1，2兩個不同的顏色

/*
	check(mid)

	對于積怨值大于mid的兩個罪犯分別關到不同的監獄內

	等價于：除去積怨值小于等于mid的邊，子圖能否構成二分圖

	顯然能構成二分圖的子圖也能構成二分圖， 所以滿足二段性

	即[不滿足，滿足]兩段，那么結果就是第一個滿足的mid
*/

void add(int a, int b, int c) {
	ne[idx] = h[a], h[a] = idx, e[idx] = b, w[idx ++] = c;
}

bool dfs(int u, int c, int mid) {
	color[u] = c;

	for (int i = h[u]; ~i; i = ne[i]) {
		int v = e[i];

		if (w[i] <= mid) continue;

		if (color[v]) {
			if (color[v] == c) return false;
		} else if (!dfs(v, 3 - c, mid)) return false;
	}

	return true;
}

bool check(int mid) {
	memset(color, 0, sizeof color);

	for (int i = 1; i <= n; i ++)
		if (color[i] == 0)
			if (!dfs(i, 1, mid)) return false;

	return true;
}

int main() {
	memset(h, -1, sizeof h);

	std::cin >> n >> m;

	while (m --) {
		int a, b, c;

		std::cin >> a >> b >> c;

		add(a, b, c), add(b, a, c);
	}

	int l = 0, r = 1e9;

	while (l < r) {
		int mid = l + r >> 1;

		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	std::cout << l;
}

最大匹配 （匈牙利算法）\(O(V_左E)\)

注意：標題復雜度中的\(V\)為左邊點數。

對于二分圖下列的概念：

? 匹配: 一個圖是一個匹配（或稱獨立邊集）是指這個圖之中，任意兩條邊都沒有公共的頂點。這時每個頂點都至多連出一條邊，而每一條邊都將一對頂點相匹配。

? 最大匹配：邊數最多的一組匹配

? 匹配點：在匹配當中的點， 非匹配點同理

? 增廣路徑：從一個非匹配點走, 經過非匹配邊和匹配邊 這樣交替，最后經過非匹配邊到非匹配點

\(最大匹配 \rightleftharpoons 不存在增廣路徑\)

例題：棋盤覆蓋

#include <bits/stdc++.h>

using i64 = long long;

typedef std::pair<int, int> PII;

const int N = 110;

int n, m;

int g[N][N], st[N][N];

PII match[N][N];

bool find(int x, int y) {
	static int dx[] = {0, -1, 1, 0}, dy[] = {1, 0, 0, -1};

	for (int i = 0; i <= 3; i ++) {
		int a = x + dx[i], b = y + dy[i];

		if (a < 1 || a > n || b < 1 || b > n) continue;

		if (st[a][b] || g[a][b]) continue;

		st[a][b] = true;

		PII t = match[a][b];

		if (t.first == -1 || find(t.first, t.second)) {
			match[a][b] = {x, y};
			return true;
		}
	}

	return false;
}

int main() {
	memset(match, -1, sizeof match);

	std::cin >> n >> m;

	while (m --) {
		int x, y;

		std::cin >> x >> y;

		g[x][y] = true;
	}

	int res = 0;

	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			if ((i + j) % 2 && !g[i][j]) {
				memset(st, 0, sizeof st);

				if (find(i, j)) res ++;	
			}
		}
	}
	
	std::cout << res;

	return 0;
}

最小點覆蓋

? 點覆蓋，在圖論中點覆蓋的概念定義如下：對于圖\(G=<V,E>\)中的一個點覆蓋是一個集合 \(S?V\)使得每一條邊至少有一個端點在\(S\)中。

? 在二分圖中，有這樣一個結論： \(最小點覆蓋 = 最大匹配數\)

證明：

• 最小點覆蓋\(\ge\)最大匹配數

  在一組匹配中，匹配的兩條邊沒有公共點，所以每條匹配邊至少要選定一個點，最大匹配為\(m\)， 則至少要選定\(m\)個點

• 最小點覆蓋\(=\)最大匹配數 (構造)

  1.先求出最大匹配，從左部每個非匹配點出發，做一遍增廣并標記所有經過的點

  2.左部所有未被標記的點和右部所有被標記的點

  ? 左部所有非匹配點一定都被標記

  ? 右部所有非匹配點一定沒有被標記

  ? 對于每一個匹配邊，左右兩點要么同時被標記，要么同時不被標記

機器任務

#include <bits/stdc++.h>

using i64 = long long;

const int N = 110;

int n, m, k;

bool g[N][N], st[N];

int match[N];

bool find(int x) {
	for (int i = 1; i < m; i ++) {
		if (!st[i] && g[x][i]) {
			st[i] = true;
			int t = match[i];

			if (!t || find(t)) {
				match[i] = x;
				return true;
			}
		}
	}
	return false;
}

int main() {
	while (std::cin >> n, n) {

		std::cin >> m >> k;	
		memset(g, 0, sizeof g);
		memset(match, 0, sizeof match);

		while (k --) {
			int t, a, b;

			std::cin >> t >> a >> b;

			if (!a || !b) continue;

			g[a][b] = true;
		}	

		int res = 0;

		for (int i = 1; i < n; i ++) {
			memset(st, 0, sizeof st);

			if (find(i)) res ++;
		}

		std::cout << res << "\n";
	}
}

最大獨立集

? 對于圖\(G<V,E>\) 選出最大的點集\(S\), 使得集合\(S\)內的任何兩個點之間都沒有邊。

最大團

? 對于圖\(G<V, E>\), 選出最大的點集\(S\), 使得集合\(S\)內的任何兩個點之間都有邊 。

? 原圖的最大獨立集是補圖的最大團。

? 在二分圖中，求最大獨立集 等價于求 去掉最少的點 = m，將所有邊都破壞掉 等價于 找最小點覆蓋 = m 等價于 找最大匹配 = m。

? 最終最大獨立集就等于去掉最少的點使集合內的點都沒有邊，所以等于\(n(總點數) - m\)

騎士放置

#include <bits/stdc++.h>
#define x first
#define y second

using i64 = long long;

const int N = 110;

typedef std::pair<int, int> PII;

int n, m, k;

PII match[N][N];

bool g[N][N], st[N][N];

int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};


bool find(int x, int y) {
	for (int i = 0; i < 8; i ++) {
		int a = x + dx[i], b = y + dy[i];

		if (a < 1 || a > n || b < 1 || b > m) continue;

		if (g[a][b]) continue;
		
		if (st[a][b]) continue;
		
		st[a][b] = true;

		PII t = match[a][b];

		if (t.x == 0 || find(t.x, t.y)) {
			match[a][b] = {x, y};
			return true;
		}
	}
	return false;
}

int main() {
	std::cin >> n >> m >> k;

	for (int i = 0; i < k; i ++) {
		int x, y;
		
		std::cin >> x >> y;	

		g[x][y] = true;
	}	

	int res = 0;

	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			if ((i + j) % 2 || g[i][j]) continue;
			memset(st, 0, sizeof st);
			if (find(i, j)) res ++;
		}
	}

	std::cout << n * m - k - res;
}

最小路徑點覆蓋

? 針對一個有向無環圖, 用最少的互補相交的路徑（點不重復），將所有點覆蓋。

最小路徑重復點覆蓋

1. 先求傳遞閉包 \(G'\)， 原圖\(G\)的最小路徑重復點覆蓋=\(G’\)的最小路徑點覆蓋
2. 在\(G'\) 的最小路徑點覆蓋

捉迷藏

#include <bits/stdc++.h>

using i64 = long long;

const int N = 210, M = 30010;

int n, m;

bool d[N][N], g[N][N], st[N];

int match[N];

bool find(int x) {
	for (int i = 1; i <= n; i ++) {
		if (d[x][i] && !st[i]) {
			st[i] = true;
			int t = match[i];

			if (t == 0 || find(t)) {
				match[i] = x;
				return true;
			}	
		}	
	}

	return false;
}

int main() {
	std::cin >> n >> m;
	
	while (m --) {
		int a, b;
		
		std::cin >> a >> b;

		d[a][b] = true;		
	}	

	// 傳遞閉包

	for (int k = 1; k <= n; k ++)
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= n; j ++)
				d[i][j] |= d[i][k] & d[k][j];

	int res = 0;

	for (int i = 1; i <= n; i ++) {
		memset(st, false, sizeof st);

		if (find(i)) res ++;	
	}

	std::cout << n - res;
}