Hall婚配定理

Hall 婚配定理刻画二分图什么时候能给左侧每个对象分配一个彼此不同的右侧对象。本篇讨论有限二分图。设左侧顶点集为 $U$ ，右侧为 $V$ ， $N (S)$ 表示左侧子集 $S \subseteq U$ 的全部可连接右侧顶点，即把每个 $u \in S$ 的邻居取并集；一个右侧顶点只需连接其中至少一个左侧顶点，不要求连接所有人。存在覆盖 $U$ 的匹配，当且仅当 $| N (S) | \geq | S | (S \subseteq U) .$ 这不是只检查每个单独顶点至少有一条边；瓶颈可能出现在一群顶点上。

两人争一个位置

三个学生 $u_{1}, u_{2}, u_{3}$ 选项目。若 $u_{1}, u_{2}$ 都只能做项目 $a$ ，而 $u_{3}$ 可做 $b, c$ ，每个人虽然至少有选项，但集合 $S = {u_{1}, u_{2}}$ 的邻居只有 ${a}$ ，于是 $| N (S) | = 1 < 2$ ，不可能一人一项。把 $u_{2}$ 的选项增添 $b$ 后，可给 $u_{1} \mapsto a, u_{2} \mapsto b, u_{3} \mapsto c$ ；这时还需对所有子集检查条件，单一可行分配已直接证明存在。

二分图左侧u1和u2都只连接右侧a，左侧u3连接b和c，因此前两人的邻居集合只有一个位置 — Hall 条件检查一组左侧顶点的全部邻居，邻居集合取并集。

充分性的归纳证明

必要性很直接：若已有一一分配， $S$ 的每个人得到不同邻居，故 $N (S)$ 至少有 $| S |$ 个。充分性按有限整数 $| U |$ 归纳。若 $U$ 为空，空匹配已足够；若只有一个左侧顶点，条件保证它至少有一个邻居，直接配对即可。以下设 $| U | \geq 2$ 。若某个非空真子集 $S$ 恰有 $| N (S) | = | S |$ ，先对 $S$ 与 $N (S)$ 用归纳得到匹配；再删掉这两部分。余下左侧任意 $T$ 仍至少有 $| T |$ 个余下邻居，因为原条件对 $S \cup T$ 给至少 $| S | + | T |$ 个邻居，而被删的只有 $| S |$ 个。对余下部分再归纳即可。

若所有非空真子集都严格满足 $| N (S) | > | S |$ ，任选左侧顶点 $u$ 及一个邻居 $v$ ，先配对并删去它们。余下任意非空 $T \subseteq U ∖ {u}$ 的原邻居至少有 $| T | + 1$ 个，删 $v$ 后仍有 $| T |$ 个，再归纳。两种情况覆盖全部可能，证明完成。实际找匹配可用增广路或网络流与最大流最小割，定理的子集条件解释了算法失败时出现的瓶颈证书。

参考资料与相关词条

Lehman、Leighton、Meyer，Mathematics for Computer Science，§11.5，第401—405页，定理11.5.2/11.5.4：有限图约定、邻集定义及分两种情形的归纳证明。
MIT 18.315：Hall 婚配定理讲义。
相关：二分图、图论、网络流与最大流最小割。