Hall 婚配定理

Hall 条件检查每一组左侧需求者是否拥有足够多的联合候选。单个顶点度数大并不够，因为许多人可能挤在同一小批候选上；真正的瓶颈由某个子集 $S$ 与其邻集 $N(S)$ 的基数公理库基数Cardinality · Size of a set忽略元素性质与排列，只用双射和单射刻画集合的大小及其比较。差暴露。定理的力量在于证明除此之外没有隐藏障碍：所有局部容量不亏损便能拼成全局一一匹配。

若三个学生的可选导师总共只有两位，则取这三个学生为 $S$ 即违反条件。只检查每个左顶点度数至少 $1$ 不足够，因为多人可能只有同一个邻居。定理保证饱和指定的 $L$ 侧；只有当 $|L|=|R|$ 时，这样的匹配才同时完美饱和两侧。

设左侧 $L=\{a,b,c\}$，邻集分别为 $N(a)=\{1,2\}$、$N(b)=\{1,2\}$、$N(c)=\{2,3\}$。每个子集都满足 $|N(S)|\ge |S|$，例如全体邻集有三个点，因此存在完美覆盖左侧的匹配，如 $a\mapsto 1,b\mapsto 2,c\mapsto 3$。若把 $c$ 的邻集也改为 $\{1,2\}$，则 $S=L$ 只有两个候选，Hall 见证立即说明不可能。

在二分图公理库二分图Bipartite graph顶点可分成两个独立侧、且每条边都跨越两侧的有限简单无向图。中，Hall 条件等价于存在覆盖指定一侧的匹配公理库匹配Matching in a graph由彼此不共享端点的边组成、表达一对一配对约束的边集合。。它可证明有限集合代表系、拉丁方的部分构造和任务—资源分配；它的“缺口”推广还能导出最大匹配大小公式，并连接拟阵中的横截结构。结合Kőnig 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。，匹配障碍又可由最小顶点覆盖公理库顶点覆盖Vertex cover与图中每条边至少一个端点相交、从而覆盖全部边的顶点子集。刻画。算法上，增广路正是在修复当前匹配对某个邻集容量的占用，网络流则提供了另一种统一的求解视角。