二分匹配

概述

二分匹配（Bipartite Matching）是在二部图中寻找最大的边集，使得任意两条选中的边不共享端点，是组合优化中的经典问题。

定义

形式化定义

给定二部图 $G=(L,R,E)$，一个匹配（matching）$M\subseteq E$ 是一个边集，满足 $M$ 中任意两条边没有公共端点。

• 最大匹配（maximum matching）：边数 $|M|$ 最大的匹配
• 完美匹配（perfect matching）：$|M|=\min (|L|,|R|)$ 的匹配，即覆盖较小部中所有顶点的匹配
• 最大基数匹配（maximum cardinality matching）：即最大匹配
• 最大权匹配（maximum weight matching）：在带权二部图中，使选中边权重之和最大的匹配

核心概念

交替路径与增广路径

• 交替路径（alternating path）：路径上的边交替属于 $M$ 和 $E\setminus M$
• 增广路径（augmenting path）：两端均为未匹配顶点的交替路径。沿增广路径翻转匹配状态，可使匹配边数 $+1$

匹配的关键定理

Berge 定理

匹配 $M$ 是最大匹配，当且仅当 $G$ 中不存在关于 $M$ 的增广路径。

König 定理

在二部图中，最大匹配的边数 = 最小顶点覆盖的顶点数。

Hall 定理

二部图 $G=(L,R,E)$ 存在完美匹配，当且仅当对任意 $S\subseteq L$，$|N(S)|\ge |S|$。

求解算法

方法一：转化为最大流

构造流网络：

1. 添加超级源点 $s$ 和超级汇点 $t$
2. $s$ 向 $L$ 中每个顶点连边，容量为 1
3. $R$ 中每个顶点向 $t$ 连边，容量为 1
4. 原二部图中的每条边方向为 $L\to R$，容量为 1
5. 在该网络上求最大流，流量值即为最大匹配边数

时间复杂度取决于最大流算法（如 Edmonds-Karp 为 $O(V{E}^2)$）。

方法二：Hopcroft-Karp 算法

专为二分匹配设计的算法，核心思想是同时寻找多条最短增广路径：

• 时间复杂度：$O(\sqrt{V}\cdot E)$
• 比直接用最大流更高效
• 分为 BFS（构建分层图）和 DFS（多路增广）两个阶段交替执行

方法三：匈牙利算法

用于求解最大权匹配问题：

• 时间复杂度：$O(V^3)$
• 基于 KM（Kuhn-Munkres）算法，利用势函数和等价子图

应用场景

• 任务分配：工人与任务的匹配，最大化分配数量或总效益
• 课程安排：将课程分配到时间槽，确保不冲突
• 顶点覆盖：利用 König 定理，通过最大匹配构造二部图的最小顶点覆盖
• 稳定婚姻问题：Gale-Shapley 算法求解稳定匹配

参见

• 图论
• 二部图
• 最大流