霍尔婚配定理

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

集族表述

设 $S$ 为 $X$ 的有限子集组成的有限多重族。

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

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

$|W|\leq \left|\bigcup _{A\in W}A\right|.$

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

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

证明见§ 图论表述。

例

例一：符合霍尔条件

例一：考虑集族 $S=\{A_{1},A_{2},A_{3}\}$，其中

${\begin{aligned}A_{1}&=\{1,2,3\},\\A_{2}&=\{1,4,5\},\\A_{3}&=\{3,5\}.\end{aligned}}$

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

例二：违反霍尔条件

例二：考虑 $S=\{A_{1},A_{2},A_{3},A_{4}\}$，其中

${\begin{aligned}A_{1}&=\{2,3,4,5\},\\A_{2}&=\{4,5\},\\A_{3}&=\{5\},\\A_{4}&=\{4\}.\end{aligned}}$

此时，无合适的代表系。子族 $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{aligned}A_{1}&=\{1,2,3\},\\A_{2}&=\{2,4\},\\A_{3}&=\{1,2,4\},\\A_{4}&=\{2,4\}.\end{aligned}}$

此时，$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|$ 名女士根本无法找到足够的配偶。较不明显的是，该条件亦为充分，此即霍尔定理的肯綮。

图论表述

蓝色边构成一组匹配

设 $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)|\geq |M(W)|$，即 $|N_{G}(W)|\geq |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|\leq |Z|=|W|-1<|W|$，违反霍尔条件。

算法

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

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

以下叙述算法的步骤：

1. 初始时，设 $M$ 为空集，未选定任何边。（其后会加边入 $M$。）
2. 检查：$M$ 确为 $G$ 的匹配。
3. 若 $M$ 已覆盖 $X$，则为所求的 $X$ 完美匹配，输出并结束程序。
4. 否则，找到未匹配的顶点 $x_{0}\in X\setminus V(M)$。
5. 调用寻找增广路径的子程序，视乎情况：
   1. 若找到霍尔犯，则输出并结束。
   2. 若找到 $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年），得名自克尼格·代奈什、艾盖瓦里·耶内两位匈牙利数学家，是克尼格定理的加权推广。
• 门格尔定理（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}$ 为真；
• 对应每对互异的 $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\leq D$，而若更甚者，图中没有反向的，由 $D$ 至 $C$ 的单射，则称 $C<D$。前述定义中，若忽略“在图中”三字，则所得大小的概念等同一般基数的大小比较。无穷集的婚配定理断言：

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

代表系的数目

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

设有一列有限集 $(A_{1},A_{2},\ldots ,A_{n})$，不必相异，但满足霍尔条件，又设 $|A_{i}|\geq r$ 对 $i=1,\ldots ,n$ 成立。则当 $r\leq 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$ 所有顶点连边。新图将满足霍尔条件。）

非二部图

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

参考文献

• Brualdi, Richard A., Introductory Combinatorics [入门组合学], Upper Saddle River, NJ: Prentice-Hall/Pearson, 2010, ISBN 978-0-13-602040-0 （英语） 
• Cameron, Peter J., Combinatorics: Topics, Techniques, Algorithms [组合学：问题、技巧、算法], Cambridge: Cambridge University Press, 1994, ISBN 978-0-521-45761-3 （英语） 
• Dongchen, Jiang; Nipkow, Tobias, Hall's Marriage Theorem [霍尔婚配定理], The Archive of Formal Proofs, 2010 [2021-12-15], ISSN 2150-914X, （原始内容存档于2016-03-19） （英语）. 经电脑验证的证明。 
• Hall, Jr., Marshall, Combinatorial Theory [组合理论] 2nd, New York: John Wiley & Sons, 1986, ISBN 978-0-471-09138-7 （英语） 
• Hall, Philip, On Representatives of Subsets [论子集的代表元], J. London Math. Soc., 1935, 10 (1): 26–30, doi:10.1112/jlms/s1-10.37.26 （英语） 
• Halmos, Paul R.; Vaughan, Herbert E., The marriage problem [婚配问题], American Journal of Mathematics, 1950, 72 (1): 214–215, JSTOR 2372148, MR 0033330, doi:10.2307/2372148 （英语） 
• Reichmeider, P.F., The Equivalence of Some Combinatorial Matching Theorems [若干组合匹配问题之等价], Polygonal Publishing House, 1984, ISBN 978-0-936428-09-3 （英语） 
• Roberts, Fred S.; Tesman, Barry, Applied Combinatorics [应用组合学] 2nd, Boca Raton: CRC Press, 2009, ISBN 978-1-4200-9982-9 （英语） 
• van Lint, J. H.; Wilson, R.M., A Course in Combinatorics [组合学教程], Cambridge: Cambridge University Press, 1992, ISBN 978-0-521-42260-4 （英语） 

站外链结

• Cut-the-knot站，Marriage Theorem （页面存档备份，存于互联网档案馆）
• Cut-the-knot站，Marriage Theorem and Algorithm （页面存档备份，存于互联网档案馆）
• Lucky的笔记Hall's marriage theorem explained intuitively （页面存档备份，存于互联网档案馆）.

本条目含有来自PlanetMath《proof of Hall's marriage theorem》的内容，版权遵守知识共享协议：署名-相同方式共享协议。