Hall 定理

Hall 定理

完美匹配：设 (M) 是二分图 (G(V_1,V_2,E)(|V_1|le|V_2|)) 的一个匹配，若 (forall v_iin V_1,exist kin V_2,(v_i,k)in M)，则称 (M) 为 (G) 的一个完美匹配。

Hall 定理：对于一个二分图 (G(V_1,V_2,E)(|V_1|le|V_2|))，对于(forall Xsubseteq V_1)，定义 (N(X)={v_j|(v_i,v_j)in E,v_jin V_2,v_iin X})。其存在 (V_1) 的完美匹配的充要条件为 (forall Xsubseteq V_1,|X|le |N(X)|)。

证明：

必要性显然，因为一个点至少需要一个匹配点。下面证明充分性。

若一个二分图 (G) 不存在完美匹配，但满足 Hall 定理。

设其最大匹配为 (M)，其对应的点集为 (X,Y(|X|le |Y|))。

则一定可以从某个点 (v_i otin X) 出发，由于满足 Hall 定理，这条路一定能够遍历 (Y) 中的 (|X|+1) 个点，即我们找到了一条增广路。与 (M) 是最大匹配的假设矛盾。故得证。

推论：一个二分图的最大匹配大小为 (|V_1|-max_{S subseteq V_1}{|S|-|N(S)|})。

证明：事实上我们只需要证明 (max_{S subseteq V_1}{|S|-|N(S)|}) 为 (V_1) 中非匹配点的个数。

显然 (max_{S subseteq V_1}{|S|-|N(S)|}) 小于等于 (V_1) 中非匹配点的个数，则我们只需要证明能够取等。

考虑构造 (V_1) 的子集 (Q)，使 (max_{S subseteq V_1}{|S|-|N(S)|}=|Q|-|N(Q)|)。首先向其加入所有 (V_1) 中的非匹配点，若 (|N(Q)|=0)，则 (max_{S subseteq V_1}{|S|-|N(S)|}=|Q|-|N(Q)|)。

否则，(N(Q)) 中一定存在点在最大匹配中，我们将这些点在 (V_1) 的匹配点加入 (Q)。若加入后 (N(Q)) 的大小发生变化，那么新增的点仍然是最大匹配中的点（否则我们找到了一条增广路，与最开始非匹配点的假设矛盾） ，将这些新增点在 (V_1) 的匹配点加入 (Q)。

如此反复，一定能够构造出一个集合使得 (|Q|-|N(Q)|) 等于非匹配点的个数，因为每次 (Q) 与 (N(Q)) 都增加了同样的点数。

得证。

变符号可得 (|V_1|+min_{S subset V_1}{|N(S)|-|S|} iff |V_1|-max_{S subseteq V_1}{|S|-|N(S)|})。