MathLabs
定理已证明

霍尔婚配定理

命题陈述

设 G=(X∪Y,E)G=(X \cup Y, E) 是有限二分图。存在覆盖 XX 中所有顶点的匹配，当且仅当对任意子集 W⊆XW \subseteq X，其邻域 N(W)⊆YN(W) \subseteq Y 都满足 ∣N(W)∣≥∣W∣|N(W)| \ge |W|。

为什么成立?

如果某一群申请人 WW 合起来总共只符合少于 ∣W∣|W| 个岗位的条件，那么显然不可能把他们全都安排进不同的岗位。霍尔定理指出，这个对每个子集 WW 检验的显然必要条件实际上是唯一的障碍：只要没有任何子群出现瓶颈，完备匹配就一定存在。

证明思路

必要性是显然的，因为覆盖 XX 的匹配会把每个 W⊆XW \subseteq X 单射地映入 N(W)N(W)。充分性对 ∣X∣|X| 用归纳法：若对每个非空真子集 W⊂XW \subset X 都有 ∣N(W)∣≥∣W∣+1|N(W)| \ge |W|+1，则任取 x∈Xx \in X 与 y∈N({x})y \in N(\{x\}) 配对，并对仍满足霍尔条件的 G−{x,y}G - \{x,y\} 应用归纳假设；否则存在某个非空真子集 WW 达到紧界（∣N(W)∣=∣W∣|N(W)| = |W|），此时由归纳假设先将 WW 与 N(W)N(W) 匹配，并验证 X∖WX \setminus W 在 G−(W∪N(W))G - (W \cup N(W)) 中仍满足霍尔条件，从而由归纳假设将剩余顶点也完成匹配。

用到此定理的主题

图、度与路径

相关定理

握手引理

分步证明

该定理暂无分步证明。

参考文献

  1. Philip Hall (1935). On Representatives of Subsets