Hall 定理 学习笔记

· · 算法·理论

二分图 Hall 定理

模型概述

给定一张二分图 G=(U_1, U_2, E)，其中：

在这张二分图中，求是否存在如下完美匹配，满足 U_1 中的所有顶点都是匹配点 ^{[1]}。

Hall 定理

对于上述问题，Hall 定理给出了存在完美匹配的充要条件。

1. 内容

Hall 条件

对于任意 U 的子集 S \subseteq U，记 N(S)表示 S 的邻域 ^{[2]}，那么存在完美匹配的充要条件为：

\forall S \subseteq U，|N(S)|\ge|S|

Hall 定理

在二分图 G=(X, Y, E) 中，存在一个完美匹配的充要条件是Hall 条件成立。

2. 证明

2.1 必要性证明

必要性是显然的。如果存在匹配 M 覆盖 X，那么对于任意 S \subseteq X，S 中的每个顶点在 M 下都匹配到 N(S) 中一个不同的顶点。因此，N(S) 中至少要有 |S| 个不同的顶点，即 |N(S)| \geq |S|。

2.2 充分性证明：

考虑使用归纳法。

我们通过对 |X| = n 进行归纳，证明 Hall 条件足以保证匹配的存在。

归纳基础 (n=1)

当 |X|=1 时，设 X = \{x\}。由 Hall 条件，|N(\{x\})| \geq 1，故存在 y \in Y 与 x 相邻。边 (x, y) 即构成覆盖 X 的匹配。

归纳假设

假设对于所有满足 Hall 条件的二分图，只要其左部顶点数 |X| < n，则一定存在匹配覆盖 X。

归纳步骤

考虑一个满足 Hall 条件且 |X| = n 的二分图 G = (X, Y, E)。我们分两种情况讨论：

情况 1：存在非平凡子集 S 使 |N(S)| = |S|。

假设存在 S \subset X，S \neq \varnothing，S \neq X，且：

|N(S)| = |S|

  1. 考虑子图 G_1：由 S 和 N(S) 及它们之间的边构成：

    • 对任意 S' \subseteq S，N_{G_1}(S') = N_G(S')。
    • 由原图 Hall 条件，|N_{G_1}(S')| \geq |S'|，故 G_1 满足 Hall 条件。
    • 因 |S| = k < n，由归纳假设，存在匹配 M_1 覆盖 S。

  2. 考虑子图 G_2：由 T = X \setminus S 和 R = Y \setminus N(S) 及它们之间的边构成：

    • 需验证 G_2 满足 Hall 条件。
    • 任取 T' \subseteq T，设 N_{G_2}(T') 为 T' 在 G_2 中的邻域。
    • 在原图 G 中：N(S \cup T') = N(S) \cup N_{G_2}(T')，且这两个集合不相交。
    • 由原图 Hall 条件：|N(S \cup T')| \geq |S| + |T'|，得：|N(S)| + |N_{G_2}(T')| \geq |S| + |T'|。
    • 代入 |N(S)| = |S|，得 |N_{G_2}(T')| \geq |T'|，所以 G_2 满足 Hall 条件。
    • 因 |T| = n-k < n，由归纳假设，存在匹配 M_2 覆盖 T。

  3. 合并匹配：由于 G_1 与 G_2 顶点集不相交，M_1 与 M_2 的边也不相交：

    M = M_1 \cup M_2

    即为 G 中覆盖 X = S \cup T 的匹配。

情况 2：对所有非平凡子集都有 |N(S)| > |S|

假设对任意 S \subset X，S \neq \varnothing，S \neq X，都有：

|N(S)| > |S|

证明思路：

  1. 任取 x_0 \in X。
  2. 由 Hall 条件，|N(\{x_0\})| \geq 1，且由当前情况假设，实际上 |N(\{x_0\})| \geq 2（严格大于）。
  3. 选择 x_0 的一个邻居 y_0 \in Y，暂定边 (x_0, y_0) 在匹配中。
  4. 考虑子图 G'：删除 x_0 和 y_0 及其关联边：
    • 顶点集：X' = X \setminus \{x_0\}，Y' = Y \setminus \{y_0\}。
  5. 验证 G' 满足 Hall 条件
    • 任取 S' \subseteq X'，S' \neq \varnothing。
    • 在原图 G 中，由情况2假设：|N_G(S')| \geq |S'| + 1。
    • 因此：|N_{G'}(S')| \geq |N_G(S')| - 1 \geq (|S'| + 1) - 1 = |S'|。
    • 故 G' 满足 Hall 条件。
  6. 因 |X'| = n-1 < n，由归纳假设，存在匹配 M' 覆盖 X'。
  7. 完成匹配：令 M = M' \cup \{(x_0, y_0)\}，则 M 覆盖 X。
归纳完成

在两种情况下，我们都由归纳假设成功构造出覆盖 X 的匹配。因此，由数学归纳法，对于所有满足 Hall 条件的有限二分图，都存在匹配覆盖其左部 X。充分性得证。

推论与应用

推论：正则二分图 ^{[3]} 一定有完美匹配。\ 应用：

  1. 解决系统不同代表系（SDR）^{[4]} 问题：可以将问题转化为二分图上的问题，然后使用 Hall 定解决即可。
  2. 作为二分图匹配算法如匈牙利算法的正确性证明的一部分。

注释

[1] : 显然，这样的完美匹配是二分图中可能存在的最大匹配。

[2] : 邻域 N(S) 表示所有与 S 中的点直接相邻的顶点所构成的集合。

[3] : 正则二分图，及满足正则图的二分图。正则图是指各顶点的度均相同的无向简单图。

[4] : 系统不同代表系（SDR）问题：对于一个有限集族 \mathcal{F}= \{A_1,A_2,...A_n \} ，能否从每个集合 A_i 中挑选出一个“代表”元素 x_i，并且所有代表都互不相同。

参考文献