5.1 二分图的最大匹配 
图的匹配问题有其丰富的实际背景，它涉及了二分图与一般图的最大匹配，二分图与 
一般图的最佳匹配等，除了一般图的最佳匹配之外，本章都将一一进行讨论。 
例 5.1.1 m 项工作准备分配给 n 个人去做，如图 5.1 所示，其中边 (xi，yj) 表示 
xi 可以从事 yj，如果每个人最多从事其中一项，且每项工作只能由一人承担。问怎样才能 
给尽可能多的人安排上任务。 
图 5.1 是二分图，按照要求，如果 xi 从事了 yj，就不允许再从事 yk，同时 yj 也不再 
允许其他人承担。因此，它相当于用一种颜色，例如红色对 G 的边进行着色，保证每个顶 
点最多只与一条红色边关联。这种红色边的集合记为 M，它就称为匹配。原问题就是计算 
G 中包含边数最多的一个匹配 M。 
例 5.1.2 第二次世界大战期间，盟军许多飞行人员到英国参加对法西斯德国的空袭 
行动，当时每架飞机需要领航员和飞行员各 1 人。其中有些人只能领航，一些人只会驾驶， 
也有人两者均会。加之二人语言要求相通，因此如果以顶点表示人，边表示两者语言相通 
并且一人可领航另一人可驾驶，就会得到如图 5.2 所示的一个简单图 G。那么最多的编队 
方案就是计算 G 中的一个最大匹配。 
图 5.1 图 5.2 
定义 5.1.1 令 M 是图 G 的边子集，若 M 中任意两条边都没有共同的顶点，则称 
M 是 G 的一个匹配，其中与 M 的边关联的顶点称为饱和点，否则称为非饱和点。 
定义 5.1.2 设 M 是 G = (V ，E) 中的一个匹配，如果对 G 的任意匹配 M′，都有 
|M| . |M′ |，就说 M 是 G 的一个最大匹配。
图论与代数结构 (第 2 版) 
R启发与思考 
如果给出二分图以及一个匹配，如何确定它是不是最大匹配？如果不是，怎么在 
这个匹配的基础上找到一个更大的匹配？为了解决这些问题，需要相关定义。 
定义 5.1.3 给定了 G 的一个匹配 M，G 中属于 M 与不属于 M 的边交替出现的 
道路称为交互道路。构成回路的交互道路称为交互回路。 
有时这种交互道路可能构成交互回路。 
定义 5.1.4 设 P 是 G 中关于匹配 M 的一条交互道路，如果 P 的两个端点是关于 
M 的非饱和点，那么它就称为可增广道路。 
可增广道路 P 一定包含奇数条边，且其中不属于匹配 M 的边比 M 中的边多一条。同 
时 P ⊕M 仍然是 G 的一个匹配 M′，它使 P 的两个端点变成饱和点，这时 |M′| = |M|+ 1， 
即 M′ 是比 M 更大的匹配。 
定理 5.1.1 M 是 G 的最大匹配当且仅当 G 中不存在关于 M 的可增广道路。 
证明：必要性。若存在 M 的可增广道路 P，则 M ⊕P = M′ 是 G 的一个新匹配，且 
|M′| > |M|，与 M 是最大匹配矛盾。充分性。如果匹配 M 不是 G 的最大匹配，则存在 
一个最大匹配 M′，做 G′ = M′ ⊕M，我们逐一分析 G′ 中 3 种可能的连通支。 
(1) 孤立顶点，当 (vi，vj) ∈ M′ ∩M 时会出现孤立点 vi 和 vj。 
(2) 初级回路，该回路中属于 M′ 和属于 M 的边数相同。 
(3) 初级道路，如果不存在增广道路，那么 |M′| = |M|，与假设矛盾。如果存在 M 关 
于 M′ 的增广路，又与 M′ 是最大匹配矛盾。由于 |M′| > |M|，故必定存在 M′ 关于 M 
的可增广交互道路，即 G 中存在关于 M 的可增广道路。 
定理 5.1.1 是二分图和一般图最大匹配算法的依据。不过由于二分图的所有回路都是 
偶回路的特点，因此它的最大匹配算法较为简单。 
计算二分图最大匹配的一个好算法是匈牙利算法。描述如下。 
匈牙利算法 
（输入为二分图 G = (X，Y ，E)；顶点标记 0 表示尚未搜索，顶点标记 1 表示是饱和 
点，顶点标记 2 表示是无法扩大匹配的顶点）。 
1. 任给一初始匹配 M，给饱和点标记“1”。 
2. 判 X 中的各顶点是否都已有非零标记。 
2.1 是。M 是最大匹配，结束。 
2.2 否。找一 0 标记点 x0 ∈ X， 
令 U ← {x0} ，V ← .。 
3. 判集合 U 的邻接点集 Γ(U) = V ? 
3.1 是，x0 无法扩大匹配，给 x0 标记“2”，转 2。 
3.2 否，在 Γ(U) . V 中找一点 yi，判 yi 是否标“1”。 
· 108 ·
第 5 章 匹配 
3.2.1 是，则有边 (yi，z) ∈ M。令 
U ← U ∪ {z}，V ← V ∪ {yi}，转 3。 
3.2.2 否，存在从 x0 至 yi 的可增广路 P， 
令 M ← M ⊕ P，给 x0 和 yi 标记“1”，转 2。 
R启发与思考 
我们已经学习过如何在有向图中寻找道路（使用深探法或广探法）。能否采用化归 
的思想，为 G 中的边规定方向，得到一个有向图，使得可增广道路都是其中的道路，从 
而解决最大匹配问题。实际上，按照边是否在匹配 M 中来规定方向，使得交互道路都 
是有向图中的道路即可。以此思路，可以尝试以广探法的思想理解上述的匈牙利算法 
中的步骤 3。 
例 5.1.3 图 5.3 中，设初始匹配 M = {(x1，y1) ， (x3，y4) ， (x4，y5)}。用匈牙利 
算法求其最大匹配的过程如下。 
(1) U = {x2} ，V = .。 
Γ(U) = {y4，y6} ，y6 ∈ Γ(U) . V ， 且无标记。 
所以 增广路P = (x2，y6)。 
M = {(x1，y1) ， (x3，y4) ， (x4，y5) ， (x2，y6)}。 
(2) U = {x5} ，V = .。 
Γ(U) = {y5，y6} ，y5 ∈ Γ(U) . V 。 
U = {x5，x4} ，V = {y5}。 
Γ(U) = {y5，y6} ，y6 ∈ Γ(U) . V 。 
U = {x5，x4，x2} ，V = {y5，y6}。 
Γ(U) = {y5，y6，y4} ，y4 ∈ Γ(U) . V 。 
U = {x5，x4，x2，x3} ，V = {y5，y6，y4}。 
Γ(U) = {y5，y6，y4，y2} ，y2 ∈ Γ(U) . V 且无标记。 
所以 有增广路P = (x5，y6，x2，y4，x3，y2)。 
M = {(x1，y1) ， (x4，y5) ， (x5，y6) ， (x2，y4) ， (x2，y3)}。 
(3) U = {x6} ，V = .。 
Γ(U) = {y6} ，y6 ∈ Γ(U) . V 。 
U = {x6，x5} ，V = {y6}。 
Γ(U) = {y6，y5} ，y5 ∈ Γ(U) . V 。 
U = {x6，x5，x4} ，V = {y6，y5}。 
Γ(U) = {y6，y5} ，Γ(U) = V 。 给x6 标记2。结束。 
· 109 ·
图论与代数结构 (第 2 版) 
图 5.3 
因此，其最大匹配是 M = {(x1，y1) ， (x4，y5) ， (x5，y6) ， (x2，y4) ， (x3，y2)}。 
定理 5.1.2 最大匹配匈牙利算法的计算复杂性是 O(mn)，其中二分图 G(X，Y ，E) 
中，n = |X|，m = |E|。 
证明：初始匹配可以是空匹配，算法最多找 n 条增广路，每找一条增广路时，最多判 
断 m 条边，因此其计算复杂性是 O(mn)。 
5.2 完 全 匹 配 
图 5.4 
二分图 G = (X，Y ，E) 的最大匹配 M 包含 
的边数不会超过 |X|，若 |M| = |X|，则称 M 是完 
全匹配。特别地，如果 |M| = |X| = |Y |，则称 M 
是完美匹配。直观地看，如果每个顶点 x 关联的边 
愈多，则最大匹配的边数可能愈大。例如图 5.4(a) 
有完全匹配，而图 5.4(b) 没有完全匹配。那么满足 
什么条件 G 中就会有完全匹配呢? 霍尔 (Hall) 定 
理给出了判别的标准。 
图 5.5 
定理 5.2.1 在二分图 G=(X，Y ，E) 中，X 
到 Y 存在完全匹配的充要条件是对于 X 的任意子集 
A，恒有 
|Γ(A)| . |A | 
证明：必要性。若存在子集 A . X，使 
|A| > |Γ(A) |，则 A 中的顶点无法全部匹 
配。因此，X 到 Y 不可能有完全匹配。充分性。 
假定 G 的一个最大匹配 M 不是完全匹配，一 
定存在顶点 x0 ∈ X 是关于 M 的非饱和点。 
如果 Γ (x0) = Φ，则令 A = {x0}，于是 
|Γ(A)| < |A|，不满足条件。如果 Γ (x0) .= Φ，如 
图 5.5 所示，对某一个 yj ∈ Γ (x0)，若 yj 关于M 为非饱 
· 110 ·
第 5 章 匹配 
和点，则存在增广路 (x0，yj)，与 M 是最大匹配矛盾。因此，yj ∈ Γ (x0) 都是关于 M 的 
饱和点。这样可以寻找以 x0 为端点的相对于 M 的一切交互道路，记交互道中顶点 yj 的 
集合为 Y1，结点 xi 的集合为 X1，根据匹配的性质 Y1 的顶点与 X1 . x0 的顶点之间存在 
一一对应，于是 |X1| > |Y1|，即 |X1| > |Γ (X1)|。 
推论 5.2.1 若二分图 G = (X，Y ，E) 的每个顶点 xi ∈ X，都有 d (xi) . k，每个 
顶点 yi ∈ Y ，都有 d (yj) . k，那么 X 到 Y 存在完全匹配。 
证明：对任意子集 A . X，设它的顶点总共与 m 条边关联，于是有 m . k|A|，这 
m 条边又与 Y 中的 |Γ(A)| 个顶点相关联，又有 m . k|Γ(A)|，因此 |Γ(A)| . |A|，由定 
理 5.2.1 即得。 
例 5.2.1 在一个舞会上男女各占一半，假定每位男士都认识 k 位女士，每位女士也 
认识 k 位男士。那么一定可以安排得当，使每位都有认识的人作为舞伴。 
证明：用顶点 xi 表示每位男士，yj 表示每位女士，互相认识者用边连接。于是得到二 
分图 G = (X，Y ，E)，图中每个顶点 xi 有 d (xi) = k，yj 有 d (yj) = k。满足 d (xi) . k， 
d (yj) . k，由推论 5.2.1，X 到 Y 有完美匹配 M。M 就是一种安排方案。 
二分图的完全匹配一定是最大匹配，而最大匹配不一定就是完全匹配，那么它们之间 
有什么内在联系呢? 
定理 5.2.2 在二分图 G = (X，Y ，E) 中，X 到 Y 最大匹配的边数是 |X|.δ(G)， 
其中 δ(G) = max 
A.x 
δ(A)，δ(A) = |A| . |Γ(A)|，δ(A) . 0。 
证明略。 
例 5.2.2 10 个人有 10 件不同的乐器，其中 3 人只会拉小提琴，其余 7 人每件乐器 
都会，若每人只用一件乐器，则由定理 5.2.2，最多只有 8 人能同时登台演出。 
二分图是一个图，当然可以用邻接矩阵表示。由于其全部的边都跨越在 X 和 Y 之 
间，因此，可以将邻接矩阵进行简化，成为 |X| × |Y | 的一个矩阵。例如图 5.6 的邻接矩 
阵是 
A = 
............ 
0 0 0 1 0 
0 1 0 0 0 
0 1 0 0 0 
1 1 0 0 1 
0 0 0 1 0 
0 0 1 0 1
............ 
这样 G 中的最大匹配数 r 就是 A 中不在同行同列非零元的最多个数。如果矩阵 A 是 
p × q 的，显然有 r . min(p，q)。 
另外，也可以适当地选取 A 的某些行和列，使这些行和列能盖住 A 中的全部非零元， 
这称为 A 的覆盖，当然如果盖住 A 的全部 p 行，或全部 q 列，就一定会盖住所有非零元， 
· 111 ·
图论与代数结构 (第 2 版) 
但这不一定是最少选取的行与列，例如图 5.6 的矩阵 A，如果盖住其第 4、6 行，第 2、4 
列，就可以覆盖其全部非零元。因此，在矩阵 A 的全部覆盖中，一定存在最小覆盖，其覆 
盖数为 s，显然 s . min(p，q)。 
定理 5.2.3 设 r 是二分图 G 的最大匹配数，s 是其邻接矩阵的最小覆盖数，则有 
r = s。 
证明：因为每个不在同行同列的非零元需要一行或一列才能盖住，所以 r 个不在同行 
同列的非零元需要 r 行、列才能盖住，而 s 个不同的行、列盖住了矩阵 A 的全部非零元， 
自然也盖住了 r 个不在同行同列的非零元。因此 s . r。再证 r . s。不失一般性，设最 
小覆盖盖住了 A 的 c 行、d 列，即 s = c + d。设这 c 行对应的顶点子集是 Xc，其余 
为 X . Xc ；d 列对应的顶点集是 Yd，其余为 Y . Yd。把矩阵 A 的行、列进行调整，如 
图 5.7 所示，显然 A11 每行都被覆盖，A22 每列都被覆盖，A12 中每个元素既被行也被列 
所覆盖，而 A21 = 0。 
图 5.6 图 5.7 
现证明 Xc 到 Y . Yd 存在完全匹配。在 A11 中任取 |V ′| 行，这些行中的非零元至少 
分布在它的 |V ′| 个不同列上。否则，不覆盖这 |V ′| 行，而覆盖这些更少的列，A 中的所有 
非零元仍然全部覆盖，这时所用的覆盖数比原先要少，与原来是最小覆盖矛盾。这就是说， 
对 Xc 的任意子集 V ′，它在 Y . Yd 中的邻接点集是 Γ (V ′)，总有 |Γ (V ′)| . |V ′|。根据定 
理 5.2.1，Xc 到 Y . Yd 存在完全匹配 M1，|M1| = c。同理，Yd 到 X .Xc 也存在完全匹 
配 M2，|M2| = d，M1 ∪M2 仍然是 G 的一个匹配，|M1 ∪M2| = c + d = s。因此，G 的 
最大匹配数 r . s。 
定理 5.2.3 不但揭示了匹配与覆盖之间的关系，而且也是最佳匹配算法的基本依据 
之一。 
5.3 最佳匹配及其算法 
5.1 节和 5.2 节讨论的都是边权为 1 的匹配问题，如果边权是非负实数，而且存在多 
个完全匹配，那么其中权和最大或最小的完全匹配就叫作最佳匹配。 
· 112 ·
第 5 章 匹配 
例 5.3.1 5 项工作由 5 个人完成，如下所示。 
C =
........ 
3 4 6 4 9 
6 4 5 3 8 
7 5 3 4 2 
6 3 2 2 5 
8 4 5 4 7
........
其中 cij 表示 i 从事工作 j 的利润，如果每个人只做一项工作，那么最大的利润就应该是 
maxΣcij，cij 不在相同的行与列。 
假如 cij 表示 i 从事工作 j 的成本，那么最小的成本应该是 minΣcij，cij 不在相同的 
行与列。 
R启发与思考 
实际问题中的情况一般更为复杂，如工作数与人数可能不等，允许一部分工作不 
被完成，有的人可能做不了某些工作，或是做某些工作的利润为负（即导致亏损）。该 
例题实际上已将问题充分简化，使得工作数与人数相等，利润均存在且非负。这样一 
来，便能找到一个较为简单的算法解决该问题，而将较为复杂的情况化归为该算法能 
解决的情况也是简单的，如添加一些虚拟的点和边来解决两边点数不同的问题，给所 
有边权加上一个固定值解决有负权边的问题等。 
显然这种最佳匹配就是二分图的最大权或最小权匹配。在讨论最佳匹配时，二分图 G = 
(X，Y ，E) 满足条件 |X| = |Y |。 
我们先介绍一个利用最小覆盖取代最大匹配的最大权匹配算法。 
最大权匹配算法（已知利润矩阵 C）。 
1. 在矩阵 C 的每行选一最大值作为本行的界值 l (xi)，每列的界值 l (yj) = 0。构造 
矩阵 B = (bij)n×n
，其中 bij = l (xi) + l (yj) . cij。 
2. 在 B 中对 0 元素进行最小覆盖，覆盖数为 r。 
2.1 若 r = n，转 4。 
2.2 在未覆盖的元素中选最小非零元，设值为 δ。 
若 xi 行、yj 列均已覆盖，则 bij ← bij + δ。 
若 xi 行、yj 列均未覆盖，则 bij ← bij . δ。 
3. 修改界值 
若 xi 行没覆盖，令 l (xi) ← l (xi) . δ； 
若 yj 列已覆盖，令 l (yj) ← l (yj) + δ。 
删除覆盖标记，转 2。 
4. Σ(l(xi) + l(yj)) 即是最大权，结束。 
例 5.3.2 求例 5.3.1 表中的最大利润。 
· 113 ·
图论与代数结构 (第 2 版) 
解：首先得到矩阵 B，界值已在表的两旁标出，最小覆盖是 1、5 两列，δ = 2。 
↓ ↓ ....... 
....... 
9 6 5 3 5 0 
8 2 4 3 5 0 
7 0 2 4 3 5 
6 0 3 4 4 1 
8 0 4 3 4 1 
0 0 0 0 0 
r < n，B 中没覆盖的元素均减 δ；修改界值，结果如下。这时一个最小覆盖是第 1、5 
列，第 3 行。δ = 1。 
↓ ↓ ....... 
....... 
7 6 3 1 3 0 
6 2 2 1 3 0 
5 0 0 2 1 5 
4 0 1 2 2 1 
6 0 2 1 2 1 
2 0 0 0 2 
r < n，B 中没覆盖元素减 1，双重覆盖元加 1。修改界值，这时一个最小覆盖是第 1、 
2、3、5 列。δ = 1。 
↓ ↓ ↓ ↓ ....... 
....... 
6 6 2 0 2 0 
5 2 1 0 2 0 
5 1 0 2 1 6 
3 0 0 1 1 1 
5 0 1 0 1 1 
3 0 0 0 3 
r < n，B 中没覆盖元素减 1，修改界值，这时一个最小覆盖是第 3、4、5 行，第 3、5 列，最 
小覆盖数 r = n。一个最大权匹配方案是 {c13，c25，c34，c42，c51}，Σ(l(xi)+l(yi)) = 29。 
结束。 
↓ ↓ ........ 
........ 
5 6 2 0 1 0 
4 2 1 0 1 0 
4 1 0 2 0 6 ← 
2 0 0 1 0 1 ← 
4 0 1 0 0 1 ← 
4 1 1 0 4 
· 114 ·
第 5 章 匹配 
定理 5.3.1 算法的结果是矩阵 C 的最大权匹配。 
证明：所选取的矩阵 B 满足
bij = l (xi) + l (yj) . cij . 0 (5-1) 
设 W 是 C 的最大权匹配权和，一定有 
Σ(l (xi) + l (yj)) . maxΣcij = W (5-2) 
如果等式成立，那么一定存在 n 个不在同行同列的 cij，满足 cij = l(xi)+l(yj)，或者说 B 
中有 n 个不在同行同列的 0 元素，处于这 n 个位置的 cij 构成了最大权匹配。如果最多存 
在 k(< n) 个这样的 0 元素，式 (5-2) 就不可能相等，设此时的最小覆盖盖住了 c 行 d 列， 
其对应的顶点集为 Xc 和 Yd，由定理 5.2.3，k = c + d < n。令 B 中没被覆盖的最小元是 
δ(> 0)，按照算法在修改界值时，对没覆盖的各行，令 l.(xi) = l(xi) . δ；对覆盖的各列， 
令 l. (yj) = l (Yj) + δ，其余界值不变。为了保证式 (5-1) 不变，即修改界值后仍需满足 
b.ij = l. (xi) + l. (yj) . cij . 0 
就应该对 bij 的不同位置分别进行如下处理。 
(1) 在覆盖的行和列的交叉点位置， 
b.ij = l. (xi) + l. (yj) . cij = l (xi) + l (yj) + δ . cij = bij + δ 
(2) 没被覆盖，b.ij = l (xi) . δ + l (yj) . cij = bij . δ。 
(3) 只被行覆盖，b.ij = l (xi) + l (yj) . cij = bij。 
(4) 只被列覆盖，b.ij = l (xi) . δ + l (yj) + δ . cij = bij。 
在上述每种情况下，b.ij . 0 成立。综上，在对界值和元素 bij 修改之后，式 (5-1) 和 
式 (5-2) 继续保持成立。但新的界值之和 
Σ(l. (xi) + l. (yj)) =Σ(l (xi) + l (yj)) . δ(n . c) + δd 
而 
.δ(n . c) + δd = δ(c + d . n) < 0 
即界值之和下降。由于 δ 选值最小，因此它是最小下降。界值以及 bij 调整后，B 中出现 
了新的 0 元素，将可能增加最小覆盖数。经过若干次迭代之后，界值之和将恰好等于最大 
权匹配值。 
如果矩阵 C 表示成本矩阵，那么它的最小权匹配或最小成本也就容易计算了。一种 
方法是确定一个 n 阶矩阵 Q = (qij)，其中 qij 是一个大于或等于 max cij 的常数 a，令 
C′ = Q. C，则 c′ij + cij = a。这样矩阵 C 的最小成本对应了 C′ 的最大利润。对 C′ 调 
用最大权匹配算法就容易计算 C 的最小成本。另一种方法类似于最大权匹配算法的思路。 
首先选每行的最小元为界值，满足 bij = cij .l (xi).l (yj) . 0。然后不断最小地增加界值， 
直至存在 n 个不在同行同列值为 0 的 bij 出现。 
· 115 ·
图论与代数结构 (第 2 版) 
例 5.3.3 求 C 的最小成本。 
C =
......... 
7 6 4 6 1 
4 6 5 7 2 
3 5 7 6 8 
4 7 8 8 5 
2 6 5 6 3
......... 
解：选用 a = 10，得到矩阵 C′ = (c′ij)，c′ij = 10 . cij。C′ 恰是例 5.3.2 计算的矩阵， 
因此 C 的最小成本是 
5 × 10 . maxΣc′ij = 21 
相应的一个最小权匹配方案是 {c13，c25，c34，c42，c51}。 
如果直接对 C 进行计算，过程可以如下。 
首先得到矩阵 B，界值已标出，满足 bij = cij .l (xi).l (yj)，最小覆盖是第 1、5 列， 
δ = 2。 
↓ ↓ ........ 
........ 
1 6 5 3 5 0 
2 2 4 3 5 0 
3 0 2 4 3 5 
4 0 3 4 4 1 
2 0 4 3 4 1 
0 0 0 0 0 
r < n。B 中没覆盖的元素均减 δ，行、列都覆盖的加 δ，修改界值。没覆盖的行界值 
加 δ，覆盖的列界值减 δ。这时一个最小覆盖是第 1、5 列，第 3 行，δ = 1。 
↓ ↓ ........ ........ 
3 6 3 1 3 0 
4 2 2 1 3 0 
5 0 0 2 1 5 ← 
6 0 1 2 2 1 
4 0 2 1 2 1 
.2 0 0 0 .2 
r < n。B 中没覆盖的元素均减 δ，修改界值如下，这时一个最小覆盖是第 1、2、3、5 
列，δ = 1。 
· 116 ·