霍爾婚配定理

数学上，霍爾婚配定理^{[註 1]}（英語：Hall's marriage theorem）是菲利浦·霍爾最先證明^[3]的圖論定理，又稱霍爾定理^[4]，描述二分图中，能將一側全部頂點牽線匹配到另一側的充要條件。定理另有一個等價的組合敍述，確定一族有限集合在何種充要條件下，可自每個集合各揀選一個元素，而使所選元素兩兩互異（即沒有元素是重復的）。

集族表述

設 ${\displaystyle S}$ 為 ${\displaystyle X}$ 的有限子集^{[註 2]}組成的有限^{[註 3]}多重^{[註 4]}族。

${\displaystyle S}$ 的一個代表系（英语：Transversal (combinatorics)）是 ${\displaystyle S}$ 至 ${\displaystyle X}$ 的單射，且該單射 ${\displaystyle f}$ 將族中任意集合 ${\displaystyle s\in S}$ 映至該集合的某元素 ${\displaystyle f(s)}$。換言之，${\displaystyle f}$ 從 ${\displaystyle S}$ 中每個集合，選出一個代表元，使得不同的集合由不同元素代表（「單射」之義）。代表系又稱為「截面」或「遍歷」（transversal）。

族 ${\displaystyle S}$ 滿足霍爾條件，意思是對每個子族 ${\displaystyle W\subseteq S}$，有

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

用文字複述，該條件斷言對於 ${\displaystyle S}$ 的每個子族，其各集合一共擁有的不同成員數，不小於該子族的集合數。若不滿足該條件，則不存在代表系，因為在某子族 ${\displaystyle W}$（設有 ${\displaystyle k}$ 個集合）中，各集合一共衹有少於 ${\displaystyle k}$ 個互異元素，如此由鴿巢原理，為 ${\displaystyle k}$ 個集合所選的 ${\displaystyle k}$ 個代表元之中，必有兩者相等。霍爾定理說明，前述命題的否命題也成立，即若滿足霍爾條件，則必存在代表系。

霍爾定理：一族有限集有代表系，當且僅當其滿足霍爾條件，即其任意子族皆滿足以上不等式。

證明見§ 圖論表述。

例

例一：符合霍爾條件

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

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

合適的代表系有 ${\displaystyle (1,4,5)}$，但並不唯一，例如 ${\displaystyle (2,1,3)}$ 亦可。

例二：違反霍爾條件

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

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

此時，無合適的代表系。子族 ${\displaystyle W=\{A_{2},A_{3},A_{4}\}}$ 違反霍爾條件，因為該族有 ${\displaystyle |W|=3}$ 個集合，但該三個集之並為 ${\displaystyle A_{2}\cup A_{3}\cup A_{4}=\{4,5\}}$，僅得兩個元素。

例三：同樣設 ${\displaystyle S=\{A_{1},A_{2},A_{3},A_{4}\}}$，但換成

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

此時，${\displaystyle A_{2}}$ 與 ${\displaystyle A_{4}}$ 的代表必為 ${\displaystyle 2,4}$ 或逆序，從而 ${\displaystyle A_{3}}$ 的代表須為 ${\displaystyle 1}$。所以，合適的代表系有且衹有 ${\displaystyle (3,2,1,4)}$ 或 ${\displaystyle (3,4,1,2)}$。

命名

定理命名為「婚配」（marriage），是與以下例子有關。設有兩組人，一組 ${\displaystyle n}$ 男，一組 ${\displaystyle n}$ 女。每名女士心目中皆有一份名單（若干男士組成的子集），會接受名單中的男士的求婚，但會拒絕其他人。而該些男士別無所求，願意向任何女士求婚。媒人希望判斷是否存在方案，在尊重諸位女士的意願的前提下，將該兩組人撮合成 ${\displaystyle n}$ 對夫妻^{[註 5]}。

