Hall 定理
泛化ψ(｀∇´)ψ
这东西和 Dilworth 一样是组合数学的工具。
不过在 OI 的图论中的应用更广泛就是了。
内容ψ(｀∇´)ψ
Hall 定理描述了一个二分图 \(G\) 存在完美匹配的充要条件。
二分图的完美匹配是指，包含了所有点的一个匹配。
我们记左部为 \(L\)，右部为 \(R\)。
那么对于 \(\forall S \subseteq L\)，如果有 \(|S| \le |N_G(S)|\)。
那么存在一个 \(L\) 完美匹配（\(L\) 中的所有点都被包含）。
同时说明最大匹配数 \(= |L|\)。
如果 \(|L| = |R|\) 则说明 \(G\) 存在完美匹配。
注意，以上所有条件都是充要的！
一个有趣的事情是，König 定理，Dilworth 定理，Hall 定理，他们之间是有紧密的联系的（可以相互推出）
最后更新:
August 19, 2023