霍尔婚配定理

数学上，霍尔婚配定理婚配之名见于。（Hall's marriage theorem）是菲利浦·霍尔最先证明的图论定理，又称霍尔定理，描述二分图中，能将一侧全部顶点牵线匹配到另一侧的充要条件。定理另有一个等价的组合叙述，确定一族有限集合在何种充要条件下，可自每个集合各拣选一个元素，而使所选元素两两互异（即没有元素是重复的）。

## 集族表述

设 $S$ 为 $X$ 的有限子集。也可以允许无穷集，但此时须限制族中的集合数有限（考虑重数），见#推广。然而，不能放宽成无穷多个无穷集。组成的有限$S$ 可以放宽为无穷族，见#推广。多重即 $S$ 可以有重复的元素，且会考虑其重复次数。族。

$S$ 的一个代表系 (组合学)是 $S$ 至 $X$ 的单射，且该单射 $f$ 将族中任意集合 $s\in S$ 映至该集合的某元素 $f(s)$。换言之，$f$ 从 $S$ 中每个集合，选出一个代表元，使得不同的集合由不同元素代表（“单射”之义）。代表系又称为“截面”或“遍历”（transversal）。

族 $S$ 满足霍尔条件，意思是对每个子族 $W \subseteq S$，有

$$|W| \le \left|\bigcup_{A \in W} A\right|.$$

用文字复述，该条件断言对于 $S$ 的每个子族，其各集合一共拥有的不同成员数，不小于该子族的集合数。若不满足该条件，则不存在代表系，因为在某子族 $W$（设有 $k$ 个集合）中，各集合一共只有少于 $k$ 个互异元素，如此由鸽巢原理，为 $k$ 个集合所选的 $k$ 个代表元之中，必有两者相等。霍尔定理说明，前述命题的否命题也成立，即若满足霍尔条件，则必存在代表系。

霍尔定理：一族有限集有代表系，当且仅当其满足霍尔条件，即其任意子族皆满足以上不等式。

证明见#图论表述。

### 例

<image>

例一：考虑集族 $S = \{A_1, A_2, A_3\}$，其中

$$\begin{align} A_1 &= \{1, 2, 3\}, \\ A_2 &= \{1, 4, 5\}, \\ A_3 &= \{3, 5\}. \end{align}$$

合适的代表系有 $(1, 4, 5)$，但并不唯一，例如 $(2, 1, 3)$ 亦可。

<image>

例二：考虑 $S = \{A_1, A_2, A_3, A_4\}$，其中

$$\begin{align} A_1 &= \{2, 3, 4, 5\},\\ A_2 &= \{4, 5\}, \\ A_3 &= \{5\},\\ A_4 &= \{4\}. \end{align}$$

此时，无合适的代表系。子族 $W = \{A_2, A_3, A_4\}$ 违反霍尔条件，因为该族有 $|W| = 3$ 个集合，但该三个集之并为 $A_2 \cup A_3 \cup A_4 = \{4, 5\}$，仅得两个元素。

例三：同样设 $S = \{A_1, A_2, A_3, A_4\}$，但换成

$$\begin{align} A_1 &= \{1, 2, 3\},\\ A_2 &= \{2, 4\}, \\ A_3 &= \{1, 2, 4\},\\ A_4 &= \{2, 4\}. \end{align}$$

此时，$A_2$ 与 $A_4$ 的代表必为 $2, 4$ 或逆序，从而 $A_3$ 的代表须为 $1$。所以，合适的代表系有且只有 $(3, 2, 1, 4)$ 或 $(3, 4, 1, 2)$。

### 命名

定理命名为“婚配”（marriage），是与以下例子有关。设有两组人，一组 $n$ 男，一组 $n$ 女。每名女士心目中皆有一份名单（若干男士组成的子集），会接受名单中的男士的求婚，但会拒绝其他人。而该些男士别无所求，愿意向任何女士求婚。媒人希望判断是否存在方案，在尊重诸位女士的意愿的前提下，将该两组人撮合成 $n$ 对夫妻此例子中，为使定理适用，需要假设该些人的婚姻为一夫一妻制。

以 $A_i$ 表示第 $i$ 名女士愿意接受的男士集合，则霍尔定理讲述，存在方案使每位女士与心仪对象结婚，且无重婚，当且仅当对于任意若干位女士组成的集合 $I$，愿意与其中至少一位女士结婚的男士数 $\left|\bigcup_{i \in I} A_i\right|$，不小于该集合的女士数 $|I|$。

后一个条件为必要，否则该 $|I|$ 名女士根本无法找到足够的配偶。较不明显的是，该条件亦为充分，此即霍尔定理的要处。

## 图论表述

<image>

