二分图最大匹配

Views: --

二分图 G=(L∪R,E)G=(L\cup R,E) 的顶点分成互不相交的左右两部分，每条边都连接一左一右。匹配 M⊆EM\subseteq E 要求每个顶点至多关联一条匹配边；最大匹配要让边数 ∣M∣|M| 尽可能大。

1. 为什么直接挑空闲边会失败

某个左点可能有多个候选右点，而另一个左点只有唯一候选。如果先随意占用唯一候选，后者就无法匹配。局部选择需要允许“反悔”和重新安排。

2. 交替路与增广路

相对于当前匹配 MM：

  • 交替路上的边在“非匹配、匹配、非匹配……”之间交替；
  • 增广路是一条以两个未匹配顶点为端点的交替路。

沿增广路翻转边的状态：非匹配边加入 MM，匹配边移出 MM。由于增广路比匹配边多一条，匹配大小恰好增加 1。

3. 最大性判据

Berge 定理：匹配 MM 是最大匹配，当且仅当不存在相对于 MM 的增广路。

一方面，有增广路就能增大匹配；另一方面，若存在更大匹配 M′M'，考察对称差 M△M′M\triangle M'，其中必有一个交替路径分量在 M′M' 中多一条边，于是构成 MM 的增广路。

4. DFS 增广的匈牙利算法

依次尝试让每个左侧顶点找到增广路：

augment(u):
    for each v in Adj[u]:
        if v was tried in this search: continue
        mark v tried
        if matchRight[v] is empty
           or augment(matchRight[v]):
            matchRight[v] = u
            return true
    return false

for each u in L:
    clear tried marks
    if augment(u): answer++

若右点 vv 已匹配，就递归尝试给原来的左点换一个位置；成功后把 vv 让给当前 uu。递归调用正是在寻找交替增广路。

5. 为什么每轮要重置访问标记

tried[v] 只表示“当前这次增广搜索已经尝试过右点 vv”。换一个新的起点后，匹配结构可能已经改变，必须重新搜索。若全程只标一次，会漏掉合法增广路。

6. 复杂度

每个左点至多发起一次 DFS，一次搜索最坏检查 O(E)O(E) 条边，总复杂度常写为

O(∣L∣E)⊆O(VE).O(|L|E)\subseteq O(VE).

更大的图可用 Hopcroft–Karp，在每轮 BFS 中同时寻找一批最短增广路，达到 O(EV)O(E\sqrt V)。

7. 与最大流的关系

建立源点 ss 到每个左点容量 1 的边、原二分边容量 1、每个右点到汇点 tt 容量 1 的边。整数最大流的每个单位流对应一条匹配边，因此最大流值等于最大匹配数。

这也解释了“每个顶点至多匹配一次”如何被容量约束表达。

8. 二分图判定与匹配不是一回事

先用 BFS/DFS 二染色可以判断一般无向图是否二分。只有确认二分后，才能把两个颜色集合当作 LL 与 RR 运行上述算法。

9. 常见扩展

  • 完美匹配：每个顶点都被匹配；
  • 加权匹配：优化总权值，不能用普通 DFS 增广直接解决；
  • 二分图最小点覆盖：由 Kőnig 定理，其大小等于最大匹配大小；
  • 指派问题：通常要求完美匹配并最小化总成本，对应带权匈牙利算法。

课程语境中的“匈牙利算法”有时指 DFS 增广，有时指带权指派算法，答题前要按题目定义确认。

评论