以 ${\displaystyle A_{i}}$ 表示第 ${\displaystyle i}$ 名女士願意接受的男士集合，則霍爾定理講述，存在方案使每位女士與心儀對象結婚，且無重婚，當且僅當對於任意若干位女士組成的集合 ${\displaystyle I}$，願意與其中至少一位女士結婚的男士數 ${\displaystyle \left|\bigcup _{i\in I}A_{i}\right|}$，不小於該集合的女士數 ${\displaystyle |I|}$。

後一個條件為必要，否則該 ${\displaystyle |I|}$ 名女士根本無法找到足夠的配偶。較不明顯的是，該條件亦為充分，此即霍爾定理的肯綮。

圖論表述

藍色邊構成一組匹配

設 ${\displaystyle G}$ 為有限二部圖，頂點集分為 ${\displaystyle X}$、${\displaystyle Y}$ 兩部，以符號記為 ${\displaystyle G=(X\sqcup Y,E)}$。${\displaystyle X}$ 完美匹配是圖上若干條邊組成的匹配，其兩兩無公共端點，且 ${\displaystyle X}$ 的每個頂點各有一條邊在該匹配中。

對於 ${\displaystyle X}$ 的任意子集 ${\displaystyle W}$，設 ${\displaystyle N_{G}(W)}$ 為 ${\displaystyle W}$ 在 ${\displaystyle G}$ 中的鄰域（英语：Neighbourhood (graph theory)），即 ${\displaystyle Y}$ 中與 ${\displaystyle W}$ 至少一點有連邊的全體頂點之集。霍爾定理斷言，存在 ${\displaystyle X}$ 完美匹配，当且仅当對 ${\displaystyle X}$ 的每個子集 ${\displaystyle W}$，皆有：

${\displaystyle |W|\leq |N_{G}(W)|.}$

換言之，與 ${\displaystyle W}$ 相鄰的頂點，不少於 ${\displaystyle W}$ 的頂點。上述不等式稱為霍爾條件。

證明

「${\displaystyle \Longrightarrow }$」：假設有匹配 ${\displaystyle M}$，覆蓋頂點集 ${\displaystyle X}$。欲證霍爾條件對全部 ${\displaystyle W\subseteq X}$ 成立。記 ${\displaystyle M(W)}$ 為 ${\displaystyle W}$ 經 ${\displaystyle M}$ 匹配到的頂點集，其為 ${\displaystyle Y}$ 的子集。由匹配的定義，必有 ${\displaystyle |M(W)|=|W|}$，同時 ${\displaystyle M(W)\subseteq N_{G}(W)}$，因為 ${\displaystyle M(W)}$ 的元素皆為 ${\displaystyle W}$ 的鄰舍。故 ${\displaystyle |N_{G}(W)|\geq |M(W)|}$，即 ${\displaystyle |N_{G}(W)|\geq |W|}$。

