Hall 定理；正则二分图的完美匹配

· · 个人记录

Hall 定理

给定一个二分图，我们记 L, R 分别为其两边的点。对于 S \subseteq L，我们令 N(S) 表示直接连到 S 的所有右边的点。

如果对任意 S \subseteq L，都有 |N(S)| \geq S，那么最大匹配数为 |L|（即左边的每个点都能被匹配上）。特别的，如果 |L| = |R|，则此时存在完美匹配。

注意到这个条件显然是充要条件，因为存在完美匹配时对每个 S \subseteq L，只是与 S 匹配的点就也有 |S| 个；与 S 直接相连的点肯定更多。

证明概要：对点数归纳。如果存在一个子集 T \subseteq L 使得 |N(T)| = |T|，那么不难证明整张图去掉 T 和 N(T) 中的点之后仍然满足 Hall 条件。（并且显然 T 和 N(T) 中的点单独拿出来满足 Hall 条件）。所以这样就拆成了两个点数更小的问题。

如果不存在这样的 T，那么我们随便从二分图里面删边，直到它存在为止。可以证明在此之前不会破坏 Hall 条件。

证明参考了 这篇 blog。

正则二分图

如果一个二分图中每个点的度数都是 k，那么称作一个 k-正则二分图。

显然一个正则二分图左右两边点数相同（因为边数 = k|L| = k|R|）。下面以 N 指代 |L|（或 |R|）。

如果 S \subseteq L，那么连到 S 的边有 k|S| 条，连到 N(S) 的边有 k|N(S)| 条。由于前者是后者的子集，我们就有 |S| \leq |N(S)|。

所以正则二分图满足 Hall 定理的条件，其必定存在完美匹配。

k=2^d 时的完美匹配

如果给定一个 2^d-正则二分图，如何找出其一个完美匹配？

这个算法很容易：直接找出一条欧拉回路，这样就给所有边定了向；且每个点出度入度相同。删掉某一个方向的所有边，然后忽略掉定向，就变成了 2^{d-1}-正则二分图。递归直到 d=0 即可。

复杂度为 2^dN+2^{d-1}N+\dots+N = O(2^dN)，也就是 O(边数)，不能再快了。

k 任意时的完美匹配

这是一个随机算法，随机在运行时间上。

算法如下：

它确实非常蠢。但是可以证明：当还剩下 2T 个未匹配点（即重复过 N-T 次）时，随机游走的步数期望是

2\frac{(N-T)(k-1)}{kT}+1

这个东西直接放缩成 \frac{2N}{T}，所以期望复杂度是

O\left(\sum_{T=1}^N \frac{2N}{T}\right) = O(N\log N)

非常神奇。

上述算法的证明

我们要证明的是：如果有一个 k-正则二分图，两边分别有 N 个点，任意给定一个大小为 M-T 的匹配，在其基础上随机增广，则期望步数为

2\frac{(N-T)(k-1)}{kT}+1

或者说，期望需要从右往左走 \frac{(N-T)(k-1)}{kT} 次。

令 b(v) 表示从 v 开始随机增广，期望需要从右往左走多少次。

记：L_m,R_m 表示左右两边的已匹配点；L_u,R_u 表示左右两边的未匹配点。如果 v \in L_m 或 v \in R_m，记 M(v) 为当前其匹配的点。

那么直接计算期望。对于 y \in R，有（从右往左只能走匹配边）

0 & y \in R_u \\ 1 + b(M(y)) & y \in R_m \end{cases}

对于 x \in L_u，有

b(x) &= \frac{1}{k} \sum_{y \in N(x)} b(y) \\ \implies kb(x) &= \sum_{y \in N(x)} b(y) \end{aligned}

对于 x \in L_m，有（注意到 b(M(x)) = 1 + b(x)）

b(x) &= \frac{1}{k-1} \left(\sum_{y \in N(x)} b(y) -b(M(x))\right)\\ \implies (k-1)b(x) + b(M(x)) &= \sum_{y \in N(x)} b(y) \\ \implies kb(x) &= \sum_{y \in N(x)} b(y) - 1 \end{aligned}

把上面两个合起来，注意到这是一张 k 正则二分图，所以上面两个式子对 x 求和之后每个 y 也恰好出现了 k 次。于是

k\sum_{x \in L} b(x) &= k\sum_{y \in R} b(y) - M \\ k\sum_{x \in L} b(x) &= k\sum_{y \in R_m} (b(M(y))+1) - M \\ k\sum_{x \in L_m} b(x) + k\sum_{x \in L_u} b(x) &= k\sum_{x \in L_m} b(x) + kM - M \\ k\sum_{x \in L_u} b(x) &= (k-1)M \end{aligned}

由于我们最开始的时候是从 L_u 中随机选一个点 X 开始增广，所以期望往左走的次数即为

\frac{1}{T}\sum_{x \in L_u} b(x) = \frac{(k-1)M}{kT} = \frac{(k-1)(N-T)}{kT}

证毕。