Hall 定理

霍尔定理
术语名称	霍尔定理
英语名称	Hall's marriage theorem
别名	霍尔婚配定理

相异代表系
术语名称	相异代表系
英语名称	system of distinct representatives
别名	SDR

婚配条件
术语名称	婚配条件
英语名称	marriage condition

霍尔定理(Hall's marriage theorem)是关于二部图完美匹配的定理，二部图较少顶点集到另一个顶点集存在完美匹配当且仅当前者任意子集邻域大小不小于该集合本身。

定理

组合数学形式

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

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

图论形式

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

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