霍爾婚配定理

數學上，**霍爾婚配定理**（英語：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》的內容，版權遵守創用 CC 協議：署名 - 相同方式共享協議。