「${\displaystyle \Longleftarrow }$」：假設無 ${\displaystyle X}$ 完美匹配，欲證有某子集 ${\displaystyle W\subseteq X}$ 違反霍爾條件。設 ${\displaystyle M}$ 為極大匹配，換言之，若再添加任何一條邊，則不再為匹配。設 ${\displaystyle u}$ 為 ${\displaystyle X}$ 中未獲覆蓋的頂點。考慮由 ${\displaystyle u}$ 出發的全體「交錯路徑」，即圖 ${\displaystyle G}$ 中的路徑，其首邊不屬 ${\displaystyle M}$，次邊屬於 ${\displaystyle M}$，第三邊又不屬 ${\displaystyle M}$，如此交錯排列。${\displaystyle u}$ 藉該些交錯路徑，與 ${\displaystyle Y}$ 中若干頂點相連，該些頂點組成的子集記為 ${\displaystyle Z}$；又與 ${\displaystyle X}$ 中若干頂點相連（此處 ${\displaystyle u}$ 亦視為與自己相連），得子集 ${\displaystyle W}$。極長^{[註 6]}的交錯路徑不能終於 ${\displaystyle Y}$，否則其首尾皆不屬 ${\displaystyle M}$，故為「增廣路徑」：翻轉路徑上所有邊的狀態，將不屬 ${\displaystyle M}$ 者加入 ${\displaystyle M}$，屬 ${\displaystyle M}$ 者移走，則得到嚴格比 ${\displaystyle M}$ 多邊的匹配，此為不可能。至此，已證 ${\displaystyle Z}$ 中每個頂點，皆經 ${\displaystyle M}$ 匹配到 ${\displaystyle W\setminus \{u\}}$ 中某頂點。反之，${\displaystyle W\setminus \{u\}}$ 中任意一個頂點，亦有 ${\displaystyle Z}$ 中某頂點與之匹配，即沿 ${\displaystyle u}$ 至 ${\displaystyle v}$ 的交錯路徑，${\displaystyle v}$ 的前一頂點。所以，${\displaystyle M}$ 給出 ${\displaystyle W\setminus \{u\}}$ 與 ${\displaystyle Z}$ 之間的一一對應，所以 ${\displaystyle |W|=|Z|+1}$。另一方面，將證明 ${\displaystyle N_{G}(W)\subseteq Z}$。設 ${\displaystyle v\in N_{G}(W)}$ 是與某頂點 ${\displaystyle w\in W}$ 鄰接。若邊 ${\displaystyle wv}$ 在 ${\displaystyle M}$ 中，則自 ${\displaystyle u}$ 至 ${\displaystyle w}$ 的一切交錯路徑中，${\displaystyle v}$ 皆在 ${\displaystyle w}$ 以先，故有 ${\displaystyle u}$ 至 ${\displaystyle v}$ 的交錯路徑。否則 ${\displaystyle wv}$ 不屬 ${\displaystyle M}$，但已知有 ${\displaystyle u}$ 至 ${\displaystyle w}$ 的交錯路徑，末邊屬於 ${\displaystyle M}$，故可續以 ${\displaystyle wv}$，亦得自 ${\displaystyle u}$ 至 ${\displaystyle v}$ 的交錯路徑。證畢 ${\displaystyle N_{G}(W)\subseteq Z}$，故 ${\displaystyle \left|N_{G}(W)\right|\leq |Z|=|W|-1<|W|}$，違反霍爾條件。

算法

若 ${\displaystyle X}$ 的子集 ${\displaystyle W}$ 滿足 ${\displaystyle |N_{G}(W)|<|W|}$，則定義 ${\displaystyle W}$ 為霍爾犯（英语：Hall violator）。若 ${\displaystyle W}$ 為霍爾犯，則無匹配能覆蓋 ${\displaystyle W}$ 的全部頂點。所以，也無匹配覆蓋 ${\displaystyle X}$。霍爾定理斷言，二部圖有 ${\displaystyle X}$ 完美匹配，當且僅當其不含任何霍爾犯。以下算法驗證定理較難的方向：輸入一幅二部圖，算法或輸出一個 ${\displaystyle X}$ 完美匹配，或輸出一個霍爾犯。

該算法調用以下子程序：輸入匹配 ${\displaystyle M}$ 及未匹配的某頂點 ${\displaystyle x_{0}\in X}$，或輸出一條 ${\displaystyle M}$ 增廣路徑，或輸出一個霍爾犯。該子程序可以深度优先搜索實作。

以下敍述算法的步驟：

1. 初始時，設 ${\displaystyle M}$ 為空集，未選定任何邊。（其後會加邊入 ${\displaystyle M}$。）
2. 檢查：${\displaystyle M}$ 確為 ${\displaystyle G}$ 的匹配。
3. 若 ${\displaystyle M}$ 已覆蓋 ${\displaystyle X}$，則為所求的 ${\displaystyle X}$ 完美匹配，輸出並結束程序。
4. 否則，找到未匹配的頂點 ${\displaystyle x_{0}\in X\setminus V(M)}$。
5. 調用尋找增廣路徑的子程序，視乎情況：
   1. 若找到霍爾犯，則輸出並結束。
   2. 若找到 ${\displaystyle M}$ 增廣路徑，則將該路徑上各邊的狀態翻轉，使 ${\displaystyle M}$ 的邊數增加一。返回第2步。

