茶年 · 中文维基百科

霍爾婚配定理

Wikipedia · 2026-07-31 维基百科 👁 1 阅读

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

集族表述
設 S 為 X 的有限子集組成的有限多重族。

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

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

:|W| \le \left|\bigcup_{A \in W} A\right|.

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

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

證明見。

例
例一：考慮集族 S = \{A_1, A_2, A_3\}，其中
:\begin{align}
A_1 &= \{1, 2, 3\}, \\
A_2 &= \{1, 4, 5\}, \\
A_3 &= \{3, 5\}.
\end{align}

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

例二：考慮 S = \{A_1, A_2, A_3, A_4\}，其中
:\begin{align}
A_1 &= \{2, 3, 4, 5\},\\
A_2 &= \{4, 5\}, \\
A_3 &= \{5\},\\
A_4 &= \{4\}.
\end{align}

此時，無合適的代表系。子族 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{align}
A_1 &= \{1, 2, 3\},\\
A_2 &= \{2, 4\}, \\
A_3 &= \{1, 2, 4\},\\
A_4 &= \{2, 4\}.
\end{align}

此時，A_2 與 A_4 的代表必為 2, 4 或逆序，從而 A_3 的代表須為 1。所以，合適的代表系有且衹有 (3, 2, 1, 4) 或 (3, 4, 1, 2)。

命名
定理命名為「婚配」（），是與以下例子有關。設有兩組人，一組 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)| \ge |M(W)|，即 |N_G(W)| \ge |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| \le |Z| = |W| - 1 ，違反霍爾條件。

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

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

以下敍述算法的步驟：

初始時，設 M 為空集，未選定任何邊。（其後會加邊入 M。）

檢查：M 確為 G 的匹配。

若 M 已覆蓋 X，則為所求的 X 完美匹配，輸出並結束程序。

否則，找到未匹配的頂點 x_0 \in X \setminus V(M)。

調用尋找增廣路徑的子程序，視乎情況：

若找到霍爾犯，則輸出並結束。

若找到 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 ，則任意 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 的單射，當且僅當對每個 D \subseteq A，皆有其鄰域 N(D) \nless D。

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

設有一列有限集 (A_1, A_2, \ldots, A_n)，不必相異，但滿足霍爾條件，又設 |A_i| \ge r 對 i = 1, \ldots, n 成立。則當 r \le 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) 為兩個不同的代表系。

分數匹配
圖的分數匹配（）是對各邊賦予非負權值，使每個頂點所連各邊的權值和不超逾 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 的虧度（）是 |W| - |N_G(W)| 的最大值，其中 W 可取 X 的任意子集。虧度越大，則圖離霍爾條件越遠。

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

非二部圖

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

註
參考文獻
*
*
*
*
*
*
*
*
*

站外鏈結

#图论定理 #組合數學定理

评论 (0)

  • 还没有评论，来抢沙发吧。