数学 上,霍爾婚配定理 [ 註 1] (英語:Hall's marriage theorem )是菲利浦·霍爾 最先證明[ 3] 的圖論 定理,又稱霍爾定理 [ 4] ,描述二分图 中,能將一側全部頂點牽線匹配 到另一側的充要條件 。定理另有一個等價的組合 敍述,確定一族有限 集合 在何種充要條件下,可自每個集合各揀選一個元素,而使所選元素兩兩互異(即沒有元素是重復的)。
集族表述
設
S
{\displaystyle S}
為
X
{\displaystyle X}
的有限子集 [ 註 2] 組成的有限[ 註 3] 多重 [ 註 4] 族 。
S
{\displaystyle S}
的一個代表系 是
S
{\displaystyle S}
至
X
{\displaystyle X}
的單射 ,且該單射
f
{\displaystyle f}
將族中任意集合
s
∈
S
{\displaystyle s\in S}
映至該集合的某元素
f
(
s
)
{\displaystyle f(s)}
。換言之,
f
{\displaystyle f}
從
S
{\displaystyle S}
中每個集合,選出一個代表元,使得不同的集合由不同元素代表(「單射」之義)。代表系又稱為「截面」或「遍歷」(transversal )。
族
S
{\displaystyle S}
滿足霍爾條件 ,意思是對每個子族
W
⊆
S
{\displaystyle W\subseteq S}
,有
|
W
|
≤
|
⋃
A
∈
W
A
|
.
{\displaystyle |W|\leq \left|\bigcup _{A\in W}A\right|.}
用文字複述,該條件斷言對於
S
{\displaystyle S}
的每個子族,其各集合一共擁有的不同成員數,不小於該子族的集合數。若不滿足該條件,則不存在代表系,因為在某子族
W
{\displaystyle W}
(設有
k
{\displaystyle k}
個集合)中,各集合一共衹有少於
k
{\displaystyle k}
個互異元素,如此由鴿巢原理 ,為
k
{\displaystyle k}
個集合所選的
k
{\displaystyle k}
個代表元之中,必有兩者相等。霍爾定理說明,前述命題的否命題也成立,即若滿足霍爾條件,則必存在代表系。
霍爾定理 :一族有限集有代表系,當且僅當其滿足霍爾條件,即其任意子族皆滿足以上不等式。
證明見§ 圖論表述 。
例
例一:符合霍爾條件
例一:考慮集族
S
=
{
A
1
,
A
2
,
A
3
}
{\displaystyle S=\{A_{1},A_{2},A_{3}\}}
,其中
A
1
=
{
1
,
2
,
3
}
,
A
2
=
{
1
,
4
,
5
}
,
A
3
=
{
3
,
5
}
.
{\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\},\\A_{2}&=\{1,4,5\},\\A_{3}&=\{3,5\}.\end{aligned}}}
合適的代表系有
(
1
,
4
,
5
)
{\displaystyle (1,4,5)}
,但並不唯一,例如
(
2
,
1
,
3
)
{\displaystyle (2,1,3)}
亦可。
例二:違反霍爾條件
例二:考慮
S
=
{
A
1
,
A
2
,
A
3
,
A
4
}
{\displaystyle S=\{A_{1},A_{2},A_{3},A_{4}\}}
,其中
A
1
=
{
2
,
3
,
4
,
5
}
,
A
2
=
{
4
,
5
}
,
A
3
=
{
5
}
,
A
4
=
{
4
}
.
{\displaystyle {\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
}
{\displaystyle W=\{A_{2},A_{3},A_{4}\}}
違反霍爾條件,因為該族有
|
W
|
=
3
{\displaystyle |W|=3}
個集合,但該三個集之並為
A
2
∪
A
3
∪
A
4
=
{
4
,
5
}
{\displaystyle A_{2}\cup A_{3}\cup A_{4}=\{4,5\}}
,僅得兩個元素。
例三:同樣設
S
=
{
A
1
,
A
2
,
A
3
,
A
4
}
{\displaystyle S=\{A_{1},A_{2},A_{3},A_{4}\}}
,但換成
A
1
=
{
1
,
2
,
3
}
,
A
2
=
{
2
,
4
}
,
A
3
=
{
1
,
2
,
4
}
,
A
4
=
{
2
,
4
}
.
{\displaystyle {\begin{aligned}A_{1}&=\{1,2,3\},\\A_{2}&=\{2,4\},\\A_{3}&=\{1,2,4\},\\A_{4}&=\{2,4\}.\end{aligned}}}
此時,
A
2
{\displaystyle A_{2}}
與
A
4
{\displaystyle A_{4}}
的代表必為
2
,
4
{\displaystyle 2,4}
或逆序,從而
A
3
{\displaystyle A_{3}}
的代表須為
1
{\displaystyle 1}
。所以,合適的代表系有且衹有
(
3
,
2
,
1
,
4
)
{\displaystyle (3,2,1,4)}
或
(
3
,
4
,
1
,
2
)
{\displaystyle (3,4,1,2)}
。
命名
定理命名為「婚配」(marriage ),是與以下例子有關。設有兩組人,一組
n
{\displaystyle n}
男,一組
n
{\displaystyle n}
女。每名女士心目中皆有一份名單(若干男士組成的子集),會接受名單中的男士的求婚,但會拒絕其他人。而該些男士別無所求,願意向任何女士求婚。媒人希望判斷是否存在方案,在尊重諸位女士的意願的前提下,將該兩組人撮合成
n
{\displaystyle n}
對夫妻[ 註 5] 。
以
A
i
{\displaystyle A_{i}}
表示第
i
{\displaystyle i}
名女士願意接受的男士集合,則霍爾定理講述,存在方案使每位女士與心儀對象結婚,且無重婚,當且僅當對於任意若干位女士組成的集合
I
{\displaystyle I}
,願意與其中至少一位女士結婚的男士數
|
⋃
i
∈
I
A
i
|
{\displaystyle \left|\bigcup _{i\in I}A_{i}\right|}
,不小於該集合的女士數
|
I
|
{\displaystyle |I|}
。
後一個條件為必要 ,否則該
|
I
|
{\displaystyle |I|}
名女士根本無法找到足夠的配偶。較不明顯的是,該條件亦為充分 ,此即霍爾定理的肯綮。
圖論表述
藍色邊構成一組匹配
設
G
{\displaystyle G}
為有限二部圖 ,頂點集分為
X
{\displaystyle X}
、
Y
{\displaystyle Y}
兩部,以符號記為
G
=
(
X
⊔
Y
,
E
)
{\displaystyle G=(X\sqcup Y,E)}
。
X
{\displaystyle X}
完美匹配 是圖上若干條邊組成的匹配 ,其兩兩無公共端點,且
X
{\displaystyle X}
的每個頂點各有一條邊在該匹配中。
對於
X
{\displaystyle X}
的任意子集
W
{\displaystyle W}
,設
N
G
(
W
)
{\displaystyle N_{G}(W)}
為
W
{\displaystyle W}
在
G
{\displaystyle G}
中的鄰域 ,即
Y
{\displaystyle Y}
中與
W
{\displaystyle W}
至少一點有連邊的全體頂點之集。霍爾定理斷言,存在
X
{\displaystyle X}
完美匹配,当且仅当 對
X
{\displaystyle X}
的每個子集
W
{\displaystyle W}
,皆有:
|
W
|
≤
|
N
G
(
W
)
|
.
{\displaystyle |W|\leq |N_{G}(W)|.}
換言之,與
W
{\displaystyle W}
相鄰的頂點,不少於
W
{\displaystyle W}
的頂點。上述不等式稱為霍爾條件。
證明
「
⟹
{\displaystyle \Longrightarrow }
」:假設有匹配
M
{\displaystyle M}
,覆蓋 頂點集
X
{\displaystyle X}
。欲證霍爾條件對全部
W
⊆
X
{\displaystyle W\subseteq X}
成立。記
M
(
W
)
{\displaystyle M(W)}
為
W
{\displaystyle W}
經
M
{\displaystyle M}
匹配到的頂點集,其為
Y
{\displaystyle Y}
的子集。由匹配的定義,必有
|
M
(
W
)
|
=
|
W
|
{\displaystyle |M(W)|=|W|}
,同時
M
(
W
)
⊆
N
G
(
W
)
{\displaystyle M(W)\subseteq N_{G}(W)}
,因為
M
(
W
)
{\displaystyle M(W)}
的元素皆為
W
{\displaystyle W}
的鄰舍。故
|
N
G
(
W
)
|
≥
|
M
(
W
)
|
{\displaystyle |N_{G}(W)|\geq |M(W)|}
,即
|
N
G
(
W
)
|
≥
|
W
|
{\displaystyle |N_{G}(W)|\geq |W|}
。
「
⟸
{\displaystyle \Longleftarrow }
」:假設無
X
{\displaystyle X}
完美匹配,欲證有某子集
W
⊆
X
{\displaystyle W\subseteq X}
違反霍爾條件。設
M
{\displaystyle M}
為極大匹配,換言之,若再添加任何一條邊,則不再為匹配。設
u
{\displaystyle u}
為
X
{\displaystyle X}
中未獲覆蓋的頂點。考慮由
u
{\displaystyle u}
出發的全體「交錯路徑」,即圖
G
{\displaystyle G}
中的路徑 ,其首邊不屬
M
{\displaystyle M}
,次邊屬於
M
{\displaystyle M}
,第三邊又不屬
M
{\displaystyle M}
,如此交錯排列。
u
{\displaystyle u}
藉該些交錯路徑,與
Y
{\displaystyle Y}
中若干頂點相連,該些頂點組成的子集記為
Z
{\displaystyle Z}
;又與
X
{\displaystyle X}
中若干頂點相連(此處
u
{\displaystyle u}
亦視為與自己相連),得子集
W
{\displaystyle W}
。極長[ 註 6] 的交錯路徑不能終於
Y
{\displaystyle Y}
,否則其首尾皆不屬
M
{\displaystyle M}
,故為「增廣路徑」:翻轉路徑上所有邊的狀態,將不屬
M
{\displaystyle M}
者加入
M
{\displaystyle M}
,屬
M
{\displaystyle M}
者移走,則得到嚴格比
M
{\displaystyle M}
多邊的匹配,此為不可能。至此,已證
Z
{\displaystyle Z}
中每個頂點,皆經
M
{\displaystyle M}
匹配到
W
∖
{
u
}
{\displaystyle W\setminus \{u\}}
中某頂點。反之,
W
∖
{
u
}
{\displaystyle W\setminus \{u\}}
中任意一個頂點,亦有
Z
{\displaystyle Z}
中某頂點與之匹配,即沿
u
{\displaystyle u}
至
v
{\displaystyle v}
的交錯路徑,
v
{\displaystyle v}
的前一頂點。所以,
M
{\displaystyle M}
給出
W
∖
{
u
}
{\displaystyle W\setminus \{u\}}
與
Z
{\displaystyle Z}
之間的一一對應,所以
|
W
|
=
|
Z
|
+
1
{\displaystyle |W|=|Z|+1}
。另一方面,將證明
N
G
(
W
)
⊆
Z
{\displaystyle N_{G}(W)\subseteq Z}
。設
v
∈
N
G
(
W
)
{\displaystyle v\in N_{G}(W)}
是與某頂點
w
∈
W
{\displaystyle w\in W}
鄰接。若邊
w
v
{\displaystyle wv}
在
M
{\displaystyle M}
中,則自
u
{\displaystyle u}
至
w
{\displaystyle w}
的一切交錯路徑中,
v
{\displaystyle v}
皆在
w
{\displaystyle w}
以先,故有
u
{\displaystyle u}
至
v
{\displaystyle v}
的交錯路徑。否則
w
v
{\displaystyle wv}
不屬
M
{\displaystyle M}
,但已知有
u
{\displaystyle u}
至
w
{\displaystyle w}
的交錯路徑,末邊屬於
M
{\displaystyle M}
,故可續以
w
v
{\displaystyle wv}
,亦得自
u
{\displaystyle u}
至
v
{\displaystyle v}
的交錯路徑。證畢
N
G
(
W
)
⊆
Z
{\displaystyle N_{G}(W)\subseteq Z}
,故
|
N
G
(
W
)
|
≤
|
Z
|
=
|
W
|
−
1
<
|
W
|
{\displaystyle \left|N_{G}(W)\right|\leq |Z|=|W|-1<|W|}
,違反霍爾條件。
算法
若
X
{\displaystyle X}
的子集
W
{\displaystyle W}
滿足
|
N
G
(
W
)
|
<
|
W
|
{\displaystyle |N_{G}(W)|<|W|}
,則定義
W
{\displaystyle W}
為霍爾犯 。若
W
{\displaystyle W}
為霍爾犯,則無匹配能覆蓋
W
{\displaystyle W}
的全部頂點。所以,也無匹配覆蓋
X
{\displaystyle X}
。霍爾定理斷言,二部圖有
X
{\displaystyle X}
完美匹配,當且僅當其不含任何霍爾犯。以下算法驗證定理較難的方向:輸入一幅二部圖,算法或輸出一個
X
{\displaystyle X}
完美匹配,或輸出一個霍爾犯。
該算法調用以下子程序:輸入匹配
M
{\displaystyle M}
及未匹配的某頂點
x
0
∈
X
{\displaystyle x_{0}\in X}
,或輸出一條
M
{\displaystyle M}
增廣路徑,或輸出一個霍爾犯。該子程序可以深度优先搜索 實作。
以下敍述算法的步驟:
初始時,設
M
{\displaystyle M}
為空集,未選定任何邊。(其後會加邊入
M
{\displaystyle M}
。)
檢查:
M
{\displaystyle M}
確為
G
{\displaystyle G}
的匹配。
若
M
{\displaystyle M}
已覆蓋
X
{\displaystyle X}
,則為所求的
X
{\displaystyle X}
完美匹配,輸出並結束程序。
否則,找到未匹配的頂點
x
0
∈
X
∖
V
(
M
)
{\displaystyle x_{0}\in X\setminus V(M)}
。
調用尋找增廣路徑的子程序,視乎情況:
若找到霍爾犯,則輸出並結束。
若找到
M
{\displaystyle M}
增廣路徑,則將該路徑上各邊的狀態翻轉,使
M
{\displaystyle M}
的邊數增加一。返回第2步。
每次找到增廣路徑,都會使
M
{\displaystyle M}
多一條邊。所以,前述算法的迴圈至多執行
|
X
|
{\displaystyle |X|}
次,就會停機。每次尋找增廣路徑需時
O
(
|
E
|
)
{\displaystyle {\mathcal {O}}(|E|)}
。總時間複雜度 與不加權的最大匹配問題 的福特-富爾克森算法 相約。
兩種表述等價
設
S
=
(
A
1
,
A
2
,
…
,
A
n
)
{\displaystyle S=(A_{1},A_{2},\ldots ,A_{n})}
,其中
A
i
{\displaystyle A_{i}}
皆為有限集,不必相異。相應地,構造二部圖
G
{\displaystyle G}
,一側頂點集
X
=
{
v
1
,
…
,
v
n
}
{\displaystyle X=\{v_{1},\ldots ,v_{n}\}}
對應該
n
{\displaystyle n}
個集合,另一側頂點集
Y
{\displaystyle Y}
為該些集合之並。若
A
i
{\displaystyle A_{i}}
有元素
y
∈
Y
{\displaystyle y\in Y}
,則在圖中連一條邊
v
i
y
{\displaystyle v_{i}y}
。如此,族
S
{\displaystyle S}
的代表系即是
G
{\displaystyle G}
的
X
{\displaystyle X}
完美匹配 ,覆蓋
X
{\displaystyle X}
的全部頂點。所以,以集族表述的霍爾問題,容易化成圖論表述的霍爾問題。反之亦然:給定二部圖
G
=
(
X
⊔
Y
,
E
)
{\displaystyle G=(X\sqcup Y,E)}
,
X
{\displaystyle X}
完美匹配相當於鄰域 族
{
Γ
(
x
)
:
x
∈
X
}
{\displaystyle \{\Gamma (x):x\in X\}}
的代表系。
其他證明
利用拓撲組合學 的斯佩納引理 ,可得霍爾定理的非構造性證明 。[ 5] :Thm.4.1,4.2
應用
定理有許多「非婚」應用。例如,取一疊啤牌 (無鬼牌),洗勻後,派成13磴,每磴4張。由霍爾定理可證,必能從每磴揀選一張牌,使所選13張牌恰好出齊各點數(A、2、3、⋯⋯、Q、K)。更一般地,任意正則 二部圖(允許重邊 )皆有完美匹配。[ 6] :2
較抽象的應用有雙邊陪集遍歷。設
G
{\displaystyle G}
為群 ,
H
{\displaystyle H}
為其有限指數 子群 ,則霍爾定理適用於證明存在集合
T
{\displaystyle T}
,既是
H
{\displaystyle H}
各左陪集 的代表系,又是各右陪集的代表系。[ 7]
霍爾定理亦用於證明,若
r
<
n
{\displaystyle r<n}
,則任意
r
×
n
{\displaystyle r\times n}
拉丁矩陣 皆可擴展成
(
r
+
1
)
×
n
{\displaystyle (r+1)\times n}
拉丁矩陣,並可重複,直至得到完整的拉丁方陣 。[ 8]
相關定理
本定理可歸類到組合學 的一列強力定理,其彼此關聯。若假設任何一條,則較易證得其他各條,但若要從頭開始 ,則較難證得任何一條。總括而言,該類定理各自斷言某類組合優化 問題具有強對偶性 。該些定理包括:
欲要更具體[ 9] [ 10] 描述各定理的關係,下列各等價關係有簡單證明:
迪爾沃思定理 ⇔ 霍爾定理 ⇔ 克尼格-艾蓋瓦里定理 ⇔ 克尼格定理。
加強
無窮族
馬歇爾·霍爾 細察菲利浦·霍爾 [ 註 9] 原先的證明,發現可以將結論修改成對(有限集組成的)無窮族
S
{\displaystyle S}
仍成立。[ 11] 該證明直接使用佐恩引理 。此外,也有較簡短的證明,用到命題邏輯 的緊緻性定理 :[ 12]
設
S
=
{
A
i
:
i
∈
I
}
{\displaystyle S=\{A_{i}:i\in I\}}
。對每個
i
∈
I
{\displaystyle i\in I}
和
a
∈
A
i
{\displaystyle a\in A_{i}}
,以命題
p
a
,
i
{\displaystyle p_{a,i}}
表示「
a
{\displaystyle a}
選為
A
i
{\displaystyle A_{i}}
的代表」。可以列出代表系須滿足的條件如下:
對應每個
i
∈
I
{\displaystyle i\in I}
,各有一條命題斷言恰有一個
a
∈
A
i
{\displaystyle a\in A_{i}}
使
p
a
,
i
{\displaystyle p_{a,i}}
為真[ 註 10] ;
對應每對互異的
i
,
j
∈
I
{\displaystyle i,j\in I}
和
a
∈
A
i
∩
A
j
{\displaystyle a\in A_{i}\cap A_{j}}
,各有一條命題為
¬
(
p
a
,
i
∧
p
a
,
j
)
{\displaystyle \neg (p_{a,i}\wedge p_{a,j})}
。
如此,代表系即等價於同時滿足以上各命題的賦值 。由有限族的霍爾定理,對
I
{\displaystyle I}
的任意有限子集
J
{\displaystyle J}
,相應的有限子族有代表系,故以上命題中,任意有限條皆可同時滿足。所以,由緊緻性定理,全部命題可同時滿足,即有整個無窮族的代表系。
以上一般情況的證明中,選擇公理 (或等價命題如佐恩引理)為必須,因為給定一族無窮多個非空 集(無額外條件),欲從每個集合中,選出一個代表(而無須相異),已需要選擇公理。
無窮集
馬歇爾·霍爾給出下列反例,表明若允許有無窮集,則所組成的無窮族,即使滿足霍爾條件,亦不保證有代表系。
設族
S
{\displaystyle S}
由可數多 個集合
A
0
=
{
1
,
2
,
3
,
…
}
,
A
1
=
{
1
}
,
A
2
=
{
2
}
,
…
,
A
i
=
{
i
}
,
…
{\displaystyle A_{0}=\{1,2,3,\ldots \},\ A_{1}=\{1\},\ A_{2}=\{2\},\ \ldots ,\ A_{i}=\{i\},\ \ldots }
構成。該族滿足霍爾條件,但無法選出代表系。[ 11]
若妥為敍述,則的確可將霍爾定理推廣至適用於無窮集。給定二部圖,兩側頂點集為
A
,
B
{\displaystyle A,B}
,若由
B
{\displaystyle B}
的子集
C
{\displaystyle C}
出發,在圖中找到單射(意思是衹能用二部圖的邊),射向
A
{\displaystyle A}
的子集
D
{\displaystyle D}
,則稱
C
≤
D
{\displaystyle C\leq D}
,而若更甚者,圖中沒有反向的,由
D
{\displaystyle D}
至
C
{\displaystyle C}
的單射,則稱
C
<
D
{\displaystyle C<D}
。前述定義中,若忽略「在圖中」三字,則所得大小的概念等同一般基數 的大小比較。無窮集的婚配定理斷言:[ 13]
圖中有
A
{\displaystyle A}
至
B
{\displaystyle B}
的單射,當且僅當對每個
D
⊆
A
{\displaystyle D\subseteq A}
,皆有其鄰域
N
(
D
)
≮
D
{\displaystyle N(D)\nless D}
。
代表系的數目
馬歇爾·霍爾也計算出給定有限族
S
{\displaystyle S}
的代表系數目的下界,從而加強婚配定理。其敍述為:[ 14]
設有一列有限集
(
A
1
,
A
2
,
…
,
A
n
)
{\displaystyle (A_{1},A_{2},\ldots ,A_{n})}
,不必相異,但滿足霍爾條件,又設
|
A
i
|
≥
r
{\displaystyle |A_{i}|\geq r}
對
i
=
1
,
…
,
n
{\displaystyle i=1,\ldots ,n}
成立。則當
r
≤
n
{\displaystyle r\leq n}
時,該族有限集至少有
r
!
{\displaystyle r!}
個不同的代表系,而當
r
>
n
{\displaystyle r>n}
時,至少有
r
(
r
−
1
)
⋯
(
r
−
n
+
1
)
{\displaystyle r(r-1)\cdots (r-n+1)}
個。
此處即使兩個代表系的元素一樣,衹要其次序不同,亦視為不同。例如,若
A
1
=
{
1
,
2
,
3
}
{\displaystyle A_{1}=\{1,2,3\}}
,
A
2
=
{
1
,
2
,
5
}
{\displaystyle A_{2}=\{1,2,5\}}
,則
(
1
,
2
)
{\displaystyle (1,2)}
和
(
2
,
1
)
{\displaystyle (2,1)}
為兩個不同的代表系。
分數匹配
圖的分數匹配 (fractional matching )是對各邊賦予非負權值,使每個頂點所連各邊的權值和不超逾
1
{\displaystyle 1}
。所謂
X
{\displaystyle X}
完美的分數匹配,即是使
X
{\displaystyle X}
中的每一頂點處,各邊權之和恰為
1
{\displaystyle 1}
。對於二部圖
G
=
(
X
⊔
Y
,
E
)
{\displaystyle G=(X\sqcup Y,E)}
,下列各項等價:[ 15]
G
{\displaystyle G}
有
X
{\displaystyle X}
完美匹配。
G
{\displaystyle G}
有
X
{\displaystyle X}
完美分數匹配。(此為前項的直接推論。給定一個
X
{\displaystyle X}
完美匹配,將該匹配所選的邊賦權
1
{\displaystyle 1}
,其餘邊賦
0
{\displaystyle 0}
,則得到
X
{\displaystyle X}
完美分數匹配。)
G
{\displaystyle G}
滿足霍爾條件。(若有前項的分數匹配,則對於
X
{\displaystyle X}
的每個子集
W
{\displaystyle W}
,其所連各邊之和恰為
|
W
|
{\displaystyle |W|}
,故至少要與對面的
|
W
|
{\displaystyle |W|}
個頂點相連,因為對面每個頂點所連的邊值和不超過
1
{\displaystyle 1}
。)
虧缺
假如霍爾條件不成立,則原定理僅斷言不存在完美匹配,但並未說明匹配最大可以多大。欲知此事,需要考慮圖的虧度 。對於二部圖
G
=
(
X
⊔
Y
,
E
)
{\displaystyle G=(X\sqcup Y,E)}
,
G
{\displaystyle G}
關於
X
{\displaystyle X}
的虧度 (deficiency )是
|
W
|
−
|
N
G
(
W
)
|
{\displaystyle |W|-|N_{G}(W)|}
的最大值,其中
W
{\displaystyle W}
可取
X
{\displaystyle X}
的任意子集。虧度越大,則圖離霍爾條件越遠。
用霍爾定理可證,若二部圖的虧度為
d
{\displaystyle d}
,則有大小為
|
X
|
−
d
{\displaystyle |X|-d}
的匹配。(考慮在
Y
{\displaystyle Y}
側添加
d
{\displaystyle d}
個輔助點,與
X
{\displaystyle X}
所有頂點連邊。新圖將滿足霍爾條件。)
非二部圖
註
參考文獻
^ 毛华; 庞双杰. Hall婚配定理的新证明方法. 河北大学学报(自然科学版). 2008, 28 (2): 127–129. doi:10.3969/j.issn.1000-1565.2008.02.005 .
^
王树禾. 前言. 图论. 21世纪高等院校教材·信息与计算科学专业教材系列. 北京: 科学出版社. 2004: ii. ISBN 7-03-012423-5 .
^ Hall, Philip . On Representatives of Subsets [論子集之代表元]. J. London Math. Soc. 1935, 10 (1): 26–30. doi:10.1112/jlms/s1-10.37.26 (英语) .
^ 张鸿林; 葛显良. 英汉数学词汇 . 清华大学出版社. 2005: 299.
^ 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) (英语) .
^ DeVos, Matt. Graph Theory [圖論] (PDF) . Simon Fraser University. [2021-12-03 ] . (原始内容 (PDF) 存档于2021-12-03) (英语) .
^ 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.
^ Hall, Marshall. An existence theorem for latin squares [拉丁方陣之存在定理]. Bull. Amer. Math. Soc. 1945, 51 : 387–388. doi:10.1090/S0002-9904-1945-08361-X (英语) .
^ Borgersen, Robert D. Equivalence of seven major theorems in combinatorics [組合學七大定理之等價] (PDF) . 2004-11-26 [2021-12-04 ] . (原始内容 (PDF) 存档于2021-05-07) (英语) .
^ Reichmeider 1984
^ 11.0 11.1 Hall, Jr. 1986 ,pg. 51
^ Cameron 1994 ,sec. 19.5
^ 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 (英语) .
^ Cameron 1994 ,p. 90
^ co.combinatorics - Fractional Matching version of Hall's Marriage theorem [co.組合學——霍爾婚配定理分數匹配版] . MathOverflow. [2020-06-29 ] . (原始内容 存档于2022-07-26) (英语) .
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 (英语)
站外鏈結
本條目含有来自PlanetMath 《proof of Hall's marriage theorem 》的內容,版权遵守知识共享协议:署名-相同方式共享 协议 。