图的匹配与网络流
1 图的匹配
1.1 匹配基础知识
1.1.1 匹配的定义
对于一个无向图 \(G = (V,E)\)，定义一个集合 \(M \sube E\) 是这张图的一个匹配当且仅当对于不存在 \(u,v,w \in V\) 使得 \((u,v) \in M\) 且 \((u,w) \in M\)。
一个匹配的大小定义为所含边数的多少。
最大匹配指一张图中最大的匹配。
考虑到一般图的匹配比较难，我们一下讨论的都是二分图的匹配。
定义一个二分图 \(G=(X,Y,E)\)。
1.1.2 增广轨
对于一个匹配 \(M\)，如果存在一条路径满足：
-
起点和终点均是未匹配点。
-
路径上的边恰好为 \(\not\in M, \in M, \not\in M ... \not\in M\) 这样交错的。
这条路径称为当前匹配下的一条增广轨。
1.1.3 交错轨
交错轨只要求起点未匹配，终点任意。
1.2 最大匹配算法
1.2.1 最大匹配与增广轨
定理： 一个二分图 \(G\) 的匹配 \(M\) 不存在增广轨 \(\iff\) \(M\) 是最大匹配。
证明：
如果存在一条增广轨 \(P\)，则 \(M \oplus P\) 将会是原匹配多一的匹配，得证。
如果 \(M\) 没有增广轨，我们要证明它是最大匹配。
假设 \(M\) 不是最大匹配，不妨设 \(M^*\) 是一个最大匹配。
令 \(T = M \oplus M^*\)，由于匹配中每个点度数不超过 \(1\)，所以 \(T\) 中点度数不超过 \(2\)，说明 \(T\) 是由若干个环和路径组成的。
如果一个点有两条邻边，则这两条显然一条属于 \(M\)，一条属于 \(M^*\)。
如果是环，则两个集合中的边数量相等，由于 \(|M| < |M^*|\)，说明剩下的路径中，一定有一条路径 \(M^*\) 中的边更多，这说明这条路径是一条增广轨，和假设矛盾！所有定理得证。
1.2.2 朴素最大匹配算法
寻找增广轨
为了寻找 \(M\) 的增广轨，我们可以先找到其所有交错轨，进而找到增广轨。
我们初始是一个空集 \(S\)，然后对其进行扩展：
-
将 \(X\) 所有未匹配点全部加入 \(S\) 中。
-
重复以下操作知道不能进行：取出 \(S\) 中还未处理的 \(X\) 中的点 \(x\)，找到所有 \((x,y) \in E,(x,y) \not\in M\) 的 \(y\)，将 \(y\) 加入 \(S\)，并将所有的 \((y,z) \in E,(y,z) \in M\) 的 \(z\) 加入 \(S\)。
如果第二步时某一时刻 \(y\) 未被匹配，说明我们找到了一条以 \(y\) 结尾的增广轨，否则不存在。
最终算法
我们可以不断找到增广轨，然后更新匹配，直到最大匹配。由于最大匹配至多为 \(n\)，而找一次增广轨按照上面的做法是 \(O(m)\) 的一次 bfs，所以总时间复杂度是 \(O(nm)\) 的。
这里以 P3386 【模板】二分图最大匹配 洛谷模板题为例。
点击查看代码
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 505;
int n, m, E;
vector<int> e[N * 2];
int mch[N * 2] = {0}, p[N * 2] = {0};
bool vis[N * 2] = {false};
bool bfs() {//找增广轨
queue<int> q;
for (int i = 1; i <= n + m; i++) {
vis[i] = false, p[i] = 0;
if (mch[i] == 0 && i <= n)
q.push(i), vis[i] = true;
}
while (!q.empty()) {
int h = q.front();
q.pop();
for (auto i: e[h]) {
if (p[i] != 0)
continue;
p[i] = h;
if (mch[i] == 0) {
int j = i;
while (j != 0)
mch[j] = p[j], swap(mch[p[j]], j);
return true;
}
if (!vis[mch[i]])
vis[mch[i]] = true, q.push(mch[i]);
}
}
return false;
}
int main() {
cin >> n >> m >> E;
for (int i = 1, u, v; i <= E; i++) {
cin >> u >> v;
e[u].push_back(v + n);
e[v + n].push_back(u);
}
while (true) {
if (!bfs())
break;
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans += (mch[i] != 0);
cout << ans << endl;
return 0;
}
1.2.3 匈牙利算法
1.2.4 Hopcroft-Karp 算法
1.3 最大独立集与最小点覆盖
1.3.1 最大独立集
对于一个集合 \(V^* \sube V\)，如果满足 \(\forall (u,v) \in E, u \not \in V^*\) 或 \(v \not \in V^*\)，则 \(V^*\) 称为独立集。
最大的独立集称为最大独立集。
1.3.2 最小点覆盖
对于一个集合 \(V^* \sube V\)，如果满足 \(\forall (u,v) \in E, u \in V^*\) 或 \(v \in V^*\)，则 \(V^*\) 称为覆盖集。
最小的覆盖集称为最小点覆盖。
1.3.3 二者关系
定理： 独立集的补集是覆盖集，覆盖集的补集是独立集。
证明：
独立集的补集不是覆盖集说明有一条边两个端点都是独立集，显然不对。
覆盖集的补集不是独立集说明有一条边两个端点都不是覆盖集，显然不对。
然后就证完了。
推论： 最大独立集的补集是最小覆盖集。
1.4 匹配中的重要定理
1.4.1 Hall's 定理
定理： 对于一个二分图 \(G\)，存在大小为 \(|X|\) 的完美匹配 \(\iff\) \(\forall A \sube X, |N(A)| \ge |A|\)。其中 \(N(A)\) 指 \(A\) 的邻域。
证明：
考虑证明逆否命题：不存在完美匹配 \(\iff\) 不满足 \(|N(A)| \ge |A|\)。
首先，如果存在 \(|N(A)| < |A|\)，则一定不存在完美匹配，这个显然。
我们现在要证明如果不存在完美匹配，一定存在 \(|N(A)|<|A|\)。
我们需要借用 1.2.2 朴素增广轨算法中的扩展集合 \(S\) 来证明。
考虑将点集分成四个部分，分别是 \(S_x = X \cup S, S_y = Y \cup S, T_x = X \cup \overline{S},T_y = Y \cup \overline{S}\)。
首先，根据 \(S\) 的定义，我们可以推断出，\(S_x\) 与 \(T_y\) 中的点没有任何形式的边。
如果存在一条未匹配边，则按照扩展规则 \(T_y\) 中的那个点应该属于 \(S\)，矛盾！
如果存在一条匹配边，考虑扩展过程，\(S_x\) 中的那个点显然已经匹配，要想进入 \(S\) 必然是由 \(T_y\) 那个点带进来的，但是 \(T_y\) 不在 \(S\) 中，矛盾！
所以我们知道 \(N(S_x) \sube S_y\)，我们现在只用证明 \(|S_x| > |S_y|\) 即可。
考虑所有 \(S_x\) 的匹配边，显然都匹配了 \(S_y\)，根据扩展规则，\(S_y\) 中所有点都被匹配了，而 \(S_x\) 肯定由为匹配点（否则 \(S\) 初始就是空的），说明 \(|S_x| > |S_y|\) 进而定理得证。
1.4.2 Konig 定理
定理： 二分图最小点覆盖等于最大匹配。
证明：
记最小点覆盖是 \(VC\)，最大匹配是 \(MM\)。
首先，我们可以证明 \(|MM| \le |VC|\) 因为如果 \(|VC| < |MM|\)，显然会有一条边未被覆盖，否则最大匹配的最大性就不能保证了。
我们尝试证明 \(|MM| \ge |VC|\)，考虑构造一个点覆盖等于 \(|MM|\)。
依然需要用到集合 \(S\)，我们考虑分成四个集合。
上一个定理的证明中，我们已经证明 \(S_x\) 与 \(T_y\) 无边，现在我们证明 \(S_y\) 与 \(T_x\) 中不存在匹配边。
由于 \(S\) 的扩展规则，如果存在匹配边，显然会加入 \(S\)，与 \(T_x\) 不在 \(S\) 中矛盾！
我们也已经证明过，\(S_y\) 中的所有点都匹配了，这个也是由于 \(S\) 的扩展规则，同理，\(T_x\) 中所有点都匹配了，否则会在一开始就加入 \(S\)。
也就是说，\(|MM| = |S_y| + |T_x|\)，我们将 \(S_y\) 与 \(|T_x|\) 中所有点全部选取，便可以构成一个大小为 \(|MM|\) 的点覆盖，所以 \(|VC| \le |MM|\) 定理得证。
1.4.3 定理的简单应用
K 阶图
问题： 给定一个二分图，顶点度数都为 \(K\)，求证：存在完美匹配。
证明：
我们任意选取一个 \(X\) 的子集 \(A\)，根据 Hall's 定理，只需证明 \(|N(A)| \ge |A|\)。
考虑如果 \(|N(A)| < |A|\)，由于总边数是 \(|A|K\)，根据鸽笼原理，\(N(A)\) 中一定存在一个点度数大于 \(K\)，矛盾！于是原命题得证。
推论： 一个度数都为 \(K\) 的图是由 \(K\) 个完美匹配组成。
拉丁方填数
问题： 填一个 \(n \times n\) 的拉丁方（即每一行每一列都是 \(1 \sim n\) 的排列），求证：如果填完了前 \(K\) 行不互相矛盾，则一定可以合法的填完这个拉丁方。
证明：
我们只用证明可以填下一行即可，将数字看成左边点，位置看成右边点，可以填的数字连边，发现每个点度数相同，根据上一个题的结论可以证明存在完美匹配。
兰道定理
问题： 求证：\(n\) 个点的竞赛图存在 \(\iff\) 比分序列 \(s_1,s_2, \dots, s_n\) 满足 \(\forall k, \sum_{i=1}^k s_i \ge \binom{k}{2}\)。
证明：
1.5 匹配相关例题
P2764 最小路径覆盖问题
考虑建图，将一个点 \(i\) 的出点拆成 \(u_i\)，如入点拆成 \(v_i\)，一条边 \((x,y)\) 等价于连一条 \(u_x\) 到 \(v_y\) 的边。显然这是个二分图，不难发现这个二分图的最大匹配与一种路径覆盖一一映射，所以答案就是总点数减去最大匹配。
POJ2594 Treasure Exploration
和上道题类似，但是这道题不要求点不相交，可以先求出闭包，然后再在闭包上跑上一个题。
POJ3216 Repairing Company
依然是路径覆盖，求出最短路，如果最短路时间够就连边，然后跑最大匹配。
SGU190 Dominoes
水题，棋盘是二分图，直接求匹配即可。