每次找到增廣路徑，都會使 ${\displaystyle M}$ 多一條邊。所以，前述算法的迴圈至多執行 ${\displaystyle |X|}$ 次，就會停機。每次尋找增廣路徑需時 ${\displaystyle {\mathcal {O}}(|E|)}$。總時間複雜度與不加權的最大匹配問題（英语：maximum cardinality matching）的福特-富爾克森算法相約。

兩種表述等價

設 ${\displaystyle S=(A_{1},A_{2},\ldots ,A_{n})}$，其中 ${\displaystyle A_{i}}$ 皆為有限集，不必相異。相應地，構造二部圖 ${\displaystyle G}$，一側頂點集 ${\displaystyle X=\{v_{1},\ldots ,v_{n}\}}$ 對應該 ${\displaystyle n}$ 個集合，另一側頂點集 ${\displaystyle Y}$ 為該些集合之並。若 ${\displaystyle A_{i}}$ 有元素 ${\displaystyle y\in Y}$，則在圖中連一條邊 ${\displaystyle v_{i}y}$。如此，族 ${\displaystyle S}$ 的代表系即是 ${\displaystyle G}$ 的 ${\displaystyle X}$ 完美匹配，覆蓋 ${\displaystyle X}$ 的全部頂點。所以，以集族表述的霍爾問題，容易化成圖論表述的霍爾問題。反之亦然：給定二部圖 ${\displaystyle G=(X\sqcup Y,E)}$，${\displaystyle X}$ 完美匹配相當於鄰域（英语：Neighbourhood (graph theory)）族 ${\displaystyle \{\Gamma (x):x\in X\}}$ 的代表系。

其他證明

利用拓撲組合學（英语：Topological combinatorics）的斯佩納引理（英语：Sperner's lemma），可得霍爾定理的非構造性證明。^{[5]:Thm.4.1,4.2}

應用

定理有許多「非婚」應用。例如，取一疊啤牌（無鬼牌），洗勻後，派成13磴，每磴4張。由霍爾定理可證，必能從每磴揀選一張牌，使所選13張牌恰好出齊各點數（A、2、3、⋯⋯、Q、K）。更一般地，任意正則二部圖（允許重邊）皆有完美匹配。^[6]:2

較抽象的應用有雙邊陪集遍歷。設 ${\displaystyle G}$ 為群，${\displaystyle H}$ 為其有限指數子群，則霍爾定理適用於證明存在集合 ${\displaystyle T}$，既是 ${\displaystyle H}$ 各左陪集的代表系，又是各右陪集的代表系。^[7]

霍爾定理亦用於證明，若 ${\displaystyle r<n}$，則任意 ${\displaystyle r\times n}$ 拉丁矩陣（英语：Latin rectangle）皆可擴展成 ${\displaystyle (r+1)\times n}$ 拉丁矩陣，並可重複，直至得到完整的拉丁方陣。^[8]

相關定理

本定理可歸類到組合學的一列強力定理，其彼此關聯。若假設任何一條，則較易證得其他各條，但若要從頭開始，則較難證得任何一條。總括而言，該類定理各自斷言某類組合優化問題具有強對偶性（英语：Strong duality）。該些定理包括：

• 克尼格定理（英语：Kőnig's theorem (graph theory)）：二部圖的最大匹配，與最小頂點覆蓋（英语：Vertex cover）等大。
  • 克尼格-艾蓋瓦里定理（英语：König–Egerváry theorem）（1931年），得名自克尼格·代奈什（英语：Dénes Kőnig）、艾蓋瓦里·耶內兩位匈牙利數學家，是克尼格定理的加權推廣。^{[註 7]}