设 $G$ 为有限二部图，顶点集分为 $X$、$Y$ 两部，以符号记为 $G = (X \sqcup Y, E)$。$X$ 完美匹配是图上若干条边组成的匹配，其两两无公共端点，且 $X$ 的每个顶点各有一条边在该匹配中。

对于 $X$ 的任意子集 $W$，设 $N_G(W)$ 为 $W$ 在 $G$ 中的邻域 (图论)，即 $Y$ 中与 $W$ 至少一点有连边的全体顶点之集。霍尔定理断言，存在 $X$ 完美匹配，当且仅当对 $X$ 的每个子集 $W$，皆有：

$$|W| \leq |N_G(W)|.$$

换言之，与 $W$ 相邻的顶点，不少于 $W$ 的顶点。上述不等式称为霍尔条件。

### 证明

“$\Longrightarrow$”：假设有匹配 $M$，覆盖顶点集 $X$。欲证霍尔条件对全部 $W \subseteq X$ 成立。记 $M(W)$ 为 $W$ 经 $M$ 匹配到的顶点集，其为 $Y$ 的子集。由匹配的定义，必有 $|M(W)| = |W|$，同时 $M(W) \subseteq N_G(W)$，因为 $M(W)$ 的元素皆为 $W$ 的邻舍。故 $|N_G(W)| \ge |M(W)|$，即 $|N_G(W)| \ge |W|$。

“$\Longleftarrow$”：假设无 $X$ 完美匹配，欲证有某子集 $W\subseteq X$ 违反霍尔条件。设 $M$ 为极大匹配，换言之，若再添加任何一条边，则不再为匹配。设 $u$ 为 $X$ 中未获覆盖的顶点。考虑由 $u$ 出发的全体“交错路径”，即图 $G$ 中的路径，其首边不属 $M$，次边属于 $M$，第三边又不属 $M$，如此交错排列。$u$ 藉该些交错路径，与 $Y$ 中若干顶点相连，该些顶点组成的子集记为 $Z$；又与 $X$ 中若干顶点相连（此处 $u$ 亦视为与自己相连），得子集 $W$。极长即无法再延伸。交错路径不能终于 $Y$，否则其首尾皆不属 $M$，故为“增广路径”：翻转路径上所有边的状态，将不属 $M$ 者加入 $M$，属 $M$ 者移走，则得到严格比 $M$ 多边的匹配，此为不可能。至此，已证 $Z$ 中每个顶点，皆经 $M$ 匹配到 $W \setminus \{u\}$ 中某顶点。反之，$W \setminus \{u\}$ 中任意一个顶点，亦有 $Z$ 中某顶点与之匹配，即沿 $u$ 至 $v$ 的交错路径，$v$ 的前一顶点。所以，$M$ 给出 $W \setminus \{u\}$ 与 $Z$ 之间的一一对应，所以 $|W| = |Z|+1$。另一方面，将证明 $N_G(W) \subseteq Z$。设 $v \in N_G(W)$ 是与某顶点 $w \in W$ 邻接。若边 $wv$ 在 $M$ 中，则自 $u$ 至 $w$ 的一切交错路径中，$v$ 皆在 $w$ 以先，故有 $u$ 至 $v$ 的交错路径。否则 $wv$ 不属 $M$，但已知有 $u$ 至 $w$ 的交错路径，末边属于 $M$，故可续以 $wv$，亦得自 $u$ 至 $v$ 的交错路径。证毕 $N_G(W) \subseteq Z$，故 $\left|N_G(W)\right| \le |Z| = |W| - 1 < |W|$，违反霍尔条件。

### 算法

若 $X$ 的子集 $W$ 满足 $|N_G(W)| < |W|$，则定义 $W$ 为霍尔犯。若 $W$ 为霍尔犯，则无匹配能覆盖 $W$ 的全部顶点。所以，也无匹配覆盖 $X$。霍尔定理断言，二部图有 $X$ 完美匹配，当且仅当其不含任何霍尔犯。以下算法验证定理较难的方向：输入一幅二部图，算法或输出一个 $X$ 完美匹配，或输出一个霍尔犯。

该算法调用以下子程序：输入匹配 $M$ 及未匹配的某顶点 $x_0 \in X$，或输出一条 $M$ 增广路径，或输出一个霍尔犯。该子程序可以深度优先搜索实作。

以下叙述算法的步骤：

- 初始时，设 $M$ 为空集，未选定任何边。（其后会加边入 $M$。）
- 检查：$M$ 确为 $G$ 的匹配。
- 若 $M$ 已覆盖 $X$，则为所求的 $X$ 完美匹配，输出并结束程序。
- 否则，找到未匹配的顶点 $x_0 \in X \setminus V(M)$。
- 调用寻找增广路径的子程序，视乎情况：
- 若找到霍尔犯，则输出并结束。
- 若找到 $M$ 增广路径，则将该路径上各边的状态翻转，使 $M$ 的边数增加一。返回第2步。

