霍爾婚配定理

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

 集族表述 

設  為  的有限子集組成的有限多重族。

 的一個是  至  的單射，且該單射  將族中任意集合  映至該集合的某元素 。換言之， 從  中每個集合，選出一個代表元，使得不同的集合由不同元素代表（「單射」之義）。代表系又稱為「截面」或「遍歷」（）。

族  滿足霍爾條件，意思是對每個子族 ，有

用文字複述，該條件斷言對於  的每個子族，其各集合一共擁有的不同成員數，不小於該子族的集合數。若不滿足該條件，則不存在代表系，因為在某子族 （設有  個集合）中，各集合一共衹有少於  個互異元素，如此由鴿巢原理，為  個集合所選的  個代表元之中，必有兩者相等。霍爾定理說明，前述命題的否命題也成立，即若滿足霍爾條件，則必存在代表系。
霍爾定理：一族有限集有代表系，當且僅當其滿足霍爾條件，即其任意子族皆滿足以上不等式。
證明見。

 例 
例一：考慮集族 ，其中

合適的代表系有 ，但並不唯一，例如  亦可。

例二：考慮 ，其中

此時，無合適的代表系。子族  違反霍爾條件，因為該族有  個集合，但該三個集之並為 ，僅得兩個元素。

例三：同樣設 ，但換成

此時， 與  的代表必為  或逆序，從而  的代表須為 。所以，合適的代表系有且衹有  或 。

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

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

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

 圖論表述 
設  為有限二部圖，頂點集分為 、 兩部，以符號記為 。 完美匹配是圖上若干條邊組成的匹配，其兩兩無公共端點，且  的每個頂點各有一條邊在該匹配中。

對於  的任意子集 ，設  為  在  中的，即  中與  至少一點有連邊的全體頂點之集。霍爾定理斷言，存在  完美匹配，当且仅当對  的每個子集 ，皆有：

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

 證明 

「」：假設有匹配 ，覆蓋頂點集 。欲證霍爾條件對全部  成立。記  為  經  匹配到的頂點集，其為  的子集。由匹配的定義，必有 ，同時 ，因為  的元素皆為  的鄰舍。故 ，即 。

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

 算法 
若  的子集  滿足 ，則定義  為。若  為霍爾犯，則無匹配能覆蓋  的全部頂點。所以，也無匹配覆蓋 。霍爾定理斷言，二部圖有  完美匹配，當且僅當其不含任何霍爾犯。以下算法驗證定理較難的方向：輸入一幅二部圖，算法或輸出一個  完美匹配，或輸出一個霍爾犯。

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

以下敍述算法的步驟：
 初始時，設  為空集，未選定任何邊。（其後會加邊入 。）
 檢查： 確為  的匹配。
 若  已覆蓋 ，則為所求的  完美匹配，輸出並結束程序。
 否則，找到未匹配的頂點 。
 調用尋找增廣路徑的子程序，視乎情況：
 若找到霍爾犯，則輸出並結束。
 若找到  增廣路徑，則將該路徑上各邊的狀態翻轉，使  的邊數增加一。返回第2步。

每次找到增廣路徑，都會使  多一條邊。所以，前述算法的迴圈至多執行  次，就會停機。每次尋找增廣路徑需時 。總時間複雜度與不加權的的福特-富爾克森算法相約。

 兩種表述等價 

設 ，其中  皆為有限集，不必相異。相應地，構造二部圖 ，一側頂點集  對應該  個集合，另一側頂點集  為該些集合之並。若  有元素 ，則在圖中連一條邊 。如此，族  的代表系即是  的  完美匹配，覆蓋  的全部頂點。所以，以集族表述的霍爾問題，容易化成圖論表述的霍爾問題。反之亦然：給定二部圖 ， 完美匹配相當於族  的代表系。

 其他證明 
利用的，可得霍爾定理的非構造性證明。

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

較抽象的應用有雙邊陪集遍歷。設  為群， 為其有限指數子群，則霍爾定理適用於證明存在集合 ，既是  各左陪集的代表系，又是各右陪集的代表系。

霍爾定理亦用於證明，若 ，則任意  皆可擴展成  拉丁矩陣，並可重複，直至得到完整的拉丁方陣。

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

 ：二部圖的最大匹配，與最小等大。
 （1931年），得名自、艾蓋瓦里·耶內兩位匈牙利數學家，是克尼格定理的加權推廣。
 门格尔定理（1927年）：邊最小割的大小，等於任意在所有頂點對之間可以找到的無公共邊的路徑的最大數量。結論換成頂點最小割與無公共（中間）頂點的路徑仍成立。
 最大流最小割定理（福特-富爾克森算法）：任意网络流中，最大流的值等於最小割。
 （1946年）：一個方陣為，當且僅當其為置換方陣的凸組合。
 ：覆蓋某偏序集所需的不交鏈數，與該集的最大反鏈等大。

欲要更具體描述各定理的關係，下列各等價關係有簡單證明：
迪爾沃思定理 ⇔ 霍爾定理 ⇔ 克尼格-艾蓋瓦里定理 ⇔ 克尼格定理。

 加強 

 無窮族 
細察菲利浦·霍爾原先的證明，發現可以將結論修改成對（有限集組成的）無窮族  仍成立。該證明直接使用佐恩引理。此外，也有較簡短的證明，用到命題邏輯的緊緻性定理：

設 。對每個  和 ，以命題  表示「 選為  的代表」。可以列出代表系須滿足的條件如下：
對應每個 ，各有一條命題斷言恰有一個  使  為真；
對應每對互異的  和 ，各有一條命題為 。
如此，代表系即等價於同時滿足以上各命題的賦值。由有限族的霍爾定理，對  的任意有限子集 ，相應的有限子族有代表系，故以上命題中，任意有限條皆可同時滿足。所以，由緊緻性定理，全部命題可同時滿足，即有整個無窮族的代表系。

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

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

設族  由可數多個集合  構成。該族滿足霍爾條件，但無法選出代表系。

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

圖中有  至  的單射，當且僅當對每個 ，皆有其鄰域 。
 代表系的數目 
馬歇爾·霍爾也計算出給定有限族  的代表系數目的下界，從而加強婚配定理。其敍述為：

設有一列有限集 ，不必相異，但滿足霍爾條件，又設  對  成立。則當  時，該族有限集至少有  個不同的代表系，而當  時，至少有  個。

此處即使兩個代表系的元素一樣，衹要其次序不同，亦視為不同。例如，若 ，，則  和  為兩個不同的代表系。

 分數匹配 
圖的分數匹配（）是對各邊賦予非負權值，使每個頂點所連各邊的權值和不超逾 。所謂  完美的分數匹配，即是使  中的每一頂點處，各邊權之和恰為 。對於二部圖 ，下列各項等價：

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

 虧缺 

假如霍爾條件不成立，則原定理僅斷言不存在完美匹配，但並未說明匹配最大可以多大。欲知此事，需要考慮。對於二部圖 ， 關於  的虧度（）是  的最大值，其中  可取  的任意子集。虧度越大，則圖離霍爾條件越遠。

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

 非二部圖 
 若推廣至一般的圖（不必為二部圖），則其上有完美匹配的充要條件，由塔特定理描述。
 若推廣至各類（二部圖的超圖版本），則相應有各種。

 註 

 參考文獻 

 站外鏈結 
 Cut-the-knot站，Marriage Theorem 
 Cut-the-knot站，Marriage Theorem and Algorithm 
 Lucky的筆記Hall's marriage theorem explained intuitively .

Category:离散数学定理
Category:图论