匹配：最优配对 | LLM Learning

上一篇 Art. 12: 网络流建立了”管道运输”的完整工具箱——Ford-Fulkerson、Edmonds-Karp、Dinic——能求出从源到汇的最大流量。文章末尾提到，二部匹配是单位容量网络流的特例。本文正式展开这个特例，并将它推广到更丰富的领域。

匹配问题回答的是一个朴素而普遍的问题：怎么把两组东西一一配对，使得配对数量最多（或总成本最低）？ 工人分配任务、医院匹配住院医师、肾脏移植的供体-受体配对、在线广告的实时竞价——这些看似不同的场景，都可以抽象为图上的匹配问题。

算法范式：增广路（匈牙利, Hopcroft-Karp）、对偶性（König 定理, Hungarian 对偶）

核心问题：怎么一一配对？

给定一张图 $G = (V, E)$ ，匹配（matching）是边集 $E$ 的一个子集 $M \subseteq E$ ，使得 $M$ 中没有两条边共享端点——每个节点最多参与一条匹配边。匹配的大小 $|M|$ 是匹配边的数量。

几个关键定义：

最大匹配（maximum matching）：大小最大的匹配。
完美匹配（perfect matching）：每个节点都被匹配， $|M| = |V|/2$ 。
自由节点（free/exposed vertex）：不在任何匹配边上的节点。

核心问题是：找到最大匹配。如果是加权图，则要找到总权重最大（或总成本最小）的完美匹配。

上图左侧是一个二部图的完美匹配：4 个工人和 4 个任务一一配对，粗实线是匹配边。右侧是一般图的最大匹配：6 个节点中有 3 对匹配。

核心思路：增广路 — 匹配变大的唯一途径

匹配问题的核心思路和网络流一脉相承——增广路。

交替路径（alternating path）：一条路径，其边在”匹配边”和”非匹配边”之间交替。

增广路（augmenting path）：一条交替路径，且两端都是自由节点。增广路的关键性质是：它包含的非匹配边比匹配边多一条。如果我们把路径上所有边的匹配/非匹配状态翻转——原来匹配的变成非匹配，原来非匹配的变成匹配——匹配数就增加 1。

Berge 定理（Berge, 1957）：一个匹配 $M$ 是最大匹配，当且仅当不存在关于 $M$ 的增广路。

这给出了一个简洁的算法框架：反复寻找增广路，找到就增广（翻转），直到找不到为止。不同的算法（匈牙利、Hopcroft-Karp、Edmonds Blossom）本质上都是这个框架，区别在于如何高效地找到增广路。

二部图最大匹配

二部图（bipartite graph） $G = (L \cup R, E)$ ：节点分为两个不相交的集合 $L$ 和 $R$ ，所有边都连接 $L$ 中的节点和 $R$ 中的节点。二部图上的匹配是最经典的情形。

匈牙利算法（增广路方法）

匈牙利算法（也称 Kuhn 的交替路径算法）是最直接的实现：

Hungarian(G = (L ∪ R, E)):
    M = ∅  // 初始空匹配
    for each u ∈ L:
        if u is free:
            从 u 做 DFS/BFS 寻找增广路
            if 找到增广路 P:
                M = M ⊕ P  // 翻转路径上的边
    return M

其中 $M \oplus P$ 表示对称差——把 $M$ 和 $P$ 中匹配/非匹配的状态翻转。

时间复杂度：每次 DFS/BFS 需要 $O(m)$ 时间（ $m = |E|$ ），最多增广 $O(n)$ 次（ $n = |V|$ ），总计 $O(nm)$ 。

走查：8 节点二部图上的匈牙利算法

下面的交互组件展示匈牙利算法在一个 8 节点二部图上的完整执行过程。观察每次增广如何通过翻转交替路径使匹配变大。

二部匹配走查（匈牙利算法）匹配数: 0

当前匹配: 空

