霍尔定理

· · 算法·理论

0 简介

本文同步到洛谷博客。

霍尔定理（Hall's Theorem）是一个有关于二分图匹配的定理，本篇文章主要讲述了霍尔定理及其推广和证明。

定理的内容比较简单简洁，所以还是记一下。

注意：在本篇文章中，我们默认 G = \text{<}V,E{>} 是一个标准的二分图，我们使用 V_1, V_2 来描述两侧的不同的集合，我们默认 V_1 \cup V_2 = V，且|V_1| < |V_2|。

1 霍尔定理

霍尔定理声称

对于集合 V_1, V_2，若最大匹配的数量为 |V_1|，当且仅当对于任意的 S_1 \subseteq V_1 满足 |S_2| \geq |S_1|，其中 S_2 是与 S_1 中的点有边相连的点的集合。

1.1 证明

首先是必要性，这个很好证。假设 |S_2| < |S_1|，那么最大匹配数 x 一定小于等于 |S_2|，即 x \leq |S_2| < |S_1|，即 x < |S_1|。必要性得证。

接下来充分性，这回我们考虑使用归纳法，我们考虑 n = |S_1| 的情况。

当 n = 1 时显然成立。

我们在 S_1 中选取 k(k \neq n) 个满足霍尔定理的点，我们在这 k 个点中任意选择一组进行匹配，并把匹配的一对删去，此时便变成了 n - 1 的情况，根据归纳法的假设，是成立的。

所以充分性也证明完了，所以霍尔定理是正确的。Q.E.D.

2 Ex1-霍尔定理

霍尔定理可以进行推广，具体的：

对于集合 V_1, V_2，若最大匹配的数量为 |V_1| - a, (a < |V_1|)，当且仅当对于任意的 S_1 \subseteq V_1 满足 |S_2| - a \geq |S_1|，其中 S_2 是与 S_1 中的点有边相连的点的集合。

证明与普通的霍尔定理是类似的，这里留作课后思考题。

3 Ex2-霍尔定理

上面是霍尔定理的一种推广形式，我们还可以从另一个角度推广，具体的，我们先从二分图匹配开始，我们将原来的唯一对应改为 1 对 c（c 为常数）的形式，具体的，每一个 u \in V_1 都可以与 c 个 v \in V_2 对应，当与 u 匹配的 v 的数量为 c 时才算作一个匹配，换句话说，这种情况下的最大匹配的数量为 u 能与 c 个 v 匹配的 u 的数目。

此时霍尔定理声称：

在这种匹配方式下，对于集合 V_1, V_2，若最大匹配的数量为 |V_1|，当且仅当对于任意的 S_1 \subseteq V_1 满足 c|S_2| \geq |S_1|，其中 S_2 是与 S_1 中的点有边相连的点的集合。

3.1 证明

我们如何证明呢？考虑拆点，如果我们将每一个 V_1 中的每个点全部拆成 c 个点，我们发现命题转化成了普通的霍尔定理，此时我们便可以使用证明普通的霍尔定理的方式来证明了。

4 Ex2-2-霍尔定理

我们再对二分图匹配做推广，对于 u \in V_1 能够与 r_u 个点匹配，最大匹配的数量的定义也类似的推广。

此时的霍尔定理声称：

在这种匹配方式下，对于集合 V_1, V_2，若最大匹配的数量为 |V_1|，当且仅当对于任意的 S_1 \subseteq V_1 满足 |S_2| \geq \sum_{i \in S_1}r_i，其中 S_2 是与 S_1 中的点有边相连的点的集合。

此时的证明与Ex2类似，只不过是把点 u \in V_1 拆成 r_u 个罢了。

差不多就这么多了。

可能的参考文献：https://www.zhihu.com/tardis/zm/art/460373184?source_id=1005，但是年代久远我也不记得是不是这篇了。