查看“︁Hall 定理”︁的源代码

[[分类:极值集合论]]
[[分类:匹配问题]]
{{InfoBox
|name=霍尔定理
|eng_name=Hall's marriage theorem
|aliases=霍尔婚配定理
}}
{{InfoBox
|name=相异代表系
|eng_name=system of distinct representatives
|aliases=SDR
}}
{{InfoBox
|name=婚配条件
|eng_name=marriage condition
}}
'''<ins>霍尔</ins>定理'''('''Hall's marriage theorem''')是关于[[二部图]][[完美匹配]]的定理，二部图较少顶点集到另一个顶点集存在完美匹配当且仅当前者任意子集邻域大小不小于该集合本身。

== 定理 ==

=== 组合数学形式 ===

对有限[[集族]] <math>\mathcal{F} = \{ A_1, A_2, \}</math> （元素可重复），其大小为 <math>n</math> ，记 <math>X = \bigcup \mathcal{F}</math> ，选择两两不同的 <math>x_1, x_2, \dots, x_n \in X</math> ，使得 <math>x_i \in A_i</math> ，称 <math>x_1,x_2,\dots,x_n</math> 为 <math>\mathcal{F}</math> 的一个'''相异代表系'''('''system of distinct representatives''', '''SDR''')。则有限可重集族 <math>\mathcal{F}</math> 存在相异代表系，当且仅当以下条件（称为'''婚配条件'''('''marriage condition''')）成立：
对任意 <math>\mathcal{G} \subseteq \mathcal{F}</math> 有 <math>\operatorname{card}\mathcal{G} \leq \operatorname{card}\bigcup_{S\in\mathcal{G}} S </math> 。

等价地，也可以表述为：对任意 <math>1\leq m\leq n</math> ， <math>\mathcal{F}</math> 中任意 <math>m</math> 个集合的[[并集]]至少包含 <math>m</math> 个元素。

=== 图论形式 ===

对二部图 <math>G = \langle X, Y, S \rangle</math> ，称边集 <math>E</math> 的不交且关联 <math>X</math> 全部顶点的子集为一个 '''<math>X</math>-完美匹配'''( '''<math>X</math>-perfect matching''')。存在一个 <math>X</math>-完美匹配，当且仅当对任意 <math>S \subseteq X</math> ，有 <math>\operatorname{card} S \leq \operatorname{card}\mathrm{N}_G(S)</math> 。

等价地，也可以表述为：对任意 <math>1\leq m\leq n</math> ， <math>X</math> 中任意 <math>m</math> 个顶点至少与 <math>Y</math> 中 <math>m</math> 个顶点邻接。