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] 个顶点邻接。