第 11 讲 · 二分图与匹配

匹配把教师—课程、学生—学校等两类对象之间的可选关系，转成一组互不冲突的边。

二分图等价于没有奇圈

若顶点集能分成互不相交的 $X,Y$，且每条边都跨越两部，图就是二分图。完全二分图 $K_{m,n}$ 连接 $X$ 与 $Y$ 的所有可能顶点对。

非平凡无向图是二分图，当且仅当它没有奇长度圈。算法上从任一顶点开始按 BFS 层数奇偶染两色；若发现一条边连接同色顶点，就得到奇圈证据。

极大匹配不等于最大匹配

匹配 $M$ 是一组没有公共端点的边。被匹配边关联的顶点称为饱和顶点。

• 极大匹配：已经不能再直接加入一条边；
• 最大匹配：在所有匹配中边数最多；
• 从较小一部到另一部的完备匹配：较小一部每个顶点都被饱和；
• 完美匹配：两部大小相同且所有顶点都被饱和。

最大匹配一定极大，但一个糟糕的局部选择可能很快得到极大匹配，却还没有达到最大。

增广路让匹配数增加一

相对于当前匹配 $M$，交替路上的边依次“不在 $M$、在 $M$、不在 $M$……”；若两个端点都未饱和，它就是增广路。

把增广路上的边身份全部翻转：原来未匹配的边加入，原来匹配的边移除。因为增广路的未匹配边比匹配边多一条，新匹配的边数恰好增加一，同时每个内部顶点仍只关联一条匹配边。

Berge 判据在二分图课件中表述为：$M$ 是最大匹配，当且仅当不存在相对于 $M$ 的增广路。匈牙利算法的核心就是反复寻找并翻转增广路，直到找不到为止。

Hall 定理检查整组候选是否够用

对 $S\subseteq X$，记它在 $Y$ 中的邻域为 $\Gamma(S)$。存在覆盖 $X$ 的匹配，当且仅当：

$$\forall S\subseteq X,\quad |\Gamma(S)|\geq |S|.$$

必要性很直观：$S$ 中每个顶点都要匹配到不同对象，候选邻居不能比人少。充分性则可由最大匹配和增广路反证：若仍有未匹配的 $X$ 顶点，沿交替边扩展会迫使邻域不足，与 Hall 条件矛盾。

课件还给出一个易检查的充分条件：若 $X$ 中每点度数至少为 $t$，$Y$ 中每点度数至多为 $t$，则存在覆盖 $X$ 的匹配。它能快速保证 Hall 条件，却不是必要条件。