步骤 1/16: 初始状态：无匹配边。我们将从每个自由 L 节点出发寻找增广路。

1 / 16

关键观察：

第 1、2 次增广简单直接：找到自由的 R 节点就完成
第 3 次增广路径变长：C → 2 → A → 1 → B → 3，涉及两次”沿匹配边回退”
第 4 次增广路径最长：D → 3 → B → 1 → A → 2 → C → 4，经过三次回退才找到自由节点 4

Hopcroft-Karp 算法

匈牙利算法每次只找一条增广路，而 Hopcroft-Karp（1973）的核心改进是：每轮用 BFS 找出所有最短增广路，然后用 DFS 同时增广多条。

算法分为两个阶段交替执行：

阶段 1：BFS 分层

从所有自由 L 节点同时出发
沿未匹配边到 R 节点（奇数层），沿匹配边回到 L 节点（偶数层）
一旦到达自由 R 节点，记录当前层数 $d$ ，不再继续深入
结果：知道了最短增广路的长度 $d$

阶段 2：DFS 增广

对每个自由 L 节点，在分层图中做 DFS 寻找长度为 $d$ 的增广路
找到的多条增广路必须点不相交（vertex-disjoint），这保证它们可以同时翻转
一轮中可能同时找到多条增广路

上图展示了 BFS 分层的概念：从自由 L 节点出发，交替经过未匹配边和匹配边，构建分层图。在分层图中做 DFS 找到多条点不相交的增广路。

复杂度分析：

每轮 BFS + DFS 的总时间是 $O(m)$
关键引理：每轮增广后，最短增广路的长度至少增加 2
最短增广路的长度上界是 $O(\sqrt{n})$ （因为如果有 $k$ 条长度 $\geq 2k+1$ 的增广路，则 $|M| \geq n/2 - k$ ，所以增广轮数 $\leq \sqrt{n}$ ）
总复杂度： $O(m\sqrt{n})$

复杂度对比

算法	时间复杂度	空间复杂度	适用场景
匈牙利算法（Kuhn）	$O(nm)$	$O(n + m)$	小规模二部匹配，实现简单
Hopcroft-Karp	$O(m\sqrt{n})$	$O(n + m)$	大规模二部匹配
网络流（Dinic）在单位容量图	$O(m\sqrt{n})$	$O(n + m)$	与 Hopcroft-Karp 等价

Hopcroft-Karp 本质上就是 Dinic 算法在单位容量二部图上的特化——BFS 分层对应 Dinic 的层次图构建，DFS 增广对应阻塞流。这不是巧合：二部最大匹配就是单位容量网络流。

Hall 定理：完美匹配何时存在？

在实际应用中，我们常常需要判断：二部图是否存在完美匹配？ Hall 定理给出了充要条件。

Hall 定理（Hall, 1935）：二部图 $G = (L \cup R, E)$ 中（ $|L| \leq |R|$ ），存在覆盖 $L$ 的匹配（ $L$ -完美匹配），当且仅当对 $L$ 的每个子集 $S \subseteq L$ ：

$|N(S)| \geq |S|$

其中 $N(S)$ 是 $S$ 的邻居集合（ $R$ 中所有与 $S$ 中某个节点相邻的节点）。

直觉：如果有一组 $k$ 个 L 节点总共只认识少于 $k$ 个 R 节点，那么无论怎么配对，这 $k$ 个 L 节点中必然有人落空——鸽巢原理。Hall 定理说的是：这是完美匹配不存在的唯一障碍。

Hall 定理的必要性显而易见：如果有完美匹配，那么 $S$ 中每个节点的匹配对象都不同，所以 $|N(S)| \geq |S|$ 。充分性的证明需要用到增广路的存在性，是组合数学的经典结果。

匹配 ↔ 网络流

二部最大匹配可以完全归约为网络流问题。构造方法在 Art. 12 末尾已经预告过：

