跳至內容

霍爾婚配定理

維基百科,自由的百科全書

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

集族表述

的有限子集[註 2]組成的有限[註 3]多重[註 4]

的一個代表系英語Transversal (combinatorics)單射,且該單射 將族中任意集合 映至該集合的某元素 。換言之, 中每個集合,選出一個代表元,使得不同的集合由不同元素代表(「單射」之義)。代表系又稱為「截面」或「遍歷」(transversal)。

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

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

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

證明見§ 圖論表述

例一:符合霍爾條件

例一:考慮集族 ,其中

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

例二:違反霍爾條件

例二:考慮 ,其中

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

例三:同樣設 ,但換成

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

命名

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

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

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

圖論表述

藍色邊構成一組匹配

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

對於 的任意子集 ,設 中的鄰域英語Neighbourhood (graph theory),即 中與 至少一點有連邊的全體頂點之集。霍爾定理斷言,存在 完美匹配,若且唯若 的每個子集 ,皆有:

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

證明

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

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

算法

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

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

以下敍述算法的步驟:

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

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

兩種表述等價

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

其他證明

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

應用

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

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

霍爾定理亦用於證明,若 ,則任意 拉丁矩陣英語Latin rectangle皆可擴展成 拉丁矩陣,並可重複,直至得到完整的拉丁方陣[8]

相關定理

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

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

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

加強

無窮族

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

。對每個 ,以命題 表示「 選為 的代表」。可以列出代表系須滿足的條件如下:

  • 對應每個 ,各有一條命題斷言恰有一個 使 為真[註 10]
  • 對應每對互異的 ,各有一條命題為

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

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

無窮集

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

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

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

圖中有 的單射,當且僅當對每個 ,皆有其鄰域

代表系的數目

馬歇爾·霍爾也計算出給定有限族 的代表系數目的下界,從而加強婚配定理。其敍述為:[14]

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

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

分數匹配

圖的分數匹配fractional matching)是對各邊賦予非負權值,使每個頂點所連各邊的權值和不超逾 。所謂 完美的分數匹配,即是使 中的每一頂點處,各邊權之和恰為 。對於二部圖 ,下列各項等價:[15]

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

虧缺

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

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

非二部圖

  1. ^ 婚配之名見於[1][2]
  2. ^ Hall, Jr. 1986,pg. 51。也可以允許無窮集,但此時須限制族中的集合數有限(考慮重數),見§ 推廣。然而,不能放寬成無窮多個無窮集。
  3. ^ 可以放寬為無窮族,見§ 推廣
  4. ^ 可以有重複的元素,且會考慮其重複次數
  5. ^ 此例子中,為使定理適用,需要假設該些人的婚姻為一夫一妻制
  6. ^ 即無法再延伸。
  7. ^ 定理的名稱,文獻中略有出入。相關的定理既有二分圖匹配的表述,也有 (0,1) 矩陣覆蓋的表述。Hall, Jr. (1986)van Lint & Wilson (1992)稱矩陣表述為克尼格定理,而Roberts & Tesman (2009)則稱之為克尼格-艾蓋瓦里定理。二部圖版本,Cameron (1994)Roberts & Tesman (2009)皆稱為克尼格定理。
  8. ^ 即行和與列和皆等於一,且各項非負。
  9. ^ 兩人並非親屬。
  10. ^ 此處的命題需要 為有限集,纔能用命題邏輯的語言寫出

參考文獻

  1. ^ 毛華; 龐雙傑. Hall婚配定理的新证明方法. 河北大學學報(自然科學版). 2008, 28 (2): 127–129. doi:10.3969/j.issn.1000-1565.2008.02.005. 
  2. ^ 王樹禾. 前言. 图论. 21世紀高等院校教材·信息與計算科學專業教材系列. 北京: 科學出版社. 2004: ii. ISBN 7-03-012423-5. 
  3. ^ Hall, Philip. On Representatives of Subsets [論子集之代表元]. J. London Math. Soc. 1935, 10 (1): 26–30. doi:10.1112/jlms/s1-10.37.26 (英語). 
  4. ^ 張鴻林; 葛顯良. 英汉数学词汇. 清華大學出版社. 2005: 299. 
  5. ^ Haxell, P. On Forming Committees [論委員會之組成]. The American Mathematical Monthly. 2011, 118 (9): 777–788 [2021-12-03]. ISSN 0002-9890. doi:10.4169/amer.math.monthly.118.09.777. (原始內容存檔於2021-12-03) (英語). 
  6. ^ DeVos, Matt. Graph Theory [圖論] (PDF). Simon Fraser University. [2021-12-03]. (原始內容 (PDF)存檔於2021-12-03) (英語). 
  7. ^ Button, Jack; Chiodo, Maurice; Zeron-Medina Laris, Mariano. Coset Intersection Graphs for Groups [群的陪集相交圖]. The American Mathematical Monthly. 2014, 121 (10): 922–26. doi:10.4169/amer.math.monthly.121.10.922 (英語). For H a finite index subgroup of G, the existence of a left-right transversal is well known, sometimes presented as an application of Hall’s marriage theorem. 
  8. ^ Hall, Marshall. An existence theorem for latin squares [拉丁方陣之存在定理]. Bull. Amer. Math. Soc. 1945, 51: 387–388. doi:10.1090/S0002-9904-1945-08361-X (英語). 
  9. ^ Borgersen, Robert D. Equivalence of seven major theorems in combinatorics [組合學七大定理之等價] (PDF). 2004-11-26 [2021-12-04]. (原始內容 (PDF)存檔於2021-05-07) (英語). 
  10. ^ Reichmeider 1984
  11. ^ 11.0 11.1 Hall, Jr. 1986,pg. 51
  12. ^ Cameron 1994,sec. 19.5
  13. ^ Aharoni, Ron. König's Duality Theorem for Infinite Bipartite Graphs [無窮二部圖的克尼格對偶定理]. Journal of the London Mathematical Society. February 1984, s2–29 (1): 1–12. ISSN 0024-6107. doi:10.1112/jlms/s2-29.1.1 (英語). 
  14. ^ Cameron 1994,p. 90
  15. ^ co.combinatorics - Fractional Matching version of Hall's Marriage theorem [co.組合學——霍爾婚配定理分數匹配版]. MathOverflow. [2020-06-29]. (原始內容存檔於2022-07-26) (英語). 

站外鏈結

本條目含有來自PlanetMathproof of Hall's marriage theorem》的內容,版權遵守共享創意協議:署名-相同方式共享協議