• 门格尔定理（1927年）：邊最小割的大小，等於任意在所有頂點對之間可以找到的無公共邊的路徑的最大數量。結論換成頂點最小割與無公共（中間）頂點的路徑仍成立。
• 最大流最小割定理（福特-富爾克森算法）：任意网络流中，最大流的值等於最小割。
• 伯克霍夫-馮紐曼定理（英语：Birkhoff–Von Neumann theorem）（1946年）：一個方陣為雙隨機（英语：Doubly stochastic matrix）^{[註 8]}，當且僅當其為置換方陣的凸組合。
• 迪爾沃思定理（英语：Dilworth's theorem）：覆蓋某偏序集所需的不交鏈數，與該集的最大反鏈等大。

欲要更具體^[9][10]描述各定理的關係，下列各等價關係有簡單證明：

迪爾沃思定理 ⇔ 霍爾定理 ⇔ 克尼格-艾蓋瓦里定理 ⇔ 克尼格定理。

加強

無窮族

馬歇爾·霍爾（英语：Marshall Hall (mathematician)）細察菲利浦·霍爾^{[註 9]}原先的證明，發現可以將結論修改成對（有限集組成的）無窮族 ${\displaystyle S}$ 仍成立。^[11]該證明直接使用佐恩引理。此外，也有較簡短的證明，用到命題邏輯的緊緻性定理：^[12]

設 ${\displaystyle S=\{A_{i}:i\in I\}}$。對每個 ${\displaystyle i\in I}$ 和 ${\displaystyle a\in A_{i}}$，以命題 ${\displaystyle p_{a,i}}$ 表示「${\displaystyle a}$ 選為 ${\displaystyle A_{i}}$ 的代表」。可以列出代表系須滿足的條件如下：

• 對應每個 ${\displaystyle i\in I}$，各有一條命題斷言恰有一個 ${\displaystyle a\in A_{i}}$ 使 ${\displaystyle p_{a,i}}$ 為真^{[註 10]}；
• 對應每對互異的 ${\displaystyle i,j\in I}$ 和 ${\displaystyle a\in A_{i}\cap A_{j}}$，各有一條命題為 ${\displaystyle \neg (p_{a,i}\wedge p_{a,j})}$。

如此，代表系即等價於同時滿足以上各命題的賦值。由有限族的霍爾定理，對 ${\displaystyle I}$ 的任意有限子集 ${\displaystyle J}$，相應的有限子族有代表系，故以上命題中，任意有限條皆可同時滿足。所以，由緊緻性定理，全部命題可同時滿足，即有整個無窮族的代表系。

以上一般情況的證明中，選擇公理（或等價命題如佐恩引理）為必須，因為給定一族無窮多個非空集（無額外條件），欲從每個集合中，選出一個代表（而無須相異），已需要選擇公理。

無窮集

馬歇爾·霍爾給出下列反例，表明若允許有無窮集，則所組成的無窮族，即使滿足霍爾條件，亦不保證有代表系。

設族 ${\displaystyle S}$ 由可數多個集合 ${\displaystyle A_{0}=\{1,2,3,\ldots \},\ A_{1}=\{1\},\ A_{2}=\{2\},\ \ldots ,\ A_{i}=\{i\},\ \ldots }$ 構成。該族滿足霍爾條件，但無法選出代表系。^[11]

若妥為敍述，則的確可將霍爾定理推廣至適用於無窮集。給定二部圖，兩側頂點集為 ${\displaystyle A,B}$，若由 ${\displaystyle B}$ 的子集 ${\displaystyle C}$ 出發，在圖中找到單射（意思是衹能用二部圖的邊），射向 ${\displaystyle A}$ 的子集 ${\displaystyle D}$，則稱 ${\displaystyle C\leq D}$，而若更甚者，圖中沒有反向的，由 ${\displaystyle D}$ 至 ${\displaystyle C}$ 的單射，則稱 ${\displaystyle C<D}$。前述定義中，若忽略「在圖中」三字，則所得大小的概念等同一般基數的大小比較。無窮集的婚配定理斷言：^[13]

