Hall 定理的一个加强

· · 算法·理论

描述

考虑如下问题：

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

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

我们称满足以上条件的图是匹配覆盖（matching-covered）的。

我们可以枚举每条边 e=(u,v)，要满足在该完美匹配中是将 v 分配给 u，相当于删掉 e,u,v，然后可以暴力判断是否还存在完美匹配。

定理 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) 属于某个完美匹配。

判断

现在，给定一张连通图 G=(L\cup R,E)，判断该图是否匹配覆盖。

首先，通过匈牙利算法或者网络流，我们可以先判断并求出一个完美匹配，我们称其为初始完美匹配。

接下来，我们按照如下方式建出有向图 G^\prime，对于 G 中的一条边 e=(u,v)，若：

若 G 是匹配覆盖的，要满足在对 G^\prime 进行 SCC 缩点过后只存在一个 SCC。

对于一条不在初始完美匹配的边，我们可以找到一条交错路，反转该路上的边，就可以将那条边放到完美匹配中了。

时间复杂度 O(n\sqrt{n})，假设 n,m 同阶，瓶颈在于求完美匹配。

拓展

给定一张二分图 G(L\cup R,E)，其中左部点有流量 c_i，右部点有流量 s_i，满足 \sum c_i=\sum s_i。询问是否存在一种给每条边 e=(u,v) 分配流量 f_{u,v} 的方案满足 c_u=\sum\limits_{v\in N(u)}f_{(u,v)} 和 s_v=\sum\limits_{u\in N(v)}f_{(u,v)}。

我们称满足上述条件的一种流量的分配方式为该图的一个完美匹配，若一条边 e=(u,v) 满足 f_{(u,v)}>0 则称 e 是在完美匹配里的。

对于这样的图，我们也有类似的结论：

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

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

我们同样称满足上述条件的图是匹配覆盖的。

同样也存在类似的判断方式来判断一个图是否匹配覆盖，由于这不是单位容量二分图，所以找完美匹配的时间复杂度为 O(n^2m)。