Hall 定理的一个加强

描述

给定一张有完美匹配的二分图 $G=(L\cup R,E)$，满足 $|L|=|R|$ 且图连通。

判断是否图上每条边都属于某个完美匹配。

定理 1（Hall 定理的加强）

对于有完美匹配的二分图 $G=(L\cup R,E)$，满足 $|L|=|R|$ 且图连通，若对于 $L$ 的每个非空真子集 $S\subsetneqq L$，都有 $|N(S)|>|S|$。则 $G$ 是匹配覆盖的。

定理 1 证明

必要性

即现在每条边都已经属于某个完美匹配。首先 $G$ 有完美匹配。对于 $L$ 的一个非空真子集 $S$，先由 Hall 定理得 $|N(S)|\ge |S|$。

若上式取等。因为 $G$ 连通，存在 $v\in N(S)$ 与 $u^\prime\in L\setminus S$ 相邻。考虑一条边 $e=(u^\prime,v)$，要存在完美匹配包含 $e$，即要求在该匹配中 $v$ 匹配给 $u^\prime$，此时考虑集合 $S$ 就不存在完美匹配了，矛盾。

充分性

即满足 $|N(S)|>|S|$。考虑一条边 $e=(u,v)$，考虑子图 $G^\prime=G-\{u,v\}$，需证 $G^\prime$ 存在完美匹配。对于集合 $T\subseteq L\setminus \{u\}$，若在 $G^\prime$ 中有 $|N_{G^\prime}(T)|<|T|$，在原图中先由 Hall 定理得 $|N_G(T)|\ge |T|$。首先要 $v\in N_G(T)$，且 $|N_G(T)|=|T|$。只有当 $T$ 包含全部左部点时该条件成立，但有 $u\not\in T$，产生矛盾。故所有 $T$ 都满足 $|N_{G^\prime}(T)|\le |T|$，即 $G^\prime$ 存在完美匹配。

从而 $e=(u,v)$ 属于某个完美匹配。

判断

• $(u,v)$ 在初始完美匹配中，连边 $u\to v$。
• 否则，连边 $v\to u$。

拓展

若图 $G$ 的每条边都在一个完美匹配里，那么对于 $L$ 的每个非空真子集 $S\subsetneqq L$，都有

$$\sum\limits_{u\in S}c_u<\sum\limits_{v\in N(S)}s_v$$