概念

匹配理论

最大匹配求「最多能配多少对」，霍尔定理给出二部图完美匹配的充要条件，稳定匹配算法（GS 算法）保证公平配对。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

匹配理论图论

01定义

匹配是两两无公共端点的边集。霍尔定理给出二部图完美匹配的充要条件（任何子集的邻居不少于自身），匈牙利算法高效求最大匹配，Gale-Shapley 稳定匹配算法则保证公平的双边配对。

二部图的完美匹配：左右顶点一一配对

二部图 $(X,Y)$ 存在饱和 $X$ 的匹配 $\iff$ 任意 $S\subseteq X$ ， $|N(S)|\geq|S|$ ——「邻居足够多」是配对的充要条件。

匈牙利算法沿增广路径翻转匹配（Berge 定理：最大 ⇔ 无增广路）， $O(VE)$ ；Hopcroft-Karp 达 $O(E\sqrt V)$ 。

Gale-Shapley 求婚算法总产出稳定配对（无人能通过私奔改善）；医院-住院医师、择校录取都以此为基础机制设计，获 2012 年诺贝尔经济学奖。

\forall S\subseteq X:\ |N(S)|\geq|S|\iff\text{饱和}\ X\ \text{的匹配存在}

柯尼希与霍尔 1930 年代建立二部匹配理论；埃杰瓦里 1965 年、Hopcroft-Karp 1973 年完善算法；盖尔与沙普利 1962 年提出稳定婚姻问题。

在线广告撮合、肾脏交换移植、住院医师规培分配、求职平台的双选机制——「公平配对」的数学与工程实现。

二分图匹配：增广路算法逐步为左侧节点找到互不冲突的右侧配对

step 已匹配左侧数0