每次找到增广路径，都会使 $M$ 多一条边。所以，前述算法的循环至多执行 $|X|$ 次，就会停机。每次寻找增广路径需时 $\mathcal O(|E|)$。总时间复杂度与不加权的最大匹配问题的福特-富尔克森算法相约。

### 两种表述等价

设 $S = (A_1, A_2, \ldots, A_n)$，其中 $A_i$ 皆为有限集，不必相异。相应地，构造二部图 $G$，一侧顶点集 $X = \{v_1, \ldots, v_n\}$ 对应该 $n$ 个集合，另一侧顶点集 $Y$ 为该些集合之并。若 $A_i$ 有元素 $y \in Y$，则在图中连一条边 $v_i y$。如此，族 $S$ 的代表系即是 $G$ 的 $X$ 完美匹配，覆盖 $X$ 的全部顶点。所以，以集族表述的霍尔问题，容易化成图论表述的霍尔问题。反之亦然：给定二部图 $G = (X \sqcup Y, E)$，$X$ 完美匹配相当于邻域 (图论)族 $\{\Gamma(x): x \in X\}$ 的代表系。

### 其他证明

利用拓扑组合学的斯佩纳引理，可得霍尔定理的非构造性证明。

## 应用

定理有许多“非婚”应用。例如，取一叠啤牌（无鬼牌），洗匀后，派成13磴，每磴4张。由霍尔定理可证，必能从每磴拣选一张牌，使所选13张牌恰好出齐各点数（A、2、3、⋯⋯、Q、K）。更一般地，任意正则二部图（允许重边）皆有完美匹配。

较抽象的应用有双边陪集遍历。设 $G$ 为群，$H$ 为其有限指数子群，则霍尔定理适用于证明存在集合 $T$，既是 $H$ 各左陪集的代表系，又是各右陪集的代表系。

霍尔定理亦用于证明，若 $r < n$，则任意 $r \times n$ 拉丁矩阵皆可扩展成 $(r+1) \times n$ 拉丁矩阵，并可重复，直至得到完整的拉丁方阵。

## 相关定理

本定理可归类到组合学的一列强力定理，其彼此关联。若假设任何一条，则较易证得其他各条，但若要从头开始，则较难证得任何一条。总括而言，该类定理各自断言某类组合优化问题具有强对偶性。该些定理包括：

- 克尼格定理：二部图的最大匹配，与最小顶点覆盖等大。
- 克尼格-艾盖瓦里定理（1931年），得名自克尼格·代奈什、艾盖瓦里·耶内两位匈牙利数学家，是克尼格定理的加权推广。定理的名称，文献中略有出入。相关的定理既有二分图匹配的表述，也有 (0,1) 矩阵覆盖的表述。和称矩阵表述为克尼格定理，而则称之为克尼格-艾盖瓦里定理。二部图版本，和皆称为克尼格定理。
- 门格尔定理（1927年）：边最小割的大小，等于任意在所有顶点对之间可以找到的无公共边的路径的最大数量。结论换成顶点最小割与无公共（中间）顶点的路径仍成立。
- 最大流最小割定理（福特-富尔克森算法）：任意网络流中，最大流的值等于最小割。
- 伯克霍夫-冯纽曼定理（1946年）：一个方阵为双随机方阵即行和与列和皆等于一，且各项非负。当且仅当其为置换方阵的凸组合。
- 迪尔沃思定理：覆盖某偏序集所需的不交链数，与该集的最大反链等大。

欲要更具体描述各定理的关系，下列各等价关系有简单证明：

迪尔沃思定理 ⇔ 霍尔定理 ⇔ 克尼格-艾盖瓦里定理 ⇔ 克尼格定理。

## 加强

### 无穷族

马歇尔·霍尔 (数学家)细察菲利浦·霍尔两人并非亲属。原先的证明，发现可以将结论修改成对（有限集组成的）无穷族 $S$ 仍成立。该证明直接使用佐恩引理。此外，也有较简短的证明，用到命题逻辑的紧致性定理：

设 $S = \{A_i: i \in I\}$。对每个 $i \in I$ 和 $a \in A_i$，以命题 $p_{a, i}$ 表示“$a$ 选为 $A_i$ 的代表”。可以列出代表系须满足的条件如下：

- 对应每个 $i \in I$，各有一条命题断言恰有一个 $a \in A_i$ 使 $p_{a, i}$ 为真此处的命题需要 $A_i$ 为有限集，才能用命题逻辑的语言写出。
- 对应每对互异的 $i, j \in I$ 和 $a \in A_i \cap A_j$，各有一条命题为 $\neg (p_{a, i} \wedge p_{a, j})$。

