算法与数据结构 · 第32课
二分图最大匹配:为什么“撤销一条旧配对”反而能匹配更多人?
2026 年 11 月 20 日|第5周·第4天|讲授约17分钟(自测另计)
上一课的 Dinic 解决了“有容量的网络最多能送多少流”。今天要解决一类更具体的问题:三个候选人和三个任务,每人最多分配一个任务,每个任务最多由一人承担,如何使成功配对数最多?二分图匹配可以转化为容量全为1的最大流,但关键不只是建图,还在于理解反向残量边为何能重新安排旧配对。
一、学习目标与问题定义(约2分钟)
本节应掌握:①匹配与最大匹配的定义;②从二分图到最大流的三层网络构造;③交替路、增广路以及一次翻转如何使匹配数加1;④整数流和匹配的双向对应及正确性证明;⑤复杂度、适用边界与 Hopcroft–Karp 的动机。
| 二分图的顶点划成互不相交的两侧 L、R,边只连接左右两侧。匹配 M 是一组不共享端点的边;最大匹配最大化边数 | M | ,不是“不能直接再添加一条边”的极大匹配。后者只保证当前没有两端都空闲的边,可能远远不最优。 |
二、一个贪心陷阱:匹配不能只加不撤(约2分钟)
取 L={A,B,C},R={1,2,3},合法配对如下:
flowchart LR
subgraph L["左侧:候选人"]
A((A))
B((B))
C((C))
end
subgraph R["右侧:任务"]
X(("1"))
Y(("2"))
Z(("3"))
end
A --- X
A --- Y
B --- X
C --- Y
C --- Z
假设先选择 A–1、C–2。这是一个合法匹配,大小为2,B 没有可以直接加入的边,因为任务1已经被 A 占用。可这不代表最优:可以让 A 改做任务2,C 改做任务3,从而腾出任务1给 B。
这里的区别是:极大意味着不能直接增加一条互不冲突的边;最大意味着无论怎样整体重排,都无法得到更多配对。
三、交替增广路:一次翻转如何从2变3(约3分钟)
相对于当前匹配 M,交替路上的边依次为“未匹配、已匹配、未匹配、已匹配……”。如果这条简单路径的两端都是未匹配顶点,并以未匹配边开始和结束,就称为增广路。
对上述 M={A–1,C–2},有:
flowchart LR
B((B)) -->|"新增 B–1"| X(("1"))
X -->|"撤销 A–1"| A((A))
A -->|"新增 A–2"| Y(("2"))
Y -->|"撤销 C–2"| C((C))
C -->|"新增 C–3"| Z(("3"))
注意图上的右→左箭头并不是原二分图中允许任务“分配给人”的新边,而是在描述撤销旧匹配的方向。
| 状态 | 具体匹配边 | 匹配数 |
|---|---|---|
| 增广前 | A–1,C–2 | 2 |
| 翻转时 | 删除 A–1、C–2;加入 B–1、A–2、C–3 | — |
| 增广后 | B–1,A–2,C–3 | 3 |
路径内部的每个顶点原先匹配一次、翻转后仍匹配一次;两个原来空闲的端点各得到一条新边。因为新增的边比删除的边恰好多1条,最终匹配数增加1。这些边须作为一次整体翻转来理解,不能把中间状态当作完整的合法匹配。
四、最大流归约:把“最多一个”写成容量1(约3分钟)
将每条无向二分图边 u–v(u∈L,v∈R)改成有向边 u→v,容量为1;再引入源点 s 和汇点 t:
- 每个左点 u:加 s→u,容量1;
- 每条允许的配对 u–v:加 u→v,容量1;
- 每个右点 v:加 v→t,容量1。
flowchart LR
S((s)) -->|"1"| A((A))
S -->|"1"| B((B))
S -->|"1"| C((C))
A -->|"1"| X(("1"))
A -->|"1"| Y(("2"))
B -->|"1"| X
C -->|"1"| Y
C -->|"1"| Z(("3"))
X -->|"1"| T((t))
Y -->|"1"| T
Z -->|"1"| T
沿 s→A→1→t 送1单位,代表匹配 A–1。容量 c(s,A)=1 限制 A 最多匹配一次,容量 c(1,t)=1 限制任务1最多分给一人。所有配对都经过 s→左点→右点→t,因此总流值就是已成功配对的数量。
先沿 s→A→1→t 和 s→C→2→t 送流,得到前面的大小2匹配。之后的残量增广路恰为:
[ s\to B\to1\to A\to2\to C\to3\to t. ]
其中 1→A、2→C 是反向残量弧,分别撤销 A→1 和 C→2 上的流;其他正向弧增加流。瓶颈为1,增广后流值变成3,与翻转后的匹配一致。
五、正确性:为什么最大流值等于最大匹配数?(约3分钟)
证明分两边,不能只凭一个例子。
| 方向1:匹配 → 可行整数流。 对每个匹配边 u–v,在 s→u→v→t 上送1单位。由于匹配边不共享端点,任一 s→u 和 v→t 都不会超过容量1;左右顶点处进出流相等。所以得到了流值为 | M | 的可行整数流。 |
方向2:整数流 → 匹配。 因为所有容量都是1,整数流在每条弧上只能取0或1。左点从 s 最多收到1,且需满足流守恒,所以最多有一条 L→R 边流量为1;右点往 t 最多送1,因此最多有一条来自 L 的边流量为1。收集流量为1的 L→R 边,便得到一个无端点冲突的匹配,其大小恰好等于流值。
整数性从哪里来? 不是说任何可行的实数流都自动是整数流。我们从零流开始,所有容量均为整数,每次选残量路径的瓶颈也为整数,按正反弧增减后仍为整数。因此 Ford–Fulkerson、Edmonds–Karp 或 Dinic 运行后能得到整数最大流。双向对应立即推出:
[ \boxed{\text{二分图最大匹配边数}=\text{对应单位容量网络的最大流值}.} ]
六、没有增广路为什么就一定最大?(约2分钟)
这也是 Berge 增广路定理:一个匹配 M 是最大匹配,当且仅当不存在相对于 M 的增广路。
| 有增广路时,翻转可使 | M | 加1,显然不是最大。难点是反方向。假设 M 不是最大,存在更大的匹配 M。考虑对称差 M△M:只保留恰属于其中一个匹配的边。每个顶点在 M、M* 中分别最多有一条边,所以对称差图中顶点度数最多2,各连通分量是交替路径、偶环或孤立点。 |
| 因为 | M* | > | M | ,必有某个路径分量比 M 边多至少一条 M* 边。它必须以 M* 边开始和结束,且两个端点在 M 中均未匹配,这就是一条相对于 M 的增广路,矛盾。因此找不到增广路,匹配就是最大的。 |
这个证明说明反向边与交替路径不是小技巧,而是完整搜索最优解所必需的能力。
七、伪代码、复杂度与边界(约2分钟)
BIPARTITE_MATCHING(L, R, E):
建立 s→L、L→R、R→t 的单位容量网络
为每条原始弧建立配对反向残量弧
while BFS 在正残量网络中找到 s→t 路径 P:
沿 P 增广瓶颈 1,更新正反残量
M = { (u,v)∈E : 原始弧 u→v 的最终流量为1 }
return M
| 设 p= | L | 、q= | R | 、m= | E | 。新网络有 p+q+2 个顶点、p+q+m 条原始弧,建立耗时/空间均为 O(p+q+m)。每次增广增加1单位流,最多 min(p,q) 次。朴素做法每次 BFS 花 O(p+q+m),总时间: |
[ \boxed{O\big((p+q+m)\min(p,q)\big),\quad \text{空间 }O(p+q+m).} ]
若只做匹配、不需要通用流网络,可以直接用 DFS 寻找交替增广路;下一课的 Hopcroft–Karp 则借鉴 Dinic 的思想,一次 BFS 寻找最短增广路的层次,再尽量处理一批不相交的最短增广路,将一般二分图的时间改进为 (O(m\sqrt{p+q}))(通常忽略孤立点和初始化项)。
边界与反例。 本课优化的是匹配数量,不考虑边权:如果不同配对有不同收益,最大权匹配是另一个问题;若允许一人做多个任务,需要容量大于1,成为 b-匹配或流容量扩展;若边可连接同侧顶点,就不再是二分图,不能直接用这套分层归约。还要区分最大匹配与极大匹配:前面的大小2匹配已经极大,但不是最大。
八、总结与下一课(约1分钟)
[ \boxed{\text{二分图配对}\longrightarrow\text{单位容量最大流} \longrightarrow\text{反向残量弧/交替增广路} \longrightarrow\text{整数最优匹配}.} ]
下一课(2026-11-21,第33课):Hopcroft–Karp。 重点不是再写一遍 BFS,而是证明:为什么“一批最短增广路”能使阶段数减少,并获得 (O(m\sqrt{p+q})) 的复杂度。
九、四级自测(满分100;首次不公布答案)
前3题客观判分,最后一题开放证明。只给中立提示,答案和解析放在独立测验 JSON 中。
Lv1|反向残量弧的意义|15分|预计2分钟|单选
题目: 在二分图匹配对应的单位容量流网络中,为什么残量网络中的反向弧是必要的?哪项说法正确?
A. 反向弧能使某个左侧顶点最终匹配两个右侧顶点。
B. 反向弧允许撤销此前占用的匹配边,使流量重新安排到另一组合法配对。
C. 反向弧意味着原二分图新增了一条反方向的可匹配边。
D. 只要初次选择的是一条合法匹配边,以后就不可能需要撤销它。
中立提示:对照 B→1→A→2→C→3 的交替路径,想想从右侧顶点走回左侧顶点意味着什么。
Lv2|交替路径翻转 Trace|20分|预计4分钟|单选
题目: 二分图左侧为 A、B、C,右侧为 1、2、3,边集为 {A–1,A–2,B–1,C–2,C–3}。初始匹配 M={A–1,C–2}。沿交替增广路 B→1→A→2→C→3 翻转边后,新匹配是哪一组?
A. {A–1,C–2}
B. {B–1,A–2,C–3}
C. {A–1,B–1,C–3}
D. {B–1,A–2,C–2}
中立提示:把路径上原来匹配的边删去,原来未匹配的边加入;检查所有顶点是否仍只出现一次。
Lv3|整数性、最优性与边界|25分|预计4分钟|多选
题目: 对标准二分图单位容量流归约及交替增广路,下列哪些论断成立?(多选)
A. 由于每条容量都是整数,任意实数可行流必然自动逐边取整数。
B. 从零流开始按残量瓶颈增广,能保持流量为整数;最终最大流值等于最大匹配的边数。
C. 如果当前匹配还不是最大匹配,一定存在以两个未匹配顶点为端点、匹配边与未匹配边交替的增广路。
D. 只要找到任意一条匹配边与非匹配边交替的路径,即使端点已匹配,翻转它也必然使匹配数增加一。
中立提示:区分整数容量与任意可行流的区别;再区分一般交替路径和端点必须空闲的增广路径。
Lv4|最大流归约与 Berge 引理证明|40分|预计11分钟|开放推导
| 题目: 给定二分图 G=(L∪R,E),p= | L | 、q= | R | 、m= | E | 。(a)(10分)构造从 s 到 t 的单位容量网络,证明任意匹配能变成同值的可行整数流。(b)(12分)证明任意整数可行流能还原为同值的匹配,并解释为什么从零流出发的残量增广始终保持整数性,从而最大流值等于最大匹配数。(c)(12分)定义交替路与增广路,证明沿增广路翻转保持匹配合法且规模增加 1;进一步使用最大匹配 M* 与当前匹配 M 的对称差证明:没有增广路时 M 就是最大匹配。(d)(6分)分析一次 BFS 搜索一条增广路、逐次增广的时间和空间上界,说明为何一般带权匹配或非二分图匹配不能直接等同于这一归约。 |
中立提示:按 s→左点→右点→t 逐层构造;把整数流的左右度限制转成匹配限制;对称差的各连通分量只有交替路径或环,比较两种颜色的边数。
十、作答与反馈
回复 Lv1选项;Lv2选项及翻转过程;Lv3所有正确选项;Lv4(a)–(d)证明。我将按15/20/25/40分逐题批改:80–100分继续 Hopcroft–Karp;60–79分补残量/交替路径练习;低于60分先复习整数流对应和对称差证明。补练不修改原定课号。