Hall定理在效应中扮演什么角色？

前置定义 对于一个图 \((V, E)\) 和它的一个匹配 \(M\)，存在着如下两种简单路径： 由非匹配，匹配边交错构成的简单路径为交错路。 起点为非匹配点且终点也为非匹配点的交错路为增广路。 对于任何一个节点的子集 \(W \subseteq V\)，称集合 \(N_G(W)\) 表示图 \(G\) 中与 \(W\) 相邻（相邻指两点间存在边）的点构成的集合。 Berge 引理 Berge 引理：对于一个图 \(G = (V, E)\) 和它的一个匹配 \(M\)，该匹配是最大匹配，当且仅当不存在增广路。 先证明必要性： 反证法，若存在一个增广路。 首先，因为增广路是 \(非匹配边 \to 匹配边 \to \cdots \to 非匹配边\) 这种形式的，所以长度必然是奇数。 所以可以得到这个路径上非匹配边的数量是匹配边的数量 \(+1\)。 所以我们考虑翻转整个路径的状态，即 \(匹配 \to 非匹配, 非匹配 \to 匹配\)。 容易发现此时的匹配是合法的，且匹配数比原来多了 \(1\)，与 \(M\) 是最大匹配矛盾。 然后考虑充分性： 同样反证法，在不存在增广路的前提下，若存在另外一个匹配 \(M'\) 使得 \(|M'| > M\)。 考虑对称差新的匹配 \(M \oplus M'\)，即相同的边将会抵消的运算。 在这个新图 \((V, M \oplus M')\) 上，容易发现，每个点的度数只能是 \(0, 1, 2\)，所以对于这个新图，其所有联通块，要么是一条链，要么是一个环。 容易发现一个性质，对于一个度数为 \(2\) 的点，其相邻的边必定是分别来自 \(M\) 和 \(M'\)；且在这个新图上，不可能存在奇环；于是可以得到对于每个环，都是偶环，且 \(M\) 和 \(M'\) 中的边出现次数一样。 那么此时来考虑链，显然肯定是由 \(M, M'\) 中的边交替构成的，即构成交替路，对于 \(M'\) 中的边，在 \(M\) 中是非匹配边。 由于 \(|M'| > M\)，那么显然必然会出现一个起点终点都是非匹配点的链，其是增广路，与 \(M\) 不存在增广路矛盾。 König 定理 König 定理：对于任意一个图 \(G\)，其的最大匹配数量等于其最小点覆盖数。 设 \(M\) 是 \(G\) 中的一个最大匹配；要覆盖 \(E\) 中的边，首先要覆盖 \(M\) 中的每条边，需要选择其的两个端点之一才可以覆盖它，因为是匹配，这些端点互不相同，于是显然最小点覆盖数 \(\ge |M|\)。 考虑构造一个点覆盖大小恰好是 \(|M|\)： 从 \(M\) 中的每一条边选择一个端点组成集合 \(U\)：考虑边 \((x, y)\)，如果存在一条终止于 \(y\) 的交错路，那么选择 \(y\)，否则选择 \(x\)。 现在考虑证明 \(U\) 是一个点覆盖集。 考虑 \(E\) 中的任意边 \((a, b)\)，如果 \(a \in U\)，那么必然被覆盖了；那么我们证明，当 \(a \not\in U\) 时，必然有 \(b \in U\)，即存在一个交错路终止于 \(b\)： 若 \(a\) 没有被任何顶点匹配：那么显然 \(ab\) 就是交错路。 否则找到 \(a\) 的匹配点 \(b'\)：因为 \(a \not\in U\)，所以 \(b' \in U\)，所以存在到 \(b'\) 的交错路 \(P\)，如果 \(b\) 就在 \(P\) 中，那么必然存在到 \(b\) 的交错路；否则 \(Pab\) 是到 \(b\) 的交错路。 于是得证。 Hall 定理 对于一个二分图 \((X, Y, E)(|X| \le |Y|)\)，若存在一个匹配 \(M\) 使得使得 \(X\) 中所有顶点都是匹配点，那么称 \(M\) 是一个完美匹配。 Hall 定理：假设 \(G\) 是一个二分图 \((X, Y, E)\)，存在一个完美匹配当且仅当对于所有 \(W \subseteq X\) 都满足 \(|N_G(W)| \ge |W|\)。 先证明必要性： 若存在完美匹配，且存在 \(W\) 使得 \(|N_G(W)| < W\)，显然这 \(|W|\) 点无法和少于它们点数的集合形成完美匹配，故矛盾。 然后考虑充要性： 考虑反证法，即对于所有 \(W \subseteq X\) 都满足 \(|N_G(W)| \ge |W|\)，且存在一个点 \(u \in X\) 是非匹配点，由 Berge 引理得到，即无法找到一个从 \(u\) 出发的增广路。