Hall’s marriage theorem

组合形式

令 \(S\) 为一个（可能无穷）的可重集合，集合中的元素为有穷集合 \(X\) 的子集。定义 \(f(S)\) 表示从 \(\forall x\in S\) 中各取出一个代表元素组成的集合，这些代表元素两两不同。如果 \(f(S)\) 存在，我们称其满足婚配条件，其等价条件为：

\(\forall W\subseteq S, \displaystyle |W|\leq {\Bigl |}\bigcup _{A\in W}A{\Bigr |}\)

换言之，婚配条件断言了对任意的 \(W \subseteq S\) 它盖住了至少 \(|W|\) 个 \(X\) 的不同元素。

图论形式

\(G=(X+Y, E)\) 为一个有穷二分图。对于任意的 \(W\subseteq X\)，令 \(N_G(W)\) 表示它的邻点集（在二分图中同时也是 \(Y\) 的一个子集）。存在一个匹配覆盖 \(X\) 的充要条件为：

\(\forall W\subseteq X, \displaystyle |W|\leq {\Bigl |}N_G(W){\Bigr |}\)

换言之，对于 \(X\) 的任意子集 \(W\)，在 \(Y\) 中都有足够多的邻点。

例题

Pair

来源：LOJ 6062 (2017 山东一轮集训 Day2)

题目大意：

题解：tmp

Exhausted?

来源：AtCoder ARC 076 F

题目大意：

题解：tmp

Lyz

来源：BZOJ 1135 POI2009

题目大意：

题解：tmp

圆桌会议

来源：BZOJ 3693

题目大意：

题解：tmp

stone

来源：BZOJ 2138

题目大意：

题解：tmp

Buying Sets

来源：Codeforces 103E

题目大意：

题解：tmp