Conventions
我们约定 \(G=(V,E)\) 是一个标准的二分图,使用 \(V_1,V_2\) 来描述两侧的不同的集合,约定 \(V_1\cup V_2=V\) 且 \(\left\lvert V_1\right\rvert<\left\lvert V_2\right\rvert\)。
Theorem
一个二分图存在完备匹配的充要条件是对于左部点大小为 \(k\) 的任意子集 \(S\),这些点的邻域 \(N(S)\) 的大小不小于 \(k\)。
Proof
首先证明必要性,如果一个点集的 \(N(S)\) 不足 \(|S|\),那么该集合不能找到一个完备匹配,与定义相反。
然后证明充分性。考虑使用归纳,分为两种情况:
-
如果存在一个严格子集 \(S\) 满足 \(S=N(S)\),则子集本身存在完备匹配。
如果删去 \(S,N(S)\) 后出现不满足条件的集合 \(T\),那么在原二分图中取子集 \(S\cup T\),必然有 \(|N(S\cup T)|<|S\cup T|\),与假设矛盾。
那么由此证明如果存在 \(|S|=|N(S)|\),\(\text{Hall}\) 定理成立。
-
如果所有子集的 \(|N(S)|\) 均大于 \(|S|\),那么找到一个点 \(u\) 并找到 \((u,v)\in E\),删掉 \(u,v\in V,(u,*),(*,v)\in E\)。
不难发现此时剩下的二分图每个子集 \(S\) 都能满足 \(|N(S)|\geq |S|\),而且因为删掉了一个点,问题是原问题的子问题。
根据归纳假设,\(\text{Hall}\) 定理在此情况下也成立。