添加源点 $s$ 和汇点 $t$
$s$ 连到每个 L 节点，容量 = 1
每个 R 节点连到 $t$ ，容量 = 1
原始二部图的每条边方向从 L 到 R，容量 = 1

在这个单位容量网络上，整数最大流 = 最大匹配数。流量为 1 的 L→R 边构成匹配。

为什么？ 因为所有容量都是 1（整数），Ford-Fulkerson 保证存在整数最优流。每个 L 节点入度 1（从 $s$ ），所以最多有 1 单位流通过；每个 R 节点出度 1（到 $t$ ），同理。因此 L→R 边上流量为 0 或 1，且每个节点最多参与一条流量为 1 的边——这恰好就是匹配的定义。

这个归约揭示了匹配与流的深刻联系，也解释了为什么 Hopcroft-Karp 和 Dinic 在单位容量图上复杂度相同。

König 定理：匹配 = 覆盖

上一站 Art. 10: 团与密子图介绍了独立集、顶点覆盖和 Gallai 对偶 $\alpha(G) + \beta(G) = |V|$ ，并预告了二部图上的一个更强结果。现在正式展开。

König 定理（König, 1931）：在二部图中，最大匹配 = 最小顶点覆盖。

$|M^*| = \beta(G)$

其中 $M^*$ 是最大匹配， $\beta(G)$ 是最小顶点覆盖数。

为什么成立？ 有两个方向要证：

$|M^*| \leq \beta(G)$ （对任意图成立）：顶点覆盖 $C$ 必须覆盖匹配 $M^*$ 的每条边，而 $M^*$ 的每条边需要 $C$ 中至少一个端点，所以 $|C| \geq |M^*|$ 。
$|M^*| \geq \beta(G)$ （只在二部图成立）：可以从最大匹配构造一个大小恰好为 $|M^*|$ 的顶点覆盖。构造方法使用交替路径树。

König 定理 + Gallai 定理的推论：在二部图中，最大独立集 = $|V|$ - 最大匹配。因此二部图上的独立集（一般图中 NP-hard）可以在多项式时间内求解。

从对偶性的角度：König 定理是 LP 对偶的特例。最大匹配的 LP 松弛的对偶就是最小顶点覆盖的 LP 松弛。在二部图上，LP 松弛恰好有整数最优解（因为二部图的约束矩阵是全幺模的），所以 LP 对偶的等式翻译成整数对偶的等式。在一般图上，LP 松弛可能有分数解，König 定理不成立。

加权二部匹配（Assignment Problem）

当每条边有权重/成本时，问题变成：找一个完美匹配（或最大权匹配），使得总权重最大（或总成本最小）。这就是经典的分配问题（Assignment Problem）。

Hungarian 算法

Kuhn（1955）提出的 Hungarian 算法（以匈牙利数学家 König 和 Egerváry 的工作命名）求解分配问题。时间复杂度 $O(n^3)$ ，其中 $n$ 是节点数。

算法的核心思想是维护对偶变量（dual variables） $u_i$ （对应 L 节点 $i$ ）和 $v_j$ （对应 R 节点 $j$ ），满足：

$u_i + v_j \leq w(i, j) \quad \forall (i, j) \in E$

（对于最大化问题；最小化问题则是 $u_i + v_j \leq c(i,j)$ ，初始化方式不同但原理相同。）

当 $u_i + v_j = w(i, j)$ 时，称边 $(i, j)$ 是紧的（tight）。Hungarian 算法只在紧边上寻找增广路。如果找不到增广路，就调整对偶变量，制造新的紧边，然后再尝试。

算法步骤（最小化版本，成本矩阵 $C$ ）：

行归约：每行减去该行最小值。 $u_i = \min_j C_{ij}$ 。
列归约：每列减去该列最小值。 $v_j = \min_i (C_{ij} - u_i)$ 。
在零元素（紧边）上找最大匹配。
如果匹配数 $= n$ （完美匹配），结束。
否则，用最少的行/列线覆盖所有零元素。如果线数 $< n$ $< n$ ：
- 找未覆盖元素的最小值 $\Delta$
- 未覆盖行减 $\Delta$ ，被覆盖列加 $\Delta$ （等价于调整 $u_i, v_j$ ）
- 回到步骤 3

