匹配算法

破除误解：最大匹配不是稳定匹配，二部也不是一般图#

把「匹配」当成一种算法，会在三个方向上滑倒。第一，基数最大不等于权最大，也不等于稳定。医院–住院医（NRMP）要的是稳定的多对一分配，不是边数最多。Gale–Shapley 给出的匹配边数甚至不必最大。第二，二部匹配的工具不能原样搬到一般图。霍尔定理、网络流、Hopcroft–Karp 都依赖左右两侧没有内部边；奇数环一旦出现，增广路必须改成「花」的收缩。第三，匈牙利算法常被当成「二部匹配的唯一名字」。库恩 1955 年的匈牙利方法解决的是分配问题（带权完美匹配），它与无权重的增广路、与最小费用流是亲戚，但不是 Hopcroft–Karp 的别名。

另一个误解是：既然匹配可以化成最大流，匹配算法就没有独立内容。归约解释的是存在性与复杂度归属——二部基数匹配和单位容量流多项式等价。算法解释的是常数、层次与结构：分层 BFS 如何把多次增广摊到 $O(\sqrt{V})$ 轮，花如何在一般图上恢复增广路的奇偶。归约是地图，实现是地形。

二部匹配：霍尔定理与 Hopcroft–Karp#

霍尔婚姻定理给出完美匹配的组合刻画：左侧每个子集 $S$ 的邻域 $|N(S)|\ge|S|$。它不是算法，但它解释算法何时必须失败：最大匹配的 König 对偶说，最小顶点覆盖等于最大匹配基数——这是二部图特有的、把匹配连到最小割的那座桥。

增广路定理对所有图成立：匹配 $M$ 最大，当且仅当不存在 $M$-增广路。二部图上找增广路就是交替 BFS。反复增广给出 $O(VE)$。霍普克罗夫特与卡普 1973 年的算法把多条最短增广路收成一层：先从所有自由的左侧顶点同时 BFS，按距离分层，再在分层图里用 DFS 一次增广极大的一组顶点不交最短路。每轮结束，最短增广路长度严格增加。他们证明轮数 $O(\sqrt{V})$，于是时间 $O(E\sqrt{V})$。对稠密图这仍是经典界；对稀疏图与单位容量流，Dinic 算法给出同一数量级，因为二部匹配本来就是单位容量网络上的最大流。

带权二部匹配（分配问题）把边权最大化或把费用最小化。库恩的匈牙利方法在等价矩阵上反复调整对偶变量，直到出现完美匹配的等式子图。它与 Egerváry 的工作、与 Kuhn–Munkres 的实现传统连在一起，时间可做到 $O(n^3)$。同一问题是最小费用流的特例：源到左侧、右侧到汇、容量一，边权写在中间。Jonker–Volgenant 等后来的实现，关心的是常数与缓存，不是新的复杂度类。

一般图：花、收缩与多面体#

非二部图的增广路上，奇数环会让「交替」的奇偶塌掉：沿着环走一圈，匹配边与非匹配边的角色无法一致地延伸。埃德蒙兹的花是这样一个奇数环，基点（base）是环上沿交替树到达的那个顶点。算法把整朵花收缩成一个超顶点，在收缩图上继续找路；找到增广后按嵌套顺序展开。正确性依赖的是：收缩不制造假增广，也不丢掉真增广。实现上要用并查集维护花、用双亲指针展开，细节以 Galil、Micali–Vazirani 以及后来的线性时间近邻算法为界，教学上仍以 Edmonds 的收缩为准。

Edmonds 还给出匹配多面体：用「奇数集不等式」描述完美匹配的凸包，使最大权匹配成为多项式可分的线性规划。这是「好的刻画」的精确含义：对偶证书短，可在多项式时间验证。一般图的最大权匹配因此与二部情形一样属于 P，尽管组合结构更重。Gabow、Lawler 等人把时间界从原始的高次多项式一路压下来；对稠密图，目前的实用实现仍常回到带权花或归结到带权二部加技巧。

没有花，霍尔定理在一般图上没有直接对应。Tutte–Berge 公式用「缺省数」刻画最大匹配基数：删掉一个顶点集后，奇数连通分量的过剩决定匹配亏多少。它是霍尔定理的非二部亲戚，同样先于算法给出证书。

稳定匹配：Gale–Shapley 与医院–住院医#

Gale–Shapley 的延迟接受算法假定两侧各有严格偏好。主动方按偏好列表求婚，被动方在当前求婚者中保留最好的、拒绝其余；被拒者继续向下。算法在 $O(n^2)$ 次求婚内终止，产出稳定匹配：不存在未配对的一对，彼此都更喜欢对方而不是自己的配偶。主动方得到对自己最优的稳定匹配，被动方得到对自己最差的稳定匹配——这是定理，不是实现细节。

