「Algorithm」Hall定理 | hk

Hall定理学习笔记

Brief Introdutcion

Hall 定理是二分图匹配的一个定理，用于判断二分图是否存在完美匹配

似乎它通常会作为一个工具和其他算法相结合，但是目前网络流水平还太差，没做过什么题。。。

设二分图中，设表示与中的点相邻（有边相连）的点集

$G$ 中存在完美匹配当且仅当对于任意点集 $S\subset V_1$ ，都有 $|M(S)|\ge |S|$

换句话来说，在左边任选 $k$ 个点，在右边与它们相邻的点至少有 $k$ 个

连出去的边数都不足点数，显然匹配不了

考虑反证

假设存在一个满足Hall定理的二分图，且不存在完美匹配

那么左边肯定存在一个未匹配的点 $x$ 。根据Hall定理，它至少和右边的一个点 $y$ 有连边

若 $y$ 没匹配过，那显然 $x$ 和 $y$ 可以匹配，矛盾
若 $y$ $y$ 匹配了，设 $y$ $y$ 和左边的 $z$ $z$ 点匹配，根据Hall定理，点集 $\{x, y\}$ ${x, y}$ 与右边至少有两个点有连边，假设除了 $y$ $y$ 之外的那个点为 $p$ $p$
- 若 $p$ 没匹配过，
- 若 $p$ 匹配了，

如此反复，就能找到一条增广路了，于是矛盾