二分图匹配 — 霍尔定理

霍尔定理：

一张左右部点分别为 \(V_1,V_2\) 的二分图存在完美匹配，当且仅当：

对任意 \(S\subseteq V_1\)，有 \(|S|\le |M(S)|\)，其中 \(M(S)\) 为所有与 \(S\) 中点有边相连的点集。

不失完备性的，我们默认二分图的左部点个数不大于右部点个数。

证明：

首先，必要性显然，否则必然不可能是完美匹配，那么考虑证明充分性，而充分性等价于：

一张满足霍尔定理的二分图 \(V_1,V_2\) 中，不存在任何左部点集中的点不在最大匹配中。

我们考虑反证，即如果二分图 \(V_1,V_2\) 满足霍尔定理，且存在一点 \(u\in V_1\) 不在最大匹配中，则：

首先，由霍尔定理，这个点有至少一条出边，我们找到该出边的端点 \(v\)。

此时，如果 \(v\) 不在最大匹配中，则将 \(u\leftrightarrow v\) 加入匹配会使匹配大小变大，这与最大匹配的前提矛盾；

那 \(v\) 一定在最大匹配中，我们找到与其匹配的点 \(u_2\)。

又由霍尔定理，我们有 \(|M(\left\{ u,u_2 \right\})|\ge|\left\{ u,u_2 \right\}|\)，则我们可以再次顺着新边找到一个新点 \(v_2\)。

我们对 \(v_2\) 进行与 \(v\) 类似的分类讨论，最后要么得出矛盾，要么能继续找到一个新点 \(v_3\)，

我们再对 \(v_3\) 进行分类讨论，如此往复，由于二分图点数有限，总有一次我们会推出矛盾，

而此时我们也就证明了，不存在满足霍尔定理且不存在完美匹配的二分图，即我们要的充分性。

其实还有更严谨的叙述，简要纲领如下。

考虑存在左部点集 \(S\subseteq V_1\)，满足：

1. \(|S|\le|M(S)|\)；
2. \(S\) 与 \(M(S)\) 中分别存在一点 \(u,v\) 不在最大匹配中，

否则最大匹配就是完美匹配，或者二分图不满足霍尔定理。

考虑证明，此时的匹配不是最大匹配，因为我们一定能构造出一条以 \(u\) 为起点，\(v\) 为终点的增广路。