圖中有 ${\displaystyle A}$ 至 ${\displaystyle B}$ 的單射，當且僅當對每個 ${\displaystyle D\subseteq A}$，皆有其鄰域 ${\displaystyle N(D)\nless D}$。

代表系的數目

馬歇爾·霍爾也計算出給定有限族 ${\displaystyle S}$ 的代表系數目的下界，從而加強婚配定理。其敍述為：^[14]

設有一列有限集 ${\displaystyle (A_{1},A_{2},\ldots ,A_{n})}$，不必相異，但滿足霍爾條件，又設 ${\displaystyle |A_{i}|\geq r}$ 對 ${\displaystyle i=1,\ldots ,n}$ 成立。則當 ${\displaystyle r\leq n}$ 時，該族有限集至少有 ${\displaystyle r!}$ 個不同的代表系，而當 ${\displaystyle r>n}$ 時，至少有 ${\displaystyle r(r-1)\cdots (r-n+1)}$ 個。

此處即使兩個代表系的元素一樣，衹要其次序不同，亦視為不同。例如，若 ${\displaystyle A_{1}=\{1,2,3\}}$，${\displaystyle A_{2}=\{1,2,5\}}$，則 ${\displaystyle (1,2)}$ 和 ${\displaystyle (2,1)}$ 為兩個不同的代表系。

分數匹配

圖的分數匹配（fractional matching）是對各邊賦予非負權值，使每個頂點所連各邊的權值和不超逾 ${\displaystyle 1}$。所謂 ${\displaystyle X}$ 完美的分數匹配，即是使 ${\displaystyle X}$ 中的每一頂點處，各邊權之和恰為 ${\displaystyle 1}$。對於二部圖 ${\displaystyle G=(X\sqcup Y,E)}$，下列各項等價：^[15]

• ${\displaystyle G}$ 有 ${\displaystyle X}$ 完美匹配。
• ${\displaystyle G}$ 有 ${\displaystyle X}$ 完美分數匹配。（此為前項的直接推論。給定一個 ${\displaystyle X}$ 完美匹配，將該匹配所選的邊賦權 ${\displaystyle 1}$，其餘邊賦 ${\displaystyle 0}$，則得到 ${\displaystyle X}$ 完美分數匹配。）
• ${\displaystyle G}$ 滿足霍爾條件。（若有前項的分數匹配，則對於 ${\displaystyle X}$ 的每個子集 ${\displaystyle W}$，其所連各邊之和恰為 ${\displaystyle |W|}$，故至少要與對面的 ${\displaystyle |W|}$ 個頂點相連，因為對面每個頂點所連的邊值和不超過 ${\displaystyle 1}$。）

虧缺

主条目：虧度 (圖論)（英语：Deficiency (graph theory)）

假如霍爾條件不成立，則原定理僅斷言不存在完美匹配，但並未說明匹配最大可以多大。欲知此事，需要考慮圖的虧度（英语：Deficiency (graph theory)）。對於二部圖 ${\displaystyle G=(X\sqcup Y,E)}$，${\displaystyle G}$ 關於 ${\displaystyle X}$ 的虧度（deficiency）是 ${\displaystyle |W|-|N_{G}(W)|}$ 的最大值，其中 ${\displaystyle W}$ 可取 ${\displaystyle X}$ 的任意子集。虧度越大，則圖離霍爾條件越遠。

用霍爾定理可證，若二部圖的虧度為 ${\displaystyle d}$，則有大小為 ${\displaystyle |X|-d}$ 的匹配。（考慮在 ${\displaystyle Y}$ 側添加 ${\displaystyle d}$ 個輔助點，與 ${\displaystyle X}$ 所有頂點連邊。新圖將滿足霍爾條件。）

非二部圖

• 若推廣至一般的圖（不必為二部圖），則其上有完美匹配的充要條件，由塔特定理描述。
• 若推廣至各類二部超圖（英语：bipartite hypergraph）（二部圖的超圖版本），則相應有各種霍爾式定理（英语：Hall-type theorems for hypergraphs）。