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)\)，若：

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

若 \(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)\)。