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\) 不存在增广路矛盾。

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\) 出发的增广路。
我们令 \(W\) 表示 \(u\) 走交错路能到达的顶点集合，设 \(W\) 中左部点是 \(S\)，右部点是 \(T\)，由于从 \(u\) 必然是非匹配边出发，则最后回到左部点时一定是匹配边，即 \(S\) 中除了 \(u\) 都是匹配点；对于右部点，若存在一个点 \(v\) 是非匹配点，那么 \(u \to v\) 的交替路就是增广路，矛盾，故 \(T\) 中也全是匹配点。
由于 \(S\) 中除了 \(u\) 与 \(T\) 都是通过边相连的，又全是匹配点，于是两两一一对应，故 \(|S| - 1 = |T|\)；此时注意到必然有 \(T \subseteq N_G(S)\)，故 \(|T| \le |N_G(S)|\)；然后又可以发现 \(N_G(S)\) 中必然全是匹配点，因为如果存在非匹配点的话，可以从 \(u\) 开始走到那个非匹配点形成增广路形成矛盾，于是可以得到 \(N_G(S) = T\)。
于是 \(|N_G(S)| = |T| < |S|\)，与初始条件矛盾。

推论 1：

一个任意二分图 \((X, Y, E)(|X| \le |Y|)\)，其最大匹配数是 \(|X| - \max\limits_{W \subseteq X}(|W| - |N_G(W)|)\)。

考虑转化为 \(\min\limits_{W \subseteq X}(|X| - |W| + |N_G(W)|)\)。
然后对于求最大匹配问题，可以进行网络流的建模，然后跑最大流，也就是最小割，而上面式子的意义就是 \(|X| - |W|\) 是左边割掉的点，\(|N_G(W)|\) 是右边割掉的点，那么取 \(\min\) 就是最小割。
得证；当然这个还可以不用最小割来理解，感兴趣的可以自己上网查一下。
例题

P3488 [POI 2009] LYZ-Ice Skates

发现只需要判断是否存在完美匹配，于是考虑使用 Hall 定理。
此时发现 \(W \subseteq S\) 的情况太多了，但是你会发现，若 \(W = \{ a_1, \cdots, a_k\}\) 时，只需要 \(W = \{a_1, a_1 + 1, \cdots, a_{k}\}\) 满足条件就必然满足，于是只需要对于所有区间 \(W = [l, r]\)，满足 \(|N_G(W)| \ge |W|\) 即可，即：

\[\sum_{i = l}^r s_i \le (r - l + 1 + d) k\]
转化一下：

\[\sum_{i = 1}^r (s_i - k) \le dk\]
于是只需要判断 \((s_i - k)\) 的最大子段和是否大于 \(dk\) 即可。
于是问题转化为单点加，全局最大子段和，使用线段树维护即可，时间复杂度为 \(O(N \log N)\)。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！