复杂度：每次调整至少产生一个新零（紧边），每次匹配增广增加匹配数 1，总共需要 $O(n)$ 次增广，每次增广前的调整需要 $O(n^2)$ 时间，总计 $O(n^3)$ 。

数值例子

成本矩阵（工人 $\times$ 任务）：

$C = \begin{pmatrix} 8 & 4 & 7 \\ 5 & 2 & 3 \\ 9 & 4 & 8 \end{pmatrix}$

Step 1: 行归约（每行减行最小值）

行最小值： $[4, 2, 4]$ 。

$C' = \begin{pmatrix} 4 & 0 & 3 \\ 3 & 0 & 1 \\ 5 & 0 & 4 \end{pmatrix}$

Step 2: 列归约（每列减列最小值）

列最小值： $[3, 0, 1]$ 。

$C'' = \begin{pmatrix} 1 & 0 & 2 \\ 0 & 0 & 0 \\ 2 & 0 & 3 \end{pmatrix}$

Step 3: 在零元素上找匹配。零的位置： $(1,2), (2,1), (2,2), (2,3), (3,2)$ 。最大匹配：工人1-任务2, 工人2-任务1（或任务3）, 工人3-任务2（冲突）。一个可行匹配：工人1-任务2, 工人2-任务1。大小=2 $< 3$ 。

Step 4: 覆盖零。用行2和列2可以覆盖所有零（2条线 $< 3$ ）。未覆盖元素为 $(1,1)=1, (1,3)=2, (3,1)=2, (3,3)=3$ ，最小值 $\Delta = 1$ 。

调整：未覆盖行（行1, 行3）减1，被覆盖列（列2）加1。