医院–住院医问题把一侧改成有容量的多对一。NRMP 使用的匹配算法是 Gale–Shapley 的这个推广。真偏好、截断列表、夫妻成对申请，会破坏朴素算法的性质：可能不存在稳定匹配，或稳定匹配的集合结构更复杂。Roth 的机制设计工作说明：没有一种稳定机制能同时让双方都把诚实申报当成优势策略。匹配算法在这里离开图论，进入激励相容。边还是那些边，但算法必须声明谁求婚、信息如何提交，否则「稳定」只在纸面上。

稳定匹配与最大基数匹配可以冲突。一个稳定匹配可能留下本可匹配的人，因为稳定性禁止某些边。工程上若目标是「尽量多的人有岗」，应走 Edmonds 或 Hopcroft–Karp；若目标是「没有人能通过私下改签同时变好」，应走 Gale–Shapley。把招聘系统说成「用了匹配算法」而不声明目标，等于没说。

与网络流的关系#

二部基数匹配 $\leftrightarrow$ 单位容量最大流，是教材里最干净的归约：源连左侧容量 1，右侧连汇容量 1，中间边容量 1。最大流的值等于最大匹配基数；整数流给出匹配。最小割对应最小顶点覆盖，这正是 König 定理。Dinic、Push–relabel 因此都是二部匹配算法。Hopcroft–Karp 可以读成 Dinic 在这个特殊网络上的分层。

带权匹配对应最小费用流或运输问题。环消减、连续最短路（对偶上的 Dijkstra / Johnson 势）给出多项式算法。一般图没有同样干净的「加一个源汇就结束」：花不等式不是普通边容量。仍可以把某些带权匹配嵌入更复杂的流或线性规划分离神谕，但那已经是归约的高级形态。

流还解释为什么匹配有快速算法而一般整数线性规划没有。匹配的约束矩阵（二部情形）是全幺模的，顶点解自动整数。一般图靠的是奇数集分离而不是全幺模。算法快，是因为多面体好，不是因为「图比矩阵简单」。

Dinic 算法在单位容量网络上的 $O(E\sqrt{V})$ 与 Hopcroft–Karp 同阶，不是巧合：分层图里最短增广路长度递增，单位容量使一条路上的阻塞边立刻饱和。把二部匹配手写成流网络再调用通用最大流，常数通常更差，因为源汇边、反向边和距离标号要多维护一层。教学上仍值得走一遍归约，实现上专用匹配代码会去掉源汇、直接在左右顶点上交替。

Micali 与 Vazirani 1980 年把一般图基数匹配也推到 $O(E\sqrt{V})$，用「花」与「基」的精细距离代替二部的分层 BFS。它是理论上的对称结果：非二部并不必然多一个 $V$ 的因子。工程库很少直接实现原文，因为花的嵌套与双重亲指针极易写错；Gabow 的带权算法与后来的代数匹配（Mucha–Sankowski 的随机矩阵，时间 $\tilde O(n^\omega)$）提供另一条线。代数方法把匹配数的奇偶或行列式插值变成矩阵乘法，对稠密图渐近好看，对稀疏图通常输给组合增广。

匈牙利方法里的对偶在算什么#

分配问题要在 $n\times n$ 费用矩阵上选 $n$ 个不同行、不同列的位置，使权和最小（或最大）。库恩把匈牙利数学家 König、Egerváry 的组合论证写成可执行的矩阵操作：维持行势 $u_i$ 与列势 $v_j$，使 $\tilde c_{ij}=c_{ij}-u_i-v_j\ge 0$，并在零费用子图上找完美匹配。若尚未完美，沿未覆盖顶点的交替树调整势，制造新的零，同时保持对偶可行。终止时，互补松弛给出最优：匹配边费用等于势之和。

这与最短路对偶是同一套数。连续最短路算法把未匹配的左侧顶点看成源，在等式子图上跑 Dijkstra（用势把边权变成非负），把最短路树当成一次增广。Johnson 势保证非负，于是不必 Bellman–Ford。每增广一次匹配基数加一，最多 $n$ 轮，每轮近似一次 $O(n^2)$ 的最短路，总时间 $O(n^3)$。更细的实现用 Fibonacci 堆或邻接表，把稀疏费用矩阵的常数压下来。把匈牙利理解成「在 Excel 里画圈」，会丢掉它是原始–对偶的事实：圈是匹配，势是对偶变量。

多对一分配（每所医院容量 $c_h$）把右侧顶点复制 $c_h$ 份，或在流网络里把医院到汇的容量改成 $c_h$。稳定版本不能这样复制完事，因为偏好是关于医院而不是关于病床副本；Gale–Shapley 的医院–住院医算法直接在容量上延迟接受。优化目标与稳定目标再次分叉：最小费用分派可以不稳定，稳定匹配的总权可以次优。

