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](https://riteme.site/blog/2016-9-19/hall-theorem.html)。 ### 正则二分图 如果一个二分图中每个点的度数都是 $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$ 任意时的完美匹配 这是一个随机算法，随机在运行时间上。 算法如下： - 重复 $N$ 次： - 随机选一个左边的未匹配点，然后沿增广路随机游走（即从左往右随机走未匹配边，从右往左走匹配边），直到走到一个右边的未匹配点。 - 把走出来的环去掉（找到最后一个出现过多次的点，然后把第一次走到它到最后一次走到它中间的这段路砍掉）。这样就找到了一条增广路。对它进行增广以把匹配数增加 $1$。 它确实非常蠢。但是可以证明：当还剩下 $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$，有（从右往左只能走匹配边） $$b(y) = \begin{cases} 0 & y \in R_u \\ 1 + b(M(y)) & y \in R_m \end{cases}$$ 对于 $x \in L_u$，有 $$\begin{aligned} 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)$） $$\begin{aligned} 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$ 次。于是 $$\begin{aligned} 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}$$ 证毕。