$C''' = \begin{pmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 2 \end{pmatrix}$

零的位置： $(1,1), (1,2), (2,1), (2,3), (3,2)$ 。完美匹配：工人1-任务1, 工人2-任务3, 工人3-任务2。

最优分配：工人1→任务1（成本8），工人2→任务3（成本3），工人3→任务2（成本4）。总成本 = 15。

对偶解释：行归约量 $u = [4, 2, 4]$ ，列归约量 $v = [3, 0, 1]$ ，对偶目标值 $\sum u_i + \sum v_j = 14$ 。Step 4 的调整进一步增加对偶值，最终对偶最优值 = 原始最优值 = 15（强对偶性）。关键直觉是：行/列归约就是在设置对偶变量，使尽可能多的边变成紧边（成本归零），然后在紧边上找匹配。

一般图匹配

为什么比二部图难：奇数环

在二部图中，增广路搜索只需要简单的 BFS/DFS。但在一般图中，奇数环（odd cycle）会导致交替路径搜索”迷路”。

考虑一个三角形 $\{1, 2, 3\}$ 加上节点 4（连接 1）和节点 5（连接 3）。当前匹配 $M = \{1\text{-}2\}$ 。从自由节点 4 开始搜索：

$4 \to 1$ （非匹配边） $\to 2$ （匹配边） $\to 3$ （非匹配边）
但从 1 也可以到 3（非匹配边），而 3 可以到 2（非匹配边）——但 2 已经通过另一条路到达了

问题是：三角形 $\{1, 2, 3\}$ 是一个奇数环。在二部图中不存在奇数环，所以搜索不会出这个问题。在一般图中，奇数环会让同一个节点从两条路径到达，且两条路径的”奇偶性”不一致——一条把它标为 L 层，另一条把它标为 R 层。

Edmonds’ Blossom 算法

Edmonds（1965）在经典论文 “Paths, Trees, and Flowers” 中提出了解决方案：当搜索中发现奇数环（blossom）时，把整个环缩成一个超级节点（shrink），在缩小后的图上继续搜索。

Blossom 的定义：在增广路搜索过程中，如果从根节点（自由节点）开始的交替树中，两条交替路径在同一个节点相遇且长度奇偶性相同，那么这两条路径加上连接边构成一个奇数环——这就是一个 blossom。

算法流程：

从每个自由节点出发，构建交替树（alternating tree）
如果找到另一个自由节点——发现增广路，增广
如果在交替树中发现奇数环（blossom）——缩花：
- 将 blossom 中所有节点合并为一个超级节点 $B^*$
- $B^*$ 继承原来所有节点的邻接关系
- 在缩小后的图上继续搜索
如果找到增广路，在缩小图上增广，然后展开（expand）回原图
如果搜索完所有自由节点都找不到增广路——当前匹配是最大匹配

为什么缩花是正确的？ Edmonds 证明了：原图 $G$ 中存在增广路，当且仅当缩花后的图 $G/B$ 中存在增广路。直觉上，奇数环的特殊之处在于：环中任意一个节点都可以”旋转”匹配来配合外部增广路的需要——不管增广路从环的哪个节点进入，都能在环内找到合适的交替路径穿过或停留。

复杂度：基本 Edmonds 算法 $O(n^2 m)$ 。配合高效数据结构（如 Micali-Vazirani 算法, 1980），可以达到 $O(m\sqrt{n})$ ——与 Hopcroft-Karp 对二部图的复杂度相同。

加权一般图匹配

加权一般图匹配可以通过 Edmonds 的加权 blossom 算法求解，但实现极为复杂。实践中通常使用专门的库（如 Kolmogorov 的 Blossom V 实现）。

复杂度对比表

算法	时间复杂度	适用场景	图类型
匈牙利算法（Kuhn）	$O(nm)$	小规模无权二部匹配	二部图
Hopcroft-Karp	$O(m\sqrt{n})$	大规模无权二部匹配	二部图
Hungarian（加权）	$O(n^3)$	加权分配问题	加权二部图
Edmonds Blossom（基本）	$O(n^2 m)$	一般图最大匹配	一般图
Micali-Vazirani	$O(m\sqrt{n})$	一般图最大匹配（最优）	一般图
Edmonds Blossom（加权）	$O(n^3)$	加权一般图匹配	加权一般图

应用场景

任务分配

最经典的应用： $n$ 个工人和 $n$ 个任务，每个工人完成每个任务有不同的成本/效率。找到最小成本的一一分配。这正是加权二部匹配（分配问题），用 Hungarian 算法 $O(n^3)$ 求解。

稳定婚姻问题（Gale-Shapley）

$n$ 个男性和 $n$ 个女性，每人对异性有一个偏好排名。找一个”稳定”匹配：不存在一对男女，他们宁愿和对方配对而不是各自当前的伴侣。

Gale 和 Shapley（1962）提出的延迟接受算法（Deferred Acceptance）在 $O(n^2)$ 时间内找到稳定匹配。算法过程：每轮每个未配对的男性向他最偏好的尚未拒绝他的女性求婚；每个女性在当前的追求者中选择最偏好的（可能拒绝之前的暂定伴侣）。

这个算法在 2012 年获得了诺贝尔经济学奖（Roth 和 Shapley），因为它的实际影响巨大——美国的住院医师分配（NRMP）、学校选择系统都使用了它的变体。

肾脏交换配对

肾脏移植中，如果患者 A 的亲属愿意捐肾但血型不匹配，同时患者 B 的亲属也有类似问题，那么”交叉捐赠”可以解决：A 的亲属捐给 B，B 的亲属捐给 A。更一般地，这构成一个匹配/环交换问题。图中节点是”不匹配的供体-受体对”，边表示”交叉兼容”。最大匹配（或最大权匹配）最大化移植数量。

实践中还需要考虑环长度限制（同时手术的可行性）和利他供体链。美国的肾脏交换项目（如 UNOS Kidney Paired Donation）使用了整数规划 + 匹配算法的混合方法。

在线广告竞价

搜索引擎在用户搜索时需要实时分配广告位给广告主。这是一个在线二部匹配问题：广告位（查询）是”R 节点”逐个到达，广告主（出价者）是”L 节点”，算法需要在每个查询到达时立即做出不可撤销的分配。

Karp, Vazirani & Vazirani（1990）证明了在线二部匹配的最优竞争比（competitive ratio）是 $1 - 1/e \approx 0.632$ ——即没有在线算法能保证做到离线最优的 63.2% 以上。Google 的 AdWords 系统使用了加权在线匹配的变体。

🔁 迭代机器视角 — Hungarian Algorithm (Bipartite Matching)OPT: 优化目标

Graph	二部图
State[v]	匹配状态 matched(v)
SELECT	BFS/DFS 找增广路
COMBINE	沿增广路翻转匹配/非匹配边
重入	到不动点（无增广路）
TERMINATE	无增广路
求解方法	NESTED

嵌套结构：外层迭代找增广路 × 内层搜索交替路径

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — Hopcroft-KarpOPT: 优化目标

Graph	二部图
State[v]	匹配状态 + 层次标签
SELECT	BFS 分层 + DFS 找增广路
COMBINE	BFS 建层次图 → DFS 找多条不相交增广路 → 批量翻转
重入	到不动点
TERMINATE	BFS 找不到新的增广路
求解方法	NESTED

💡 对比: Hungarian: 同一问题，Hopcroft-Karp 用 BFS+DFS 批量增广 → O(E√V) vs O(VE)

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文建立了图上”配对”的完整工具箱：

增广路是匹配变大的唯一途径——Berge 定理奠定了所有匹配算法的理论基础
二部图匹配：匈牙利算法 $O(nm)$ 简单直接，Hopcroft-Karp $O(m\sqrt{n})$ 通过 BFS 分层 + 批量增广提速
匹配 ↔ 网络流：二部最大匹配 = 单位容量最大流，Hopcroft-Karp = Dinic 在单位容量图上的特化
König 定理：二部图最大匹配 = 最小顶点覆盖，是 LP 对偶在组合优化中的优美体现
Hall 定理：完美匹配存在 $\Leftrightarrow$ 每个子集 $S$ 的邻居数 $\geq |S|$
加权匹配：Hungarian 算法 $O(n^3)$ ，通过对偶变量维护紧边
一般图匹配：Edmonds Blossom 算法通过缩花处理奇数环

从算法范式的角度：

增广路范式贯穿始终——每次找到增广路就翻转，匹配加 1
对偶性再次闪耀——König 定理（匹配 = 覆盖）、Hungarian 对偶（行/列归约 = 对偶变量）

匹配是 Part 3”优”中将图的离散结构与优化理论连接最紧密的一章。下一篇 Art. 14: 图着色与划分将探讨另一类经典的组合优化问题——如何给图的节点着色或将图分成均衡的部分。

实现指引

算法	库	函数/方法
最大二部匹配 (Hopcroft-Karp)	NetworkX	`nx.bipartite.maximum_matching(G)`
最大权二部匹配	NetworkX	`nx.bipartite.minimum_weight_full_matching(G)`
最大匹配（一般图，Edmonds）	NetworkX	`nx.max_weight_matching(G)`
最小权完美匹配	NetworkX	`nx.min_weight_matching(G)`
最大二部匹配	scipy	`scipy.sparse.csgraph.maximum_bipartite_matching(graph)`
最大匹配	igraph	`g.maximum_matching()`
加权匹配	OR-Tools	`pywrapgraph.LinearSumAssignment()`
Blossom V（加权一般图）	独立库	Kolmogorov’s Blossom V
稳定匹配	Python `matching`	`matching.games.StableMarriage`