稳定匹配的格子、农村医院与夫妻#

稳定匹配的集合在偏序下构成分配格：男方最优与女方最优是格的两端，中间的稳定匹配可以用「轮换」从一端走到另一端。格子结构解释了为什么可以在稳定匹配之间做改进而不离开稳定集合——这也是 Roth 讨论「农村医院定理」的背景：某些医院在所有稳定匹配里录取人数相同，于是单靠换稳定机制填不满农村名额。机制设计必须在稳定之外加入补贴或约束，不能指望换一个求婚方向就改变那些医院的度数。

NRMP 在 1990 年代把算法改成以住院医为求婚方，以回应「医院最优对住院医不公」的批评。边的集合没变，改变的是格上的选择点。夫妻成对申请把问题变成 NP 完全：可能不存在稳定匹配，搜索也不能再靠一次延迟接受。真实市场用启发式、允许部分不稳定或限制夫妻列表长度。理论告诉你何时算法消失，市场告诉你消失之后行政如何凑合。

偏好严格的假设也是理论脚手架。并列名次、截断列表、不完全列表，会使稳定定义出现弱稳定、强稳定、超稳定几种。算法仍在延迟接受家族里，但拒绝规则与保留规则要改。把 Gale–Shapley 当成「排序后配对」的一句话实现，会在并列处产生未定义行为。

代价与争议#

$O(E\sqrt{V})$ 在稀疏图上仍可能慢于精心实现的 $O(VE)$ 启发式，因为分层与内存跳跃有常数。竞赛图与生物网络上，人们常常先跑贪心加局部增广，再在需要证书时切换到完整算法。复杂度界是最坏情况地图，不是运行时间预测。

稳定匹配的公平性争议是结构性的。男方最优意味着女方最差（在双方都诚实申报时）。医院最优意味着住院医最差。谁被指定为求婚方，就是在分配剩余。2012 年诺贝尔经济学奖授予 Roth 与 Shapley，不是因为算法突然变快，而是因为市场设计必须把这笔剩余说清楚，并处理夫妻、农村医院等真实约束。

一般图匹配的实现长期落后于理论。花的嵌套、权的对偶更新，使正确实现稀缺。许多库只提供二部匹配，并把一般图匹配交给近似或启发式。理论说问题在 P，工程上仍可能把它当难题——这不是矛盾，是实现复杂度。

跨域连接#

• 图论：匹配是图论里少数同时拥有增广路定理、霍尔/Tutte 刻画和多项式算法的结构。König 定理把二部最大匹配钉到最小顶点覆盖，Tutte–Berge 把一般图的亏数写成奇数分量。算法论文里的花、分层、交替树，都是在图上维护这些刻画，而不是另起一套启发式。
• 组合学：霍尔定理是典型的组合充分必要条件，Edmonds 的奇数集不等式则把组合障碍翻译成多面体的刻面。计数完美匹配的个数是 #P 完全的，但找一个最大匹配在 P 里——对象同为匹配，计数与优化分道。组合学区分「有多少」与「最大有多好」，匹配算法站在后者。
• 纳什均衡：稳定匹配要求没有一对能通过偏离而同时变好，这是一种成对稳定，而不是混合策略均衡。Gale–Shapley 给出的是确定性匹配，激励问题问的是申报博弈里诚实是否均衡。把稳定匹配直接叫成纳什均衡会混掉策略空间：一边是图上的成对阻塞，一边是偏好申报的博弈。
• 线性代数：分配问题的匈牙利方法在矩阵上做行列加减，本质是维护对偶可行的势；匹配多面体的分离则把奇数集约束交给优化神谕。全幺模说明二部关联矩阵的线性规划松弛已经是整数的。线性代数在这里不是特征值，而是约束矩阵如何保证顶点解为 0-1。势与费用矩阵的差是一次显式的对角缩放，最优性来自互补松弛而不是来自特征值间隙。

参考文献#

• Edmonds, J. "Paths, Trees, and Flowers." Canadian Journal of Mathematics 17:449–467, 1965.
• Hopcroft, J. E. & Karp, R. M. "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs." SIAM Journal on Computing 2(4):225–231, 1973.
• Kuhn, H. W. "The Hungarian Method for the Assignment Problem." Naval Research Logistics Quarterly 2:83–97, 1955.
• Gale, D. & Shapley, L. S. "College Admissions and the Stability of Marriage." The American Mathematical Monthly 69(1):9–15, 1962.
• Roth, A. E. & Sotomayor, M. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, 1990.

延伸阅读#

• Lovász, L. & Plummer, M. D. Matching Theory. North-Holland, 1986; AMS Chelsea reprint, 2009.
• Kleinberg, J. & Tardos, É. Algorithm Design. Addison-Wesley, 2005. 第七章（网络流与二部匹配）。