Hall 定理;正则二分图的完美匹配
_rqy
2021-01-03 03:00:49
### 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}$$
证毕。