如此，代表系即等价于同时满足以上各命题的赋值。由有限族的霍尔定理，对 $I$ 的任意有限子集 $J$，相应的有限子族有代表系，故以上命题中，任意有限条皆可同时满足。所以，由紧致性定理，全部命题可同时满足，即有整个无穷族的代表系。

以上一般情况的证明中，选择公理（或等价命题如佐恩引理）为必须，因为给定一族无穷多个非空集（无额外条件），欲从每个集合中，选出一个代表（而无须相异），已需要选择公理。

### 无穷集

马歇尔·霍尔给出下列反例，表明若允许有无穷集，则所组成的无穷族，即使满足霍尔条件，亦不保证有代表系。

设族 $S$ 由可数多个集合 $A_0 = \{1, 2, 3, \ldots\},\ A_1 = \{1\},\ A_2 = \{2\}, \ \ldots,\ A_i = \{i\},\ \ldots$ 构成。该族满足霍尔条件，但无法选出代表系。

若妥为叙述，则的确可将霍尔定理推广至适用于无穷集。给定二部图，两侧顶点集为 $A, B$，若由 $B$ 的子集 $C$ 出发，在图中找到单射（意思是只能用二部图的边），射向 $A$ 的子集 $D$，则称 $C \le D$，而若更甚者，图中没有反向的，由 $D$ 至 $C$ 的单射，则称 $C < D$。前述定义中，若忽略“在图中”三字，则所得大小的概念等同一般基数的大小比较。无穷集的婚配定理断言：

图中有 $A$ 至 $B$ 的单射，当且仅当对每个 $D \subseteq A$，皆有其邻域 $N(D) \nless D$。

### 代表系的数目

马歇尔·霍尔也计算出给定有限族 $S$ 的代表系数目的下界，从而加强婚配定理。其叙述为：

设有一列有限集 $(A_1, A_2, \ldots, A_n)$，不必相异，但满足霍尔条件，又设 $|A_i| \ge r$ 对 $i = 1, \ldots, n$ 成立。则当 $r \le n$ 时，该族有限集至少有 $r!$ 个不同的代表系，而当 $r > n$ 时，至少有 $r(r-1) \cdots (r - n + 1)$ 个。

此处即使两个代表系的元素一样，只要其次序不同，亦视为不同。例如，若 $A_1 = \{1, 2, 3\}$，$A_2 = \{1, 2, 5\}$，则 $(1, 2)$ 和 $(2, 1)$ 为两个不同的代表系。

### 分数匹配

图的分数匹配（fractional matching）是对各边赋予非负权值，使每个顶点所连各边的权值和不超逾 $1$。所谓 $X$ 完美的分数匹配，即是使 $X$ 中的每一顶点处，各边权之和恰为 $1$。对于二部图 $G = (X\sqcup Y, E)$，下列各项等价：

- $G$ 有 $X$ 完美匹配。
- $G$ 有 $X$ 完美分数匹配。（此为前项的直接推论。给定一个 $X$ 完美匹配，将该匹配所选的边赋权 $1$，其余边赋 $0$，则得到 $X$ 完美分数匹配。）
- $G$ 满足霍尔条件。（若有前项的分数匹配，则对于 $X$ 的每个子集 $W$，其所连各边之和恰为 $|W|$，故至少要与对面的 $|W|$ 个顶点相连，因为对面每个顶点所连的边值和不超过 $1$。）

### 亏缺

假如霍尔条件不成立，则原定理仅断言不存在完美匹配，但并未说明匹配最大可以多大。欲知此事，需要考虑亏度 (图论)。对于二部图 $G = (X \sqcup Y, E)$，$G$ 关于 $X$ 的亏度（deficiency）是 $|W| - |N_G(W)|$ 的最大值，其中 $W$ 可取 $X$ 的任意子集。亏度越大，则图离霍尔条件越远。

用霍尔定理可证，若二部图的亏度为 $d$，则有大小为 $|X| - d$ 的匹配。（考虑在 $Y$ 侧添加 $d$ 个辅助点，与 $X$ 所有顶点连边。新图将满足霍尔条件。）

### 非二部图

- 若推广至一般的图（不必为二部图），则其上有完美匹配的充要条件，由塔特定理描述。
- 若推广至各类二部超图（二部图的超图版本），则相应有各种超图的霍尔式定理。

## 站外链接

- Cut-the-knot站， Marriage Theorem
- Cut-the-knot站， Marriage Theorem and Algorithm
- Lucky的笔记 Hall's marriage theorem explained intuitively .