1
第三章 匹配理论
§3.1 匹配与最大匹配
定义 3.1.1 设 G 是一个图,)(GEM?,满足:对
i
e?,Me
j
∈,
i
e 与
j
e 在 G 中不相邻，则称 M 是 G 的一个匹配。对匹配 M 中每条边 uve =,其两端点 u 和 v 称为被匹配 M 所匹配，
而 u和 v 都称为是 M饱和的(saturated vertex)。
注,每个顶点要么未被 M 饱和,要么仅被 M 中一条边饱和。
定义 3.1.2 设 M 是 G 的一个匹配,若 G 中无匹配 M′,使得 |||| MM >′,则称 M 是 G 的一个最大匹配；如果 G 中每个点都是 M 饱和的,则称 M 是 G 的完美匹配(Perfect matching),
显然,完美匹配必是最大匹配。
例如，在下图 G
1
中，边集 {e
1
},{e
1
,e
2
},{e
1
,e
2
,e
3
}都构成匹配,{e
1
,e
2
,e
3
}是 G
1
的一个最大匹配。在 G
2
中，边集 {e
1
,e
2
,e
3
,e
4
}是一个完美匹配，也是一个最大匹配。
定义 3.1.3 设 M 是 G 的一个匹配,G 的 M交错路是指其边 M 和 MGE \)( 中交替出现的路。 如果 G 的一条 M 交错路 (alternating path)的起点和终点都是 M 非饱和的,则称其为一条 M
可扩展路或 M增广路(augmenting path)。
定理 3.1.1(Berge,1957) 图 G 的匹配 M 是最大匹配的充要条件是 G中不存在 M 可扩展路。
证明,必要性,设 M 是 G 的一个最大匹配。如果 G 中存在一个 M 可扩展路 P,则将 P 上所有不属于 M 的边构成集合 M′。显然 M′也是 G 的一个匹配且比 M 多一条边。这与 M 是最大匹配相矛盾。
充分性,设 G 中不存在 M 可扩展路。若匹配 M 不是最大匹配，则存在另一匹配 M′,使
|||| MM >′,令
][ MMGH ′⊕=,( MMMMMM ′?′=′⊕ ∩∪ 称为对称差)。
则 H 中每个顶点的度非1即2(这是因为一个顶点最多只与 M 的一条边及 M′的一条边相关联)。故 H 的每个连通分支要么是 M 的边与 M′的边交替出现的一个偶长度圈，要么是 M 的边与 M′的边交替出现的一条路。 由于 |||| MM >′,H 的边中 M′的边多于 M 的边,故必有 H
的某个连通分支是一条路，且始于 M′的边又终止于 M′的边。这条路是一条 M 可扩展路。这与条件矛盾。 证毕。
G
1
G
2
e
1
e
2
e
3
e
2
e
1
e
3
e
4
2
§3.2 完美匹配
定义 3.2.1 图 G 的奇分支,G 的含有奇数个顶点的连通分支。 用 )(GO 表示 G 的奇分支的个数。
定理 3.2.1 (Tutte,1947) 图 G 有完美匹配的充分必要条件是对 )(GVS,||)\( SSGO ≤ 。
证明 （ Lovász,1973） 必要性,设图 G 有完美匹配 M。对 )(GVS,若 SG \ 无奇分支，则
0)\( =SGO ；否则，设
k
GGG,,,
21
null 是 SG \ 的所有奇分支。注意每个
i
G 中至少有一个顶点
i
u 在 M 下与 S 中的某个顶点
i
v 配对（ ki,,2,1 null= ）,（因
i
G 是奇分支,M 是完美匹配） 。
故 SvvvkSGO
k
≤== |},,,{|)\(
21
null 。
充分性 （反证法）,设 G 满足：对 )(GVS,SSGO ≤)\(,但 G 没有完美匹配。首先，
取 φ=S,知 0)( =GO,故 )(GV 是偶数。现在，给 G 添加边以获得一个没有完美匹配而有尽可能多的边的图
*
G 。因 G 是
*
G 的生成子图，故对 )(GVS,SG \ 是 SG \
*
的生成子图，
从而
SSGOSGO ≤≤ )\()\(
*
,（ *）
令 }1)(),({
*
*
=∈= νudGVuuU
G
,
若 )(
*
GVU =,则
*
G 是偶数阶完全图，有完美匹配。这与
*
G 的性质矛盾。因此，
)(
*
GVU ≠,可以证明，此时 UG \
*
的每个连通分支都是完全图（记为命题Ａ，另证） 。
由（ *）式,UUGO ≤)\(
*
，即 UG?
*
的奇分支个数最多是 U 。但这样一来，
*
G 就有一个完美匹配,
UG \
*
的各奇分支中的一个顶点和 U 的一个顶点配对； U 中余下的顶点以及 UG \
*
的各分支中余下的顶点在本分支内配对（由于各分支及 U 都是完全图） 。
…
u
1
u
2
u
k …
S
…
v
2
v
k
v
1
…
G
1
G
2
G
k
奇分支 偶分支
…
…
U
G
*
\U 的奇分支 G
*
\U 的偶分支
…
3
这与
*
G 无完美匹配矛盾。证毕,
命题Ａ的证明,在上述充分性证明的条件下，当 )(
*
GVU ≠ 时,UG \
*
的每个连通分支都是完全图。
用反证法证明：若不然，设 UG \
*
中某个连通分支
i
G 不是完全图，则 3)( ≥
i
GV 。必存在
)(,,
i
GVzyx ∈,使得 )(,
i
GEyzxy ∈,且 )(
i
GExz? 。由于 Uy?,故必有与 y 不相邻的顶点，即必存在 ),\(
*
UGVw∈ 使得 )(
*
GEyw? 。
由于
*
G 是不含完美匹配的极大图，所以 xzG +
*
和 ywG +
*
都含有完美匹配，分别设为
1
M 和
2
M 。用 H 表示 { }ywxzG,
*
∪ 中由
21
MM ⊕ 导出的子图。由于对 )(HVu∈?,2)( =ud
H
或
0（由
1
M 和
2
M 都是完美匹配知）,故 H 的每个非平凡连通分支都是其边在
1
M 和
2
M 中交替出现的偶长度圈。下分两种情形,
(1) xz 和 yw分别在 H 的不同分支中。设 yw在 H 的某个圈 C 上，则
1
M 在 C 上的边连同
2
M 不在 C 上的边构成
*
G 的一个完美匹配。这与
*
G 的选择矛盾。
情形（ 1） 情形（ 2）
(2) xz 和 yw在 H 的同一分支Ｃ中,由 x 和 z 的对称性,不妨设 zwyx,,,在 C 中依次出现，
并设
1
M 在 C 的 zywnull 段中的边集为
1
M′，
2
M 在 C 的 zywnull 段中的边集为
2
M′，于是
)\(}{
221
MMyzM ′′ ∪∪
是
*
G 的完美匹配，又与
*
G 的选择矛盾。
综合 (1),(2)两种情形，便证明了 UG \
*
的每个连通分支都是完全图。证毕。
推论 3.2.1 ( 1?k )边连通偶数阶 k 正则图有完美匹配
证明：设 G 是命题中所述的 k 正则图。
当 1=k 时，结论显然。
以下假定 2≥k 。设 S 是 G 的任一个非空顶点集，
n
GGG,,,
21
null 是 SG \ 的奇分支。令
),(
ii
GV=ν eem
i
|{|= 是
i
G 与 S 之间的连边 |} 。
w
z
y
x
C
M
1
的边
M
2
的边
w
y
x z
C
…
U
G
i
x
wy
z
4
由于 1?≥′ kκ,故 1?≥ km
i
,),,2,1( mi null= 。
若存在 i,使得 1?= km
i
，则因
i
GVv
G
kvd
i
ν=
∑
∈ )(
)(,Skvd
Sv
G
=
∑
∈
)(,（ *）
从而 )(2)()(
)()(
ii
GVv
G
GVv
Gi
Gkvdvdm
i
i
i
εν?=?=
∑∑
∈∈
。因此,
1)1()1()(2 +?==?=
iiiii
kkkmkG νννε 。
但因 1?
i
ν 是偶数（每个
i
G 是奇分支）,上式两端不可能相等。这个矛盾说明 km
i
≥
（ ),,2,1 ni null=,于是
knm
n
i
i
≥
∑
=1
,（**）
故有 Sud
k
m
k
nSGO
Su
G
n
i
i
=
∑∑
≤
∈=
≤?=?
(*)1(**)
)(
11
)(
由 Tutte 定理,G 有完美匹配。证毕。
推论 3.2.2 (Peterson,1891) 2边连通（无割边）的 3 正则图有完美匹配。
证明：设 G 是 2 边连通的 3 正则图。因 νε 3)(2
)(
==
∑
∈ GVv
vd,故 ν 为偶数。由推论 3.2.1,G 有完美匹配。 证毕
注,有割边的 3 正则图未必有完美匹配，例如，对如下所示的图 G，因 ()3OG v?=，故无完美匹配。
推论 3.2.3 偶数阶完全图
n
K
2
有 12?n 个边不重的完美匹配。
…
…
G
1
G
2
G
n
S
G\S 的奇分支 G\S 的偶分支
G
v
5
证明：用平面上正 12?n 边形的点代表
1221
,,,
n
vvv null,而用其中心点代表
n
v
2
点。用直线段连接每个顶点对,即得
n
K
2
。 构作匹配
i
M 为边
ni
vv
2
和所有与
ni
vv
2
垂直的边之集。 易检验每个
i
M
都是 G 的完美匹配，且不同的
i
M 无公共边。例如，按这种方法构作出 K
6
的两个完美匹配如下图 (b),(c)所示。显然，
n
v
2
关联的每条边对应这样一个完美匹配，故共有 12?n 个边不重的完美匹配。证毕。
§3.3 二部图的匹配
定理 3.3.1 (Hall,1935) 设 G 是具有二划分 ),( YX 的二部图，则 G 有饱和 X 的匹配当且仅当对 XS,SSN ≥)(,其中 )(SN 表示 S 的所有邻点之集。
证明：必要性。设 G 有饱和 X 的匹配 M,则对 XS,因 S 的顶点在 M 下和 )(SN 中顶点配对，故 SSN ≥)( 。
充分性：设 ),( YXG = 是二部图，且对 XS,SSN ≥)( 。下用反证法。
假如 G 没有饱和 X 的匹配，则 G 的最大匹配
*
M 不能饱和 X 的所有顶点。设 u 是 X 的一个
*
M 不饱和点，并设
|{vA = u 到 v 有
*
M 交错路 }。
由于
*
M 是最大匹配，故由 Berge 定理,u 是 A 中唯一的
*
M 非饱和点。令
XAS ∩=,YAT ∩= 。
注意 }{uS? 中的顶点在
*
M 下与 T 中的顶点一一配对（因 Su∈,且对 Tt ∈?,u 与 t 有
*
M
交错路
t
P 相连，而且 t 是
*
M 饱和的，故交错路
t
P 上最后一条边必是
*
M 的边，它将 S 中一个顶点与 t 配对。而且不同的 t 会有 S 中不同的顶点相配，否则会有两条
*
M 的边关联到 S 中同一顶点） 。因此
1?= ST 。 (1)
X
Y
S
T
u
M
*
的边
v
6
v
1
v
3
v
2 v5
v
4
v
6
v
1
v
3
v
2
v
5
v
4
v
6
v
1
v
3
v
2
v
5
v
4
(a)
(c)
(b)
6
此外,TSN?)( （因 T 中顶点通过 S 中顶点与 u 连
*
M 交错路）,且 TSN?)( （对 )(SN
中每个顶点 t,设它是 S 中顶点 s 的邻点,从 u 到 s 的
*
M 交错路必可延伸为 u 到 t 的
*
M 交错路） 。故
TSN =)( (2)
由(1)、(2)知,() | | 1NS T S S==?<，这与定理条件矛盾。证毕。
推论 3.3.1 设 ),( YXG = 是二部图，若 X 中每个顶点至少关联 k 条边（ )1≥k 而 Y 中每个顶点至多关联 k 条边，则 G 中存在饱和 X 的匹配。
证明：由条件知，对 XS,S 至少关联 || Sk 条边。这 || Sk 条边至少关联 Y 中 || S 个顶点。
即 SSN ≥)(,由 Hall 定理,G 有饱和 X 的匹配。证毕。
推论 3.3.2.(Frobenius,1917) 具有二划分 ),( YX 的二部图 G 有完美匹配的充分必要条件是
YX = 且对 XS （或 Y ）,均有 |||)(| SSN ≥ 。
证明：显然。
推论 3.3.3 (K?nig,1916) 设 G 是 k 正则二部图 )0( >k,则 G 有 k 个边不重的完美匹配。
证明,（1）先证 G 有完美匹配。
证法１：设 ),( YXG = 是 k 正则二部图，则 YkGEXk == )(,因 0>k,故 YX =,任取 XS?,令 =
1
E {G 中与 S 关联的边},=
2
E {G 中与 N(S)关联的边}。则
21
EE? 。因而
SkEESNk =≥=
12
)(,即 SSN ≥)( 。由推论 3.3.2,G 有完美匹配。
证法２,由推论 3.3.1,G 中有饱和 X 的匹配。因 YX = （如前所证）,故这个匹配就是完美匹配。
（2）再证 G 中有 k 个边不重的完美匹配（用归纳法） 。
当 1=k 时，显然。
设对所有 k 正则二部图，结论成立。下证对 )1( +k 正则二部图 G,结论也成立。
设 M 是 G 的一个完美匹配。令 MGG \=′ 。则 G′是 k 正则二部图。由归纳假设,G′中有 k 个边不重的完美匹配。故 G 中有 1+k 个边不重的完美匹配。证毕。
下一推论是显然的。
推论 3.3.4 完全二部图
kk
K
,
中存在 k 个边不重的完美匹配。
推论 3.3.5 设 ).( YXG = 是二部图，且 nYX == 。若
2
)(
n
G ≥δ,则 G 有完美匹配。
证明(用反证法)：若 G 没有完美匹配，则由推论 3.3.2，存在 φ≠? SXS,，使 |||)(| SSN < 。
因 G 是二部图且
2
)(
n
G ≥δ,故
2
)(|)(|||
n
GSNS ≥≥> δ,且 φ≠)(\ SNY （因
7
|||)(| SSN < |||| YX =≤ ） 。令 )(\ SNYu∈,则 SXuN \)(?,因此,
22
|||||)(|)()(
nn
nSXuNudG
G
=?<?≤=≤δ 。
这与条件矛盾。故 G 有完美匹配。证毕。
例 3.3.1 下图所示的是 14 个大小相同的正方形组成的图形。试证明：不论如何用剪刀沿着图形中所画的直线对它进行裁剪，总剪不出 7 个由相邻的两个小正方形组成的矩形来。
证明：将图形中方格从 1 到 14 编号。以方格为顶点集作简单图 G = (V,E)，边 )(GEij∈ 当且仅当 i,j 所在的方格在图形中相邻（有公共边） 。
注意 G 中每条边对应于原图形中由相邻两个小正方形组成的矩形，故剪出 7 个矩形相当于在 G 中求由 7 条边组成的匹配。由于有 14 个顶点，故所求的是完美匹配。但这样的匹配是不存在的。事实上,G 是一个二部图，其二划分为
X={1,3,4,6,9,11,12,14},Y={2,5,7,8,10,13}。
|X| = 8 > 6 = |Y|。由推论 3.3.2，不存在完美匹配。
注,G 的 k 正则生成子图称为 G 的 k 因子。若 G 存在无公共边的 k 因子
n
HHH,,,
21
null,
使得
n
HHHG ∪null∪∪
21
=,则称 G 是 可 k－因子分解的 。
推论 3.2.3 证明了完全图
n
K
2
是可 1－因子分解的；推论 3.3.4 证明了完全二部图
nn
K
,
是可
1－因子分解的；推论 3.3.3 证明了每个 k 正则二部图是可 1－因子分解的。
若图 G 有 1 因子，则它显然应是偶数阶图。因此奇数阶完全图 K
2n+1
不可能有 1 因子。
因子分解是图论研究的一个重要选题，进一步的了解可参看
[1] G,Chartrand,and O.R,Ollermann,Applied and Algorithmic Graph Theory,MCGraw-Hill,New
York,1993,
[2] J,Akiyama,M,Kano,Factors and factorizations of graphs — a survey,J,Graph Theory,9(1985),
1-42,
[3] W.D,Wallis,One-factorizations,Kluwer Academic Publishers,Dordrecht,Boston,1997,
[4] Guizhen Liu,and Binhai Zhu,Some problems on factorizations with constraints in bipartite graphs,
128(2003),421-434,
4 6 75
1 32
8 9 1110
12 13 14
4
1
6 7
8
5
32
9 1110
12 13 14
8
§3.4 二部图中最大匹配与最大权匹配的算法
一、求完美匹配的匈牙利算法
1.背景与问题
指派问题 （ assignment problem）,欲安排 n 个人员
n
xxx null,,
21
从事 n 项工作
n
yyy,,,
21
null 。已知每个人能胜任其中一项或几项工作。试问：能否给每个人分配一项他所胜任的工作？若能，
如何求出这种安排？
图论描述,对于一个二部图 G = (X,Y ),X = {
n
xxx null,,
21
},Y＝ {
n
yyy,,,
21
null }，当且仅当
i
x
胜任工作
j
y 时,)(GEyx
ji
∈ 。问,G 中是否有完美匹配？若有，如何求之？
2.理论基础
Berge 定理（定理 3.1.1）,图 G 的匹配 M 是最大匹配的充要条件是 G 中不存在 M 可扩展路。
Hall 定理（定理 3.3.1）,设 G 是具有二划分 ),( YX 的二部图，则 G 有饱和 X 的匹配当且仅当对 XS,SSN ≥)(,其中 )(SN 表示 S 的所有邻点之集。
3.匈牙利算法
匈牙利算法由匈牙利数学家 Egerváry 首先提出，后来由 Edmonds(1965)基于 Berge 定理和
Hall 定理进行了改进 [5]。这种算法既能判定一个二部图中完美匹配是否存在，又能在存在时求出一个完美匹配。
[5] J,Edmonds,Path,tree and flowers,Canad,J,Math,17(1965)449-467,
算法思想,从图 G 的任何匹配 M 开始。
若 M 饱和 X，则 M 是 G 的完美匹配。
若 M 不饱和 X，在 X 中选择一个 M 不饱和点 x。若存在以 x 为起点的 M 增广路 P，则由
Berge 定理知 M 不是最大匹配，且 )(PEMM ⊕=′ 是比 M 更大的匹配。用 M′替代 M 重复上述过程；若 G 中不存在以 x 为起点的 M 增广路，则可找到与 x 由 M 交错路相连的顶点集合 A，
而 XAS ∩= 满足 |||)(| SSN < （见 Hall 定理的证明） 。由 Hall 定理,G 不存在完美匹配。
算法步骤,
step0,任取图 G 的一个匹配 M。
step1,若 M 饱和 X，则停止,M 是 G 的完美匹配。
否则，取 X 中一个 M 不饱和点 x，记 φ==,},{,TxS 。
step2,若 TSN =)(,则停止,G 无完美匹配。 （因 ||1|||||)(| SSTSN <?== ） 。
否则取 TSNy \)(∈ 。
step3,若 y 是 M 饱和的，设 Myz∈,令 }{,zSS ∪=,}{,yTT ∪=,转 step2。 （此时仍保
9
持 )1||||?= ST 。否则，取 M 增广路 ),( yxP,令 )(,PEMM ⊕=,转 step1,
例 3.4.1 判断如下二部图是否存在完美匹配。若存在，求其出一个完美匹配；若不存在，给出满足 TSN =)( 的集合 S 和 T。
解,从一个初始匹配 M＝
22 33 55
{,,}x yxyxy（图 1）出发，执行匈牙利算法。因 M 尚未饱和 X，
找到 X 中一个 M 未饱和点 x
1
。从 x
1
出发，反复执行算法第 2 步和第 3 步，找到一条 M 增广路
x
1
y
2
x
2
y
1
（图 2） 。按第 3 步，沿增广路交换进入匹配和不进入匹配的边，匹配扩大为 M＝
12 21 33 55
{,,,}x yxyxyxy（图 3） 。
图 1：图 G=(X,Y)及一个匹配 M 图 2,M 增广路 x
1
y
2
x
2
y
1
图 3：无完美匹配
因 M 仍未饱和 X，按算法第 1 步，找到 X 中一个 M 未饱和点 x
4
。然后算法令
4
{},SxTφ==，并转入第 2 步试图找一条从 x
4
出发的 M 增广路。因当前
23
() {,}NS y y=,
()NS T≠,从 ()\NS T中任意取出一个，比如 y
3
，转到第三步。因 y
3
是 M 饱和的，其匹配点为 x
3
，按算法第 3 步,S 和 T 更新为
43 3
{,},{}SxxTy= = 。此后，转第 2 步判断是否
TSN =)( 。因当前
23
() {,}NS y y T=≠，故取
2
()\y NS T∈,再次循环执行第 3 步，找到
y
2
的匹配点 x
1
,S 和 T 进一步更新为
431 32
{,,,},{,}SxxxTyy= =,再转第 2 步。此时发现
23
() {,}NS y y T==，因此该图不存在完美匹配。算法找到的满足 TSN =)( 的集合为
431 32
{,,,},{,}SxxxTyy。
匈牙利算法的正确性由 Berge 定理和 Hall 定理可知。
匈牙利算法是多项式时间算法。事实上，设 ||||nXY= = 。算法每找到一条增广路更新一次匹配，匹配边增加一条，故最多需执行 n 次增广路的循环。
算法每找一条增广路需反复执行第 2 步和第 3 步“生长”交错路，这实际上是反复扩充集合 S 和 T 的过程。 算法每循环一次第 2 步和第 3 步,S 和 T 的元素各增加 1 个。 由于 ||||X Yn==，
故这种扩张不会超过 n 次。
而算法每执行一次第二步和第三步，除了需要做两次赋值（ }{,zSS ∪=,}{,yTT ∪= ）
和一次判断（ y 是否 M 饱和的）外，主要计算量在于判断 TSN =)( 。由于总有 ()NS T?,
故可转为判断是否 |()|||NS T= 。 | T |的计数可通过每次循环加 1 来实现,|()|NS 的计数可用
x
2
x
3
x
4
x
5
x
1
y
2
y
3
y
4 y5
y
1
y
2
y
3
y
4
y
5
y
1
x
2
x
3
x
4
x
5
x
1x
2
x
3
x
4 x5
x
1
y
2
y
3
y
4
y
5
y
1
x
2
x
3
x
4 x5
x
1
y
2
y
3
y
4 y5
y
1
10
上一循环的 |()|NS 值加上本次循环新进入 S 集合的点 z 在 ()YNS? 中的邻点数计算，这需要不超过 |Y|＝ n 次判断。因此算法总的计算复杂度约为
3
(6) ()nn n On + = 。
注,(1) 匈牙利算法稍加修改后可用于求二部图的最大匹配（留作习题） ；
(2) 也可在匈牙利算法中引入标号方法，此时算法的计算复杂度为 ()O υ ε? 。具体可参看文献 [6]或 [7]。
(3) 求二部图最大匹配目前已知的最好算法是 Hopcroft 和 Karp 提出的一个
2.5
()O υ 算法。
读者可参看文献 [7]或 [8]。
(4) 求一般图的最大匹配也有多项式时间算法。第一个多项式时间算法是由 Edmonds 给出的一个
4
()O υ 阶算法。关于该算法读者可参看文献 [9]，也可在文献 [6],[7]或 [10]~[12]中找到对该算法的描述。 Ahuja,Magnanti 和 Orlin 对这一算法进行了处理
[13]
,将其复杂度降低为
3
()O υ 。
Even 和 Kariv 提出的一个算法
[14]
将时间复杂度改进到
2.5
()O υ 。目前已知的最快算法是 Micali
和 Vazirani 提出的
0.5
()O ευ 阶算法
[15,16 ]
，该算法对稀疏图运算时，比
2.5
()O υ 算法快。
[6] 谢政，网络算法与复杂性理论（第二版）,国防科技大学出版社,2003。
[7] D.B,West,Introduction to Graph Theory (second edition),Prentice Hall,2001。（中译本,李建中、
骆吉周译，图论导引，机械工业出版社,2006） 。
[8] J,Hopcroft,and R.M,Karp,An
2.5
()On algorithm for maximum matching in bipartite graphs,
SIAM J,Computing,2(1973),225-231,
[9] J,Edmonds,Paths,trees,and flowers,Canad,J,Math.,17(1965),449-467,
[10] C.H,Papadimitriou & K,Steiglitz,Combinatorial Optimization,Algorithms and Complexity,
Prentice-Hall,Inc.,Englewood Cliffs,New Jersey,1982,
[11] 田丰，马仲蕃，图与网络流理论，科学出版社，北京,1987。
[12] 蒋长浩，图论与网络流，中国林业出版社,2001。
[13] R.K,Ahuja,T.L,Magnanti,J,B,Orlin,Network Flows,Theory,Algorithms,and Applications,
Prentice Hall,1993.(影印版：网络流：理论算法与应用，机械工业出版社,2005 年 )。
[14] S,Even,and O,Kariv,An
2.5
()On algorithm for maximum matching in general graphs,in Proc,
16
th
IEEE Symp,Found,Comp,Sci.,1975,100-112,
[15] S,Micali,and V.V,Vazirani,An (| || |)OVE? algorithm for finding maximum matching in
general graphs,in Proc,21
th
IEEE Symp,Found,Comp,Sci.,ACM (1980),17-27,
[16] V.V,Vazirani,A theory of alternating paths and blossoms for proving correctness of the
(| || |)OVE? general graph matching algorithm,Combinatorica,14(1994),71-91,
[17] H.W,Kuhn,The Hungarian method for the assignment problem,Naval Research Logistics
Quarterly,2(1955),83-97,
[18] J,Munkres,Algorithms for the assignment and transportation problems,J,Soc,Indust,Appl,
Math,5(1957),32-38,
11
二、求赋权二部图最大权匹配的 Kuhn－ Munkres 算法
[17,18]
1.背景与问题
最优指派问题,欲安排 n 个人员
n
xxx null,,
21
从事 n 项工作
n
yyy,,,
21
null 。已知每个人能胜任其中一项或几项工作，各人做不同工作的效率不同。求一种工作安排使得总的工作效率达到最大。
图论描述,给定赋权完全二部图 K
n,n
= (X,Y ),X = {
n
xxx null,,
21
},Y＝ {
n
yyy,,,
21
null }，边
ji
xx
有权
ij
w （权可以为 0，这表示
i
x 不胜任工作
j
y ） 。求 K
n,n
的一个具有最大权的完美匹配。
2.算法的理论基础
z 顶点标号与可行顶点标号（ feasible vertex labeling）
图 G 的顶点标号是从顶点集到正整数集的一个映射。对于赋权完全图 ),(
,
wK
nn
，若对每条边 xye =,均有 )()()( xywylxl ≥+,则称这个标号为 ),(
,
wK
nn
的一个 可行顶点标号 。
下图显示了一个赋权二部图以及它的一个可行定点标号。
一个二部图及其可行顶点标号
注,可行顶点标号总是存在的。一种平凡的可行标号是,
∈
∈
=
∈
Yv
Xvvyw
vl
Yy
,0
),(max
)( 。
z 相等子图
记
nn
KG
,
=,设 l 是 ),( wG 的一个可行的顶点标号。令
l
E ＝ )}()()(|)({ xywylxlGExy =+∈,
G 中以
l
E 为边集的生成子图称为 G 的 l 相等子图，记为
l
G 。注意
l
G 的顶点集与 G 的顶点集相同。
下面的例子显示了赋权图
4,4
GK= 的平凡顶点标号，以及在这种标号下的相等子图。
=
0010
0442
2022
4553
4
3
2
1
4321
x
x
x
x
yyyy
w
图 G 中各边的权 图 G 的平凡标号 对应的相等子图
定理 3.4.1 设 l 是图 G 的一个可行顶点标号。若相等子图
l
G 有完美匹配 M
*
，则 M
*
是 G 的最大权完美匹配。
证明：由于相等子图
l
G 是 G 的生成子图，故
l
G 的完美匹配
*
M 也是 G 的完美匹配，而且
1 2 2
1 0 0
1
1
2
2
X
Y
x
2
x
3
x
4
x
1
y
2
y
3
y
4
y
1
5
0
2 4 1
0 0 0
x
2
x
3
x
4
x
1
y
2
y
3
y
4
y
1
12
∑∑
∈∈
==
VvMe
vlewMw )()()(
*
*
,
另一方面，对 G 的任何完美匹配 M，有,
∑∑
∈∈
≤=
VvMe
vlewMw )()()(
可见 )()(
*
MWMW ≥,即
*
M 是 G 的最大匹配。证毕。
由定理 3.4.1 知，欲求赋权完全二部图的最大权匹配，只需求出某个相等子图
l
G 中的完美匹配即可,这可用匈牙利方法求得。 问题是,如果相等子图
l
G 中无完美匹配时怎么办？ Kuhn 和
Munkres 给出修改标号的一个方法，使得新的相等子图的最大匹配逐渐扩大，最终得到有完美匹配的相等子图。
3.算法思想,
首先给出 K
n,n
的任意一个可行顶点标号（如平凡标号）,然后决定相等子图
l
G,在
l
G 中执行匈牙利算法。若在
l
G 中找到完美匹配，则由定理 3.4.1，它就是 G 的最大权匹配。否则，匈牙利算法终止于 XS?,YT?,且 TSN
l
G
=)( 。
令 }\,)()()(min{ TYySxxywylxl
l
∈∈?+=α,(*)
对每个顶点，修改标号如下
∈+
∈?
=′
其它)(
)(
)(
)(
ul
Tuul
Suul
ul
l
l
α
α
。 (**)
可以检验 l′仍是一个可行标号。用 l′替代 l。
l
G
′
的边数比
l
G 的 多。继续上述过程，直到获得一个相等子图含有完全美匹配为止。
4,算法步骤－ Kuhn-Munkres 算法,求赋权完全二部图中的最大权完美匹配。
Step 1,从任一可行的顶点标号 l 开始，决定
l
G,
Step 2,在
l
G 中执行匈牙利算法，如果求得完美匹配 M，则 M 即为 G 的最大权匹配，算法停止；否则，匈牙利算法必终止于某个 XS? 和 YT? 使得 TSN
l
G
=)(,此时转下步。
Step 3,按 (*)式计算
l
α,按 (**)计算新的可行顶点标号 l′,以 l′替代 l,以
l
G
′
替代
l
G,转第
２步。
例 3.4.2 设赋权完全二部图 K
5,5
=（ X,Y）的权矩阵如下，求其最大权完美匹配。
X
x
Yy
T
S
13
3
1
4
2
5
33121
00110
01442
22022
14553
5
4
3
2
1
54321
→
→
→
→
→
x
x
x
x
x
yyyyy
解,求出 X 中每个顶点关联的最大权（权矩阵每行的最大元）,依次为 5,2,4,1,3。取初始匹配
M={x
2
y
2
,x
3
y
3
,x
5
y
5
}。给定初始可行顶点标号为平凡标号，获得相等子图 G
l
如下。
在相等子图 G
l
中执行匈牙利算法，对匹配进行一次增广路扩张后，得新的匹配
M = {x
1
y
2
,x
2
y
1
,x
3
y
3
,x
5
y
5
},
并发现当前的 G
l
无完美匹配，匈牙利算法终止时获得 S = {x
1,
x
3
,x
4
},N(S) = T = {y
2
,y
3
}（见例
3.4.1） 。
按公式 }\,)()()(min{ TYySxxywylxl
l
∈∈?+=α 计算得 1
l
α =,达到最小的 4 条边,x
1
y
4
,x
4
y
1
,x
4
y
4
,x
4
y
5
。按照（ **）式修改标号，得到新的可行顶点标号及其相等子图 G
l
。新的 G
l
比原来增加了四条边 x
1
y
4
,x
4
y
1
,x
4
y
4
,x
4
y
5
。在新的相等子图中以原匹配边作为初始匹配再执行匈牙利算法，经一次增广路扩张后，得到 G
l
的完美匹配 M={x
1
y
2
,x
2
y
1
,x
3
y
3
,x
4
y
4
,x
5
y
5
}（如下图）,此即 G 的最大权匹配。
平凡标号及相应的相等子图 G
l
,
G
l
的一个匹配 M（粗边）
x
2
x
3
x
4
x
5
x
1
y
2
y
3
y
4 y5
y
1
2 4 1 35
0 0 0 00
经一次增广路扩张后发现 G
l
无完美匹配,
S={x
1,
x
3
,x
4
},N(S)=T={y
2
,y
3
}。
x
2
x
3
x
4 x5
x
1
y
2
y
3
y
4
y
5
y
1
修改标号后，新的标号及其相等子图 G
l
。
G
l
比原相等子图增加了的 4 条边,x
1
y
4
,x
4
y
1
,
x
4
y
4
,x
4
y
5
。 粗边是当前 G
l
的一个完美匹配 。
1 1 0 00
x
2
x
3
x
4 x5
x
1
y
2
y
3
y
4 y5
y
1
2 3 0 34
14
Kuhn-Munkres 算法的正确性证明可参看 [7]，其计算复杂度为 O(n
3
)
[6]
。
二部图最大权匹配的其它算法 (如网络流方法 )可参看文献 [6],[13]或 [19]。
对于求一般赋权图中的最大权匹配,Edmonds
[20]
首先给出一个算法，其后 Gabow 和 Lawler
在
3
()O υ 时间内实现了该算法
[ 21,22 ]
。更快的算法已由 Gabow 和 Tarjan 给出
[ 23,24 ]
。
为了在高速骨干通信网络中设计高性能路由器调度算法，人们已经研究并提出了二部图最大匹配和最大权匹配的若干快速启发式算法。读者可参看文献 [25]~[33]。
设在一个完全二部图 K
n,n
= (X,Y)中,X 中每个点对 Y 中各点都有偏好值,Y 中每个点对 X
中各点也有偏好值。给定 K
n,n
一个匹配 M，如果存在 x X∈,y Y∈ 使得 x 对 y 的偏好值大于它对当前匹配点的偏好值,y 对 x 的偏好值也大于它对当前匹配点的偏好值，则称 M 是一个不稳定匹配，而称 (x,y)为一个不稳定对。如果一个完美匹配没有不稳定的未匹配对，则称为 稳定匹配 。
求一个完全二部图的稳定匹配有 O(n
2
)多项式时间算法，读者可参看文献 [7],[13],[34]、
[35]。稳定匹配的综述和新进展见 [35],[36]。稳定匹配在通信网络路由器调度算法中得到了很好的应用，读者可参看文献 [28]及 [37]~[40]。
参考文献 [41]是关于二部图匹配和指派问题的一个综述。有兴趣进一步了解关于匹配理论及其应用的读者，可参阅 [42]~[46]。
[19] R.E,Tarjan,Data structures and network algorithms,Society for Industrial and applied
mathematics,Pennsylvania,Nov,1983,
[20] J,Edmonds,Maximum matchings and a polyhedron with 0,1 vertices,J,Res,Nat,Bur,Standards,
69B(1965),125-130,
[21] H.N,Gabow,An efficient implementation of Edmonds’ algorithm for maximum matchings on
graph,J,Assoc,Comp,Math.,23(1975),221-234,
[22] E.L,Lawler,Combinatorial Optimization,Networks and Matroids,Holt,Rinehart,and Winston,
1976,
[23] H.N,Gabow,Data structures for weighted matching and nearest common ancestors with linking,
In Proc,1th ACM-SIAM Symp,Disc,Algs,SIAM,(1990),434-443,
[24] H.N,Gabow,and R.E,Tarjan,Faster scaling algorithms for general graph matching problems,
Tech,Rept,CU-CS- 432-89 Dept,Comp,Sci,Univ,Colorado-Boulder,1989,
[25] T,Anderson,S,Owicki,J,Saxe,and C,Thacker,High speed switch scheduling for local area
networks,ACM Trans,On Computer Systems,Nov.,(1993) 319-352,
[26] M,Ali,H,Nguyen,A neural network implementation of an input access scheme in a high-speed
packet switch,in Proc,of GLOBECOM 1989,1192-1196,
[27] Ge Nong,J.K Muppala,and M,Hamdi,Analysis of Nonblocking ATM switches with multiple
input queues,IEEE/ACM Transactions on Networking,7:1(1999) 60-74,
[28] N,Mckeown,Scheduling algorithms for input-queued cell switches,Ph.D Dissertation,
University of California at Berkley,May 1995,
[29] N,Mckeown,The iSLIP Scheduling algorithm for input-queued switches,IEEE/ACM
Transactions on Networking,7:2(1999)188-201,
[30] A,Mekkittikul,N,Mckeown,A practical scheduling algorithm to achieve 100% throughput in
15
input-queued switches,in Proc,IEEE INFOCOM’98,San Francisco,CA,Apr,(1998)792-799,
[31] N,Mckeown,V,Anantharam,and J,Walrand,Achieving 100% throughput in an input-queued
switch,in Proc,IEEE INFOCOM’96,San Francisco,Mar.,1(1996) 296-302
[32] D,Shah,M,Kopikare,Delay bounds for approximate maximum weight matching algorithms for
input queued switches,in Proc,IEEE INFOCOM 2002,(2002) 1-8
[33] P,Giaccone,B,Prabhakar,and D,Shah,Randomized scheduling algorithms for high-aggregate
bandwidth switches,IEEE Journal on Selected Areas in Communications,21(4)(2003),pp546-559,
[34] D.Gale,and L.S,Shapley,College admissions and the stability of marriage,American
Mathematical Monthly,69(1962),9-15,
[35] D,Gusfield,and R.W,Irving,The Stable Marriage Problem,Structure and Algorithms,MIT
Press,Cambridge,MA,1989,
[36] K,Cechlárová,and D,F,Manlov,The exchange-stable marriage problem,Discrete Applied
Mathematics,152(2005)109-122
[37] E,Leonardi,M,Mellia,F,Neri,and M.A,Marsan,On the stability of input-queued switches with
speed-up,IEEE/ACM Transactions on Networking,9:1(2001),104-118,
[38] S.T,Chuang,A,Goel,N,Mckeown,and B,Prabhakar,Matching output queueing with combined
input and output queueing,IEEE J,Selected Areas Communication,17(1999) 1030-1039,
[39] M,Ajmone Marsan,E,Leonardi,M,Mellia,and F,Neri,Stability of maximal size matching
scheduling in input-queued cell switches,in IEEE ICC,New Orleans,LA,June(2000)1758-1763,
[40] Ge Nong,and M,Hamdi,On the provision of integrated QoS guarantees of unicast and multicast
traffic in input-queued switches,in Proc,Global Telecommunications Conference-Globecom’99,
1742-1746,
[41] R,E,Burkard,Selected topics on assignment problems,Discrete Applied Mathematics,
123(2002)257-302,
[42] P.M,Vaidya,Approximate minimum weight matching on points in k-dimensional space,
Algorithmica,1990,
[43] P.M,Vaidya,Geometry helps in matching,SIAM Journal on Computing,18(1989) 1201-1225,
[44] A,Gibbons,Algorithmic Graph Theory,Cambridge University Press,1985,
[45] L,Lováze,and M,D,Plummer,Matching Theory,Annals of Discrete Mathematics,29(1986),
[46] A,Schrijver,Combinatorial Optimization Polyhedra and Efficiency,New York,NY,
Springer-Verlag,2003,
第三章习题
1,证明：一棵树最多只有一个完美匹配。
2,证明一棵树 T 有完美匹配当且仅当对 (),vVG? ∈ 奇分支数 o(T-v)=1。
3,两人在图 G 上做游戏：交替选择相异的顶点 null,,,
210
vvv,使得对每个
i
vi,0> 相邻于
1?i
v,
选择最后一个顶点者获胜。证明：第一个选点人有一个得胜策略当且仅当图 G 没有完美匹配。
16
4,设 M
1
,M
2
是简单图 G 的两个匹配,G′是
12
MM⊕ 在 G 中的边导出子图。证明 G′的每个连通分支必定是下列两种情况之一,
（ 1）边在 M
1
和 M
2
中交替出现的偶长度圈； （ 2）边在 M
1
和 M
2
中交替出现的路。
5,设 M 和 N 是图 G 中两个不相交的匹配，且 |M|>|N|。证明,G 中必存在两个不相交匹配 M′
和 N′，使得,M NMN′′=∪∪且 | |||1,||||1MM NM′ ′=?=+。
6,设 G=(X,Y)是一个二部图,U
1
,U
2
是 X 的两个子集,V
1
,V
2
是 Y 的两个子集。 M
1
是 G 中 U
1
与 V
1
间的一个匹配,M
2
是 G 中 U
2
与 V
2
间的一个匹配。证明：存在匹配
12
MM M? ∪,
它饱和 U
1
和 V
2
。
7,设 G=(X,Y)是一个二部图，利用上题的结论证明,（ 1） G 中存在一个匹配饱和 G 的所有最大度顶点； （ 2） G 的边集可划分成 (G)Δ 个匹配。
8,证明下图没有完美匹配。
9,设 G 是一个 3 正则图且 G 有一个包含所有顶点的圈，证明 G 是可 1－因子分解的。
10,证明：若 3 正则图有割边，则不能 1－因子分解。
11,证明奇数阶完全图 K
2n+1
是可 2－因子分解的，但偶数阶完全图 K
2n+1
不可 2－因子分解。
12,证明,每个无割边的 3 度正则图可分解为一个 1 因子和一个 2 因子的并。
13,证明：一个连通图是可 2－因子化的当且仅当它是偶数度正则的。利用此结论证明：偶数阶完全图可分解为一个 1 因子和 n?1 个 2 因子的并。
14,修改匈牙利算法使其适用于求二部图的最大匹配。
15,已知工人 x
1
,x
2
,x
3
,x
4
,x
5
做工作 y
1
,y
2
,y
3
,y
4
,y
5
的效率 w
ij
如下矩阵所示,
W=(
ij
w ) =
31241
50122
31550
13210
22143
5
4
3
2
1
54321
x
x
x
x
x
yyyyy
,
试给出一种工作效率最大的分配方案。
16,在某届大学毕业生招聘会上，有 n 个毕业生可选择 m 个单位（ mn≥ ） 。已知每个毕业生至少对 r 个单位有工作意向，而每个招聘单位至多看中了其中 r?1 个毕业生（ 1 rm≤≤）,并最终要从中录用一名。问最多有多少个单位可选择到一名看中的毕业生？
第三章 匹配理论
§3.1 匹配与最大匹配
定义 3.1.1 设 G 是一个图,)(GEM?,满足:对
i
e?,Me
j
∈,
i
e 与
j
e 在 G 中不相邻，则称 M 是 G 的一个匹配。对匹配 M 中每条边 uve =,其两端点 u 和 v 称为被匹配 M 所匹配，
而 u和 v 都称为是 M饱和的(saturated vertex)。
注,每个顶点要么未被 M 饱和,要么仅被 M 中一条边饱和。
定义 3.1.2 设 M 是 G 的一个匹配,若 G 中无匹配 M′,使得 |||| MM >′,则称 M 是 G 的一个最大匹配；如果 G 中每个点都是 M 饱和的,则称 M 是 G 的完美匹配(Perfect matching),
显然,完美匹配必是最大匹配。
例如，在下图 G
1
中，边集 {e
1
},{e
1
,e
2
},{e
1
,e
2
,e
3
}都构成匹配,{e
1
,e
2
,e
3
}是 G
1
的一个最大匹配。在 G
2
中，边集 {e
1
,e
2
,e
3
,e
4
}是一个完美匹配，也是一个最大匹配。
定义 3.1.3 设 M 是 G 的一个匹配,G 的 M交错路是指其边 M 和 MGE \)( 中交替出现的路。 如果 G 的一条 M 交错路 (alternating path)的起点和终点都是 M 非饱和的,则称其为一条 M
可扩展路或 M增广路(augmenting path)。
定理 3.1.1(Berge,1957) 图 G 的匹配 M 是最大匹配的充要条件是 G中不存在 M 可扩展路。
证明,必要性,设 M 是 G 的一个最大匹配。如果 G 中存在一个 M 可扩展路 P,则将 P 上所有不属于 M 的边构成集合 M′。显然 M′也是 G 的一个匹配且比 M 多一条边。这与 M 是最大匹配相矛盾。
充分性,设 G 中不存在 M 可扩展路。若匹配 M 不是最大匹配，则存在另一匹配 M′,使
|||| MM >′,令
][ MMGH ′⊕=,( MMMMMM ′?′=′⊕ ∩∪ 称为对称差)。
则 H 中每个顶点的度非1即2(这是因为一个顶点最多只与 M 的一条边及 M′的一条边相关联)。故 H 的每个连通分支要么是 M 的边与 M′的边交替出现的一个偶长度圈，要么是 M 的边与 M′的边交替出现的一条路。 由于 |||| MM >′,H 的边中 M′的边多于 M 的边,故必有 H
的某个连通分支是一条路，且始于 M′的边又终止于 M′的边。这条路是一条 M 可扩展路。这与条件矛盾。 证毕。
G
1
G
2
e
1
e
2
e
3
e
2
e
1
e
3
e
4
2
§3.2 完美匹配
定义 3.2.1 图 G 的奇分支,G 的含有奇数个顶点的连通分支。 用 )(GO 表示 G 的奇分支的个数。
定理 3.2.1 (Tutte,1947) 图 G 有完美匹配的充分必要条件是对 )(GVS,||)\( SSGO ≤ 。
证明 （ Lovász,1973） 必要性,设图 G 有完美匹配 M。对 )(GVS,若 SG \ 无奇分支，则
0)\( =SGO ；否则，设
k
GGG,,,
21
null 是 SG \ 的所有奇分支。注意每个
i
G 中至少有一个顶点
i
u 在 M 下与 S 中的某个顶点
i
v 配对（ ki,,2,1 null= ）,（因
i
G 是奇分支,M 是完美匹配） 。
故 SvvvkSGO
k
≤== |},,,{|)\(
21
null 。
充分性 （反证法）,设 G 满足：对 )(GVS,SSGO ≤)\(,但 G 没有完美匹配。首先，
取 φ=S,知 0)( =GO,故 )(GV 是偶数。现在，给 G 添加边以获得一个没有完美匹配而有尽可能多的边的图
*
G 。因 G 是
*
G 的生成子图，故对 )(GVS,SG \ 是 SG \
*
的生成子图，
从而
SSGOSGO ≤≤ )\()\(
*
,（ *）
令 }1)(),({
*
*
=∈= νudGVuuU
G
,
若 )(
*
GVU =,则
*
G 是偶数阶完全图，有完美匹配。这与
*
G 的性质矛盾。因此，
)(
*
GVU ≠,可以证明，此时 UG \
*
的每个连通分支都是完全图（记为命题Ａ，另证） 。
由（ *）式,UUGO ≤)\(
*
，即 UG?
*
的奇分支个数最多是 U 。但这样一来，
*
G 就有一个完美匹配,
UG \
*
的各奇分支中的一个顶点和 U 的一个顶点配对； U 中余下的顶点以及 UG \
*
的各分支中余下的顶点在本分支内配对（由于各分支及 U 都是完全图） 。
…
u
1
u
2
u
k …
S
…
v
2
v
k
v
1
…
G
1
G
2
G
k
奇分支 偶分支
…
…
U
G
*
\U 的奇分支 G
*
\U 的偶分支
…
3
这与
*
G 无完美匹配矛盾。证毕,
命题Ａ的证明,在上述充分性证明的条件下，当 )(
*
GVU ≠ 时,UG \
*
的每个连通分支都是完全图。
用反证法证明：若不然，设 UG \
*
中某个连通分支
i
G 不是完全图，则 3)( ≥
i
GV 。必存在
)(,,
i
GVzyx ∈,使得 )(,
i
GEyzxy ∈,且 )(
i
GExz? 。由于 Uy?,故必有与 y 不相邻的顶点，即必存在 ),\(
*
UGVw∈ 使得 )(
*
GEyw? 。
由于
*
G 是不含完美匹配的极大图，所以 xzG +
*
和 ywG +
*
都含有完美匹配，分别设为
1
M 和
2
M 。用 H 表示 { }ywxzG,
*
∪ 中由
21
MM ⊕ 导出的子图。由于对 )(HVu∈?,2)( =ud
H
或
0（由
1
M 和
2
M 都是完美匹配知）,故 H 的每个非平凡连通分支都是其边在
1
M 和
2
M 中交替出现的偶长度圈。下分两种情形,
(1) xz 和 yw分别在 H 的不同分支中。设 yw在 H 的某个圈 C 上，则
1
M 在 C 上的边连同
2
M 不在 C 上的边构成
*
G 的一个完美匹配。这与
*
G 的选择矛盾。
情形（ 1） 情形（ 2）
(2) xz 和 yw在 H 的同一分支Ｃ中,由 x 和 z 的对称性,不妨设 zwyx,,,在 C 中依次出现，
并设
1
M 在 C 的 zywnull 段中的边集为
1
M′，
2
M 在 C 的 zywnull 段中的边集为
2
M′，于是
)\(}{
221
MMyzM ′′ ∪∪
是
*
G 的完美匹配，又与
*
G 的选择矛盾。
综合 (1),(2)两种情形，便证明了 UG \
*
的每个连通分支都是完全图。证毕。
推论 3.2.1 ( 1?k )边连通偶数阶 k 正则图有完美匹配
证明：设 G 是命题中所述的 k 正则图。
当 1=k 时，结论显然。
以下假定 2≥k 。设 S 是 G 的任一个非空顶点集，
n
GGG,,,
21
null 是 SG \ 的奇分支。令
),(
ii
GV=ν eem
i
|{|= 是
i
G 与 S 之间的连边 |} 。
w
z
y
x
C
M
1
的边
M
2
的边
w
y
x z
C
…
U
G
i
x
wy
z
4
由于 1?≥′ kκ,故 1?≥ km
i
,),,2,1( mi null= 。
若存在 i,使得 1?= km
i
，则因
i
GVv
G
kvd
i
ν=
∑
∈ )(
)(,Skvd
Sv
G
=
∑
∈
)(,（ *）
从而 )(2)()(
)()(
ii
GVv
G
GVv
Gi
Gkvdvdm
i
i
i
εν?=?=
∑∑
∈∈
。因此,
1)1()1()(2 +?==?=
iiiii
kkkmkG νννε 。
但因 1?
i
ν 是偶数（每个
i
G 是奇分支）,上式两端不可能相等。这个矛盾说明 km
i
≥
（ ),,2,1 ni null=,于是
knm
n
i
i
≥
∑
=1
,（**）
故有 Sud
k
m
k
nSGO
Su
G
n
i
i
=
∑∑
≤
∈=
≤?=?
(*)1(**)
)(
11
)(
由 Tutte 定理,G 有完美匹配。证毕。
推论 3.2.2 (Peterson,1891) 2边连通（无割边）的 3 正则图有完美匹配。
证明：设 G 是 2 边连通的 3 正则图。因 νε 3)(2
)(
==
∑
∈ GVv
vd,故 ν 为偶数。由推论 3.2.1,G 有完美匹配。 证毕
注,有割边的 3 正则图未必有完美匹配，例如，对如下所示的图 G，因 ()3OG v?=，故无完美匹配。
推论 3.2.3 偶数阶完全图
n
K
2
有 12?n 个边不重的完美匹配。
…
…
G
1
G
2
G
n
S
G\S 的奇分支 G\S 的偶分支
G
v
5
证明：用平面上正 12?n 边形的点代表
1221
,,,
n
vvv null,而用其中心点代表
n
v
2
点。用直线段连接每个顶点对,即得
n
K
2
。 构作匹配
i
M 为边
ni
vv
2
和所有与
ni
vv
2
垂直的边之集。 易检验每个
i
M
都是 G 的完美匹配，且不同的
i
M 无公共边。例如，按这种方法构作出 K
6
的两个完美匹配如下图 (b),(c)所示。显然，
n
v
2
关联的每条边对应这样一个完美匹配，故共有 12?n 个边不重的完美匹配。证毕。
§3.3 二部图的匹配
定理 3.3.1 (Hall,1935) 设 G 是具有二划分 ),( YX 的二部图，则 G 有饱和 X 的匹配当且仅当对 XS,SSN ≥)(,其中 )(SN 表示 S 的所有邻点之集。
证明：必要性。设 G 有饱和 X 的匹配 M,则对 XS,因 S 的顶点在 M 下和 )(SN 中顶点配对，故 SSN ≥)( 。
充分性：设 ),( YXG = 是二部图，且对 XS,SSN ≥)( 。下用反证法。
假如 G 没有饱和 X 的匹配，则 G 的最大匹配
*
M 不能饱和 X 的所有顶点。设 u 是 X 的一个
*
M 不饱和点，并设
|{vA = u 到 v 有
*
M 交错路 }。
由于
*
M 是最大匹配，故由 Berge 定理,u 是 A 中唯一的
*
M 非饱和点。令
XAS ∩=,YAT ∩= 。
注意 }{uS? 中的顶点在
*
M 下与 T 中的顶点一一配对（因 Su∈,且对 Tt ∈?,u 与 t 有
*
M
交错路
t
P 相连，而且 t 是
*
M 饱和的，故交错路
t
P 上最后一条边必是
*
M 的边，它将 S 中一个顶点与 t 配对。而且不同的 t 会有 S 中不同的顶点相配，否则会有两条
*
M 的边关联到 S 中同一顶点） 。因此
1?= ST 。 (1)
X
Y
S
T
u
M
*
的边
v
6
v
1
v
3
v
2 v5
v
4
v
6
v
1
v
3
v
2
v
5
v
4
v
6
v
1
v
3
v
2
v
5
v
4
(a)
(c)
(b)
6
此外,TSN?)( （因 T 中顶点通过 S 中顶点与 u 连
*
M 交错路）,且 TSN?)( （对 )(SN
中每个顶点 t,设它是 S 中顶点 s 的邻点,从 u 到 s 的
*
M 交错路必可延伸为 u 到 t 的
*
M 交错路） 。故
TSN =)( (2)
由(1)、(2)知,() | | 1NS T S S==?<，这与定理条件矛盾。证毕。
推论 3.3.1 设 ),( YXG = 是二部图，若 X 中每个顶点至少关联 k 条边（ )1≥k 而 Y 中每个顶点至多关联 k 条边，则 G 中存在饱和 X 的匹配。
证明：由条件知，对 XS,S 至少关联 || Sk 条边。这 || Sk 条边至少关联 Y 中 || S 个顶点。
即 SSN ≥)(,由 Hall 定理,G 有饱和 X 的匹配。证毕。
推论 3.3.2.(Frobenius,1917) 具有二划分 ),( YX 的二部图 G 有完美匹配的充分必要条件是
YX = 且对 XS （或 Y ）,均有 |||)(| SSN ≥ 。
证明：显然。
推论 3.3.3 (K?nig,1916) 设 G 是 k 正则二部图 )0( >k,则 G 有 k 个边不重的完美匹配。
证明,（1）先证 G 有完美匹配。
证法１：设 ),( YXG = 是 k 正则二部图，则 YkGEXk == )(,因 0>k,故 YX =,任取 XS?,令 =
1
E {G 中与 S 关联的边},=
2
E {G 中与 N(S)关联的边}。则
21
EE? 。因而
SkEESNk =≥=
12
)(,即 SSN ≥)( 。由推论 3.3.2,G 有完美匹配。
证法２,由推论 3.3.1,G 中有饱和 X 的匹配。因 YX = （如前所证）,故这个匹配就是完美匹配。
（2）再证 G 中有 k 个边不重的完美匹配（用归纳法） 。
当 1=k 时，显然。
设对所有 k 正则二部图，结论成立。下证对 )1( +k 正则二部图 G,结论也成立。
设 M 是 G 的一个完美匹配。令 MGG \=′ 。则 G′是 k 正则二部图。由归纳假设,G′中有 k 个边不重的完美匹配。故 G 中有 1+k 个边不重的完美匹配。证毕。
下一推论是显然的。
推论 3.3.4 完全二部图
kk
K
,
中存在 k 个边不重的完美匹配。
推论 3.3.5 设 ).( YXG = 是二部图，且 nYX == 。若
2
)(
n
G ≥δ,则 G 有完美匹配。
证明(用反证法)：若 G 没有完美匹配，则由推论 3.3.2，存在 φ≠? SXS,，使 |||)(| SSN < 。
因 G 是二部图且
2
)(
n
G ≥δ,故
2
)(|)(|||
n
GSNS ≥≥> δ,且 φ≠)(\ SNY （因
7
|||)(| SSN < |||| YX =≤ ） 。令 )(\ SNYu∈,则 SXuN \)(?,因此,
22
|||||)(|)()(
nn
nSXuNudG
G
=?<?≤=≤δ 。
这与条件矛盾。故 G 有完美匹配。证毕。
例 3.3.1 下图所示的是 14 个大小相同的正方形组成的图形。试证明：不论如何用剪刀沿着图形中所画的直线对它进行裁剪，总剪不出 7 个由相邻的两个小正方形组成的矩形来。
证明：将图形中方格从 1 到 14 编号。以方格为顶点集作简单图 G = (V,E)，边 )(GEij∈ 当且仅当 i,j 所在的方格在图形中相邻（有公共边） 。
注意 G 中每条边对应于原图形中由相邻两个小正方形组成的矩形，故剪出 7 个矩形相当于在 G 中求由 7 条边组成的匹配。由于有 14 个顶点，故所求的是完美匹配。但这样的匹配是不存在的。事实上,G 是一个二部图，其二划分为
X={1,3,4,6,9,11,12,14},Y={2,5,7,8,10,13}。
|X| = 8 > 6 = |Y|。由推论 3.3.2，不存在完美匹配。
注,G 的 k 正则生成子图称为 G 的 k 因子。若 G 存在无公共边的 k 因子
n
HHH,,,
21
null,
使得
n
HHHG ∪null∪∪
21
=,则称 G 是 可 k－因子分解的 。
推论 3.2.3 证明了完全图
n
K
2
是可 1－因子分解的；推论 3.3.4 证明了完全二部图
nn
K
,
是可
1－因子分解的；推论 3.3.3 证明了每个 k 正则二部图是可 1－因子分解的。
若图 G 有 1 因子，则它显然应是偶数阶图。因此奇数阶完全图 K
2n+1
不可能有 1 因子。
因子分解是图论研究的一个重要选题，进一步的了解可参看
[1] G,Chartrand,and O.R,Ollermann,Applied and Algorithmic Graph Theory,MCGraw-Hill,New
York,1993,
[2] J,Akiyama,M,Kano,Factors and factorizations of graphs — a survey,J,Graph Theory,9(1985),
1-42,
[3] W.D,Wallis,One-factorizations,Kluwer Academic Publishers,Dordrecht,Boston,1997,
[4] Guizhen Liu,and Binhai Zhu,Some problems on factorizations with constraints in bipartite graphs,
128(2003),421-434,
4 6 75
1 32
8 9 1110
12 13 14
4
1
6 7
8
5
32
9 1110
12 13 14
8
§3.4 二部图中最大匹配与最大权匹配的算法
一、求完美匹配的匈牙利算法
1.背景与问题
指派问题 （ assignment problem）,欲安排 n 个人员
n
xxx null,,
21
从事 n 项工作
n
yyy,,,
21
null 。已知每个人能胜任其中一项或几项工作。试问：能否给每个人分配一项他所胜任的工作？若能，
如何求出这种安排？
图论描述,对于一个二部图 G = (X,Y ),X = {
n
xxx null,,
21
},Y＝ {
n
yyy,,,
21
null }，当且仅当
i
x
胜任工作
j
y 时,)(GEyx
ji
∈ 。问,G 中是否有完美匹配？若有，如何求之？
2.理论基础
Berge 定理（定理 3.1.1）,图 G 的匹配 M 是最大匹配的充要条件是 G 中不存在 M 可扩展路。
Hall 定理（定理 3.3.1）,设 G 是具有二划分 ),( YX 的二部图，则 G 有饱和 X 的匹配当且仅当对 XS,SSN ≥)(,其中 )(SN 表示 S 的所有邻点之集。
3.匈牙利算法
匈牙利算法由匈牙利数学家 Egerváry 首先提出，后来由 Edmonds(1965)基于 Berge 定理和
Hall 定理进行了改进 [5]。这种算法既能判定一个二部图中完美匹配是否存在，又能在存在时求出一个完美匹配。
[5] J,Edmonds,Path,tree and flowers,Canad,J,Math,17(1965)449-467,
算法思想,从图 G 的任何匹配 M 开始。
若 M 饱和 X，则 M 是 G 的完美匹配。
若 M 不饱和 X，在 X 中选择一个 M 不饱和点 x。若存在以 x 为起点的 M 增广路 P，则由
Berge 定理知 M 不是最大匹配，且 )(PEMM ⊕=′ 是比 M 更大的匹配。用 M′替代 M 重复上述过程；若 G 中不存在以 x 为起点的 M 增广路，则可找到与 x 由 M 交错路相连的顶点集合 A，
而 XAS ∩= 满足 |||)(| SSN < （见 Hall 定理的证明） 。由 Hall 定理,G 不存在完美匹配。
算法步骤,
step0,任取图 G 的一个匹配 M。
step1,若 M 饱和 X，则停止,M 是 G 的完美匹配。
否则，取 X 中一个 M 不饱和点 x，记 φ==,},{,TxS 。
step2,若 TSN =)(,则停止,G 无完美匹配。 （因 ||1|||||)(| SSTSN <?== ） 。
否则取 TSNy \)(∈ 。
step3,若 y 是 M 饱和的，设 Myz∈,令 }{,zSS ∪=,}{,yTT ∪=,转 step2。 （此时仍保
9
持 )1||||?= ST 。否则，取 M 增广路 ),( yxP,令 )(,PEMM ⊕=,转 step1,
例 3.4.1 判断如下二部图是否存在完美匹配。若存在，求其出一个完美匹配；若不存在，给出满足 TSN =)( 的集合 S 和 T。
解,从一个初始匹配 M＝
22 33 55
{,,}x yxyxy（图 1）出发，执行匈牙利算法。因 M 尚未饱和 X，
找到 X 中一个 M 未饱和点 x
1
。从 x
1
出发，反复执行算法第 2 步和第 3 步，找到一条 M 增广路
x
1
y
2
x
2
y
1
（图 2） 。按第 3 步，沿增广路交换进入匹配和不进入匹配的边，匹配扩大为 M＝
12 21 33 55
{,,,}x yxyxyxy（图 3） 。
图 1：图 G=(X,Y)及一个匹配 M 图 2,M 增广路 x
1
y
2
x
2
y
1
图 3：无完美匹配
因 M 仍未饱和 X，按算法第 1 步，找到 X 中一个 M 未饱和点 x
4
。然后算法令
4
{},SxTφ==，并转入第 2 步试图找一条从 x
4
出发的 M 增广路。因当前
23
() {,}NS y y=,
()NS T≠,从 ()\NS T中任意取出一个，比如 y
3
，转到第三步。因 y
3
是 M 饱和的，其匹配点为 x
3
，按算法第 3 步,S 和 T 更新为
43 3
{,},{}SxxTy= = 。此后，转第 2 步判断是否
TSN =)( 。因当前
23
() {,}NS y y T=≠，故取
2
()\y NS T∈,再次循环执行第 3 步，找到
y
2
的匹配点 x
1
,S 和 T 进一步更新为
431 32
{,,,},{,}SxxxTyy= =,再转第 2 步。此时发现
23
() {,}NS y y T==，因此该图不存在完美匹配。算法找到的满足 TSN =)( 的集合为
431 32
{,,,},{,}SxxxTyy。
匈牙利算法的正确性由 Berge 定理和 Hall 定理可知。
匈牙利算法是多项式时间算法。事实上，设 ||||nXY= = 。算法每找到一条增广路更新一次匹配，匹配边增加一条，故最多需执行 n 次增广路的循环。
算法每找一条增广路需反复执行第 2 步和第 3 步“生长”交错路，这实际上是反复扩充集合 S 和 T 的过程。 算法每循环一次第 2 步和第 3 步,S 和 T 的元素各增加 1 个。 由于 ||||X Yn==，
故这种扩张不会超过 n 次。
而算法每执行一次第二步和第三步，除了需要做两次赋值（ }{,zSS ∪=,}{,yTT ∪= ）
和一次判断（ y 是否 M 饱和的）外，主要计算量在于判断 TSN =)( 。由于总有 ()NS T?,
故可转为判断是否 |()|||NS T= 。 | T |的计数可通过每次循环加 1 来实现,|()|NS 的计数可用
x
2
x
3
x
4
x
5
x
1
y
2
y
3
y
4 y5
y
1
y
2
y
3
y
4
y
5
y
1
x
2
x
3
x
4
x
5
x
1x
2
x
3
x
4 x5
x
1
y
2
y
3
y
4
y
5
y
1
x
2
x
3
x
4 x5
x
1
y
2
y
3
y
4 y5
y
1
10
上一循环的 |()|NS 值加上本次循环新进入 S 集合的点 z 在 ()YNS? 中的邻点数计算，这需要不超过 |Y|＝ n 次判断。因此算法总的计算复杂度约为
3
(6) ()nn n On + = 。
注,(1) 匈牙利算法稍加修改后可用于求二部图的最大匹配（留作习题） ；
(2) 也可在匈牙利算法中引入标号方法，此时算法的计算复杂度为 ()O υ ε? 。具体可参看文献 [6]或 [7]。
(3) 求二部图最大匹配目前已知的最好算法是 Hopcroft 和 Karp 提出的一个
2.5
()O υ 算法。
读者可参看文献 [7]或 [8]。
(4) 求一般图的最大匹配也有多项式时间算法。第一个多项式时间算法是由 Edmonds 给出的一个
4
()O υ 阶算法。关于该算法读者可参看文献 [9]，也可在文献 [6],[7]或 [10]~[12]中找到对该算法的描述。 Ahuja,Magnanti 和 Orlin 对这一算法进行了处理
[13]
,将其复杂度降低为
3
()O υ 。
Even 和 Kariv 提出的一个算法
[14]
将时间复杂度改进到
2.5
()O υ 。目前已知的最快算法是 Micali
和 Vazirani 提出的
0.5
()O ευ 阶算法
[15,16 ]
，该算法对稀疏图运算时，比
2.5
()O υ 算法快。
[6] 谢政，网络算法与复杂性理论（第二版）,国防科技大学出版社,2003。
[7] D.B,West,Introduction to Graph Theory (second edition),Prentice Hall,2001。（中译本,李建中、
骆吉周译，图论导引，机械工业出版社,2006） 。
[8] J,Hopcroft,and R.M,Karp,An
2.5
()On algorithm for maximum matching in bipartite graphs,
SIAM J,Computing,2(1973),225-231,
[9] J,Edmonds,Paths,trees,and flowers,Canad,J,Math.,17(1965),449-467,
[10] C.H,Papadimitriou & K,Steiglitz,Combinatorial Optimization,Algorithms and Complexity,
Prentice-Hall,Inc.,Englewood Cliffs,New Jersey,1982,
[11] 田丰，马仲蕃，图与网络流理论，科学出版社，北京,1987。
[12] 蒋长浩，图论与网络流，中国林业出版社,2001。
[13] R.K,Ahuja,T.L,Magnanti,J,B,Orlin,Network Flows,Theory,Algorithms,and Applications,
Prentice Hall,1993.(影印版：网络流：理论算法与应用，机械工业出版社,2005 年 )。
[14] S,Even,and O,Kariv,An
2.5
()On algorithm for maximum matching in general graphs,in Proc,
16
th
IEEE Symp,Found,Comp,Sci.,1975,100-112,
[15] S,Micali,and V.V,Vazirani,An (| || |)OVE? algorithm for finding maximum matching in
general graphs,in Proc,21
th
IEEE Symp,Found,Comp,Sci.,ACM (1980),17-27,
[16] V.V,Vazirani,A theory of alternating paths and blossoms for proving correctness of the
(| || |)OVE? general graph matching algorithm,Combinatorica,14(1994),71-91,
[17] H.W,Kuhn,The Hungarian method for the assignment problem,Naval Research Logistics
Quarterly,2(1955),83-97,
[18] J,Munkres,Algorithms for the assignment and transportation problems,J,Soc,Indust,Appl,
Math,5(1957),32-38,
11
二、求赋权二部图最大权匹配的 Kuhn－ Munkres 算法
[17,18]
1.背景与问题
最优指派问题,欲安排 n 个人员
n
xxx null,,
21
从事 n 项工作
n
yyy,,,
21
null 。已知每个人能胜任其中一项或几项工作，各人做不同工作的效率不同。求一种工作安排使得总的工作效率达到最大。
图论描述,给定赋权完全二部图 K
n,n
= (X,Y ),X = {
n
xxx null,,
21
},Y＝ {
n
yyy,,,
21
null }，边
ji
xx
有权
ij
w （权可以为 0，这表示
i
x 不胜任工作
j
y ） 。求 K
n,n
的一个具有最大权的完美匹配。
2.算法的理论基础
z 顶点标号与可行顶点标号（ feasible vertex labeling）
图 G 的顶点标号是从顶点集到正整数集的一个映射。对于赋权完全图 ),(
,
wK
nn
，若对每条边 xye =,均有 )()()( xywylxl ≥+,则称这个标号为 ),(
,
wK
nn
的一个 可行顶点标号 。
下图显示了一个赋权二部图以及它的一个可行定点标号。
一个二部图及其可行顶点标号
注,可行顶点标号总是存在的。一种平凡的可行标号是,
∈
∈
=
∈
Yv
Xvvyw
vl
Yy
,0
),(max
)( 。
z 相等子图
记
nn
KG
,
=,设 l 是 ),( wG 的一个可行的顶点标号。令
l
E ＝ )}()()(|)({ xywylxlGExy =+∈,
G 中以
l
E 为边集的生成子图称为 G 的 l 相等子图，记为
l
G 。注意
l
G 的顶点集与 G 的顶点集相同。
下面的例子显示了赋权图
4,4
GK= 的平凡顶点标号，以及在这种标号下的相等子图。
=
0010
0442
2022
4553
4
3
2
1
4321
x
x
x
x
yyyy
w
图 G 中各边的权 图 G 的平凡标号 对应的相等子图
定理 3.4.1 设 l 是图 G 的一个可行顶点标号。若相等子图
l
G 有完美匹配 M
*
，则 M
*
是 G 的最大权完美匹配。
证明：由于相等子图
l
G 是 G 的生成子图，故
l
G 的完美匹配
*
M 也是 G 的完美匹配，而且
1 2 2
1 0 0
1
1
2
2
X
Y
x
2
x
3
x
4
x
1
y
2
y
3
y
4
y
1
5
0
2 4 1
0 0 0
x
2
x
3
x
4
x
1
y
2
y
3
y
4
y
1
12
∑∑
∈∈
==
VvMe
vlewMw )()()(
*
*
,
另一方面，对 G 的任何完美匹配 M，有,
∑∑
∈∈
≤=
VvMe
vlewMw )()()(
可见 )()(
*
MWMW ≥,即
*
M 是 G 的最大匹配。证毕。
由定理 3.4.1 知，欲求赋权完全二部图的最大权匹配，只需求出某个相等子图
l
G 中的完美匹配即可,这可用匈牙利方法求得。 问题是,如果相等子图
l
G 中无完美匹配时怎么办？ Kuhn 和
Munkres 给出修改标号的一个方法，使得新的相等子图的最大匹配逐渐扩大，最终得到有完美匹配的相等子图。
3.算法思想,
首先给出 K
n,n
的任意一个可行顶点标号（如平凡标号）,然后决定相等子图
l
G,在
l
G 中执行匈牙利算法。若在
l
G 中找到完美匹配，则由定理 3.4.1，它就是 G 的最大权匹配。否则，匈牙利算法终止于 XS?,YT?,且 TSN
l
G
=)( 。
令 }\,)()()(min{ TYySxxywylxl
l
∈∈?+=α,(*)
对每个顶点，修改标号如下
∈+
∈?
=′
其它)(
)(
)(
)(
ul
Tuul
Suul
ul
l
l
α
α
。 (**)
可以检验 l′仍是一个可行标号。用 l′替代 l。
l
G
′
的边数比
l
G 的 多。继续上述过程，直到获得一个相等子图含有完全美匹配为止。
4,算法步骤－ Kuhn-Munkres 算法,求赋权完全二部图中的最大权完美匹配。
Step 1,从任一可行的顶点标号 l 开始，决定
l
G,
Step 2,在
l
G 中执行匈牙利算法，如果求得完美匹配 M，则 M 即为 G 的最大权匹配，算法停止；否则，匈牙利算法必终止于某个 XS? 和 YT? 使得 TSN
l
G
=)(,此时转下步。
Step 3,按 (*)式计算
l
α,按 (**)计算新的可行顶点标号 l′,以 l′替代 l,以
l
G
′
替代
l
G,转第
２步。
例 3.4.2 设赋权完全二部图 K
5,5
=（ X,Y）的权矩阵如下，求其最大权完美匹配。
X
x
Yy
T
S
13
3
1
4
2
5
33121
00110
01442
22022
14553
5
4
3
2
1
54321
→
→
→
→
→
x
x
x
x
x
yyyyy
解,求出 X 中每个顶点关联的最大权（权矩阵每行的最大元）,依次为 5,2,4,1,3。取初始匹配
M={x
2
y
2
,x
3
y
3
,x
5
y
5
}。给定初始可行顶点标号为平凡标号，获得相等子图 G
l
如下。
在相等子图 G
l
中执行匈牙利算法，对匹配进行一次增广路扩张后，得新的匹配
M = {x
1
y
2
,x
2
y
1
,x
3
y
3
,x
5
y
5
},
并发现当前的 G
l
无完美匹配，匈牙利算法终止时获得 S = {x
1,
x
3
,x
4
},N(S) = T = {y
2
,y
3
}（见例
3.4.1） 。
按公式 }\,)()()(min{ TYySxxywylxl
l
∈∈?+=α 计算得 1
l
α =,达到最小的 4 条边,x
1
y
4
,x
4
y
1
,x
4
y
4
,x
4
y
5
。按照（ **）式修改标号，得到新的可行顶点标号及其相等子图 G
l
。新的 G
l
比原来增加了四条边 x
1
y
4
,x
4
y
1
,x
4
y
4
,x
4
y
5
。在新的相等子图中以原匹配边作为初始匹配再执行匈牙利算法，经一次增广路扩张后，得到 G
l
的完美匹配 M={x
1
y
2
,x
2
y
1
,x
3
y
3
,x
4
y
4
,x
5
y
5
}（如下图）,此即 G 的最大权匹配。
平凡标号及相应的相等子图 G
l
,
G
l
的一个匹配 M（粗边）
x
2
x
3
x
4
x
5
x
1
y
2
y
3
y
4 y5
y
1
2 4 1 35
0 0 0 00
经一次增广路扩张后发现 G
l
无完美匹配,
S={x
1,
x
3
,x
4
},N(S)=T={y
2
,y
3
}。
x
2
x
3
x
4 x5
x
1
y
2
y
3
y
4
y
5
y
1
修改标号后，新的标号及其相等子图 G
l
。
G
l
比原相等子图增加了的 4 条边,x
1
y
4
,x
4
y
1
,
x
4
y
4
,x
4
y
5
。 粗边是当前 G
l
的一个完美匹配 。
1 1 0 00
x
2
x
3
x
4 x5
x
1
y
2
y
3
y
4 y5
y
1
2 3 0 34
14
Kuhn-Munkres 算法的正确性证明可参看 [7]，其计算复杂度为 O(n
3
)
[6]
。
二部图最大权匹配的其它算法 (如网络流方法 )可参看文献 [6],[13]或 [19]。
对于求一般赋权图中的最大权匹配,Edmonds
[20]
首先给出一个算法，其后 Gabow 和 Lawler
在
3
()O υ 时间内实现了该算法
[ 21,22 ]
。更快的算法已由 Gabow 和 Tarjan 给出
[ 23,24 ]
。
为了在高速骨干通信网络中设计高性能路由器调度算法，人们已经研究并提出了二部图最大匹配和最大权匹配的若干快速启发式算法。读者可参看文献 [25]~[33]。
设在一个完全二部图 K
n,n
= (X,Y)中,X 中每个点对 Y 中各点都有偏好值,Y 中每个点对 X
中各点也有偏好值。给定 K
n,n
一个匹配 M，如果存在 x X∈,y Y∈ 使得 x 对 y 的偏好值大于它对当前匹配点的偏好值,y 对 x 的偏好值也大于它对当前匹配点的偏好值，则称 M 是一个不稳定匹配，而称 (x,y)为一个不稳定对。如果一个完美匹配没有不稳定的未匹配对，则称为 稳定匹配 。
求一个完全二部图的稳定匹配有 O(n
2
)多项式时间算法，读者可参看文献 [7],[13],[34]、
[35]。稳定匹配的综述和新进展见 [35],[36]。稳定匹配在通信网络路由器调度算法中得到了很好的应用，读者可参看文献 [28]及 [37]~[40]。
参考文献 [41]是关于二部图匹配和指派问题的一个综述。有兴趣进一步了解关于匹配理论及其应用的读者，可参阅 [42]~[46]。
[19] R.E,Tarjan,Data structures and network algorithms,Society for Industrial and applied
mathematics,Pennsylvania,Nov,1983,
[20] J,Edmonds,Maximum matchings and a polyhedron with 0,1 vertices,J,Res,Nat,Bur,Standards,
69B(1965),125-130,
[21] H.N,Gabow,An efficient implementation of Edmonds’ algorithm for maximum matchings on
graph,J,Assoc,Comp,Math.,23(1975),221-234,
[22] E.L,Lawler,Combinatorial Optimization,Networks and Matroids,Holt,Rinehart,and Winston,
1976,
[23] H.N,Gabow,Data structures for weighted matching and nearest common ancestors with linking,
In Proc,1th ACM-SIAM Symp,Disc,Algs,SIAM,(1990),434-443,
[24] H.N,Gabow,and R.E,Tarjan,Faster scaling algorithms for general graph matching problems,
Tech,Rept,CU-CS- 432-89 Dept,Comp,Sci,Univ,Colorado-Boulder,1989,
[25] T,Anderson,S,Owicki,J,Saxe,and C,Thacker,High speed switch scheduling for local area
networks,ACM Trans,On Computer Systems,Nov.,(1993) 319-352,
[26] M,Ali,H,Nguyen,A neural network implementation of an input access scheme in a high-speed
packet switch,in Proc,of GLOBECOM 1989,1192-1196,
[27] Ge Nong,J.K Muppala,and M,Hamdi,Analysis of Nonblocking ATM switches with multiple
input queues,IEEE/ACM Transactions on Networking,7:1(1999) 60-74,
[28] N,Mckeown,Scheduling algorithms for input-queued cell switches,Ph.D Dissertation,
University of California at Berkley,May 1995,
[29] N,Mckeown,The iSLIP Scheduling algorithm for input-queued switches,IEEE/ACM
Transactions on Networking,7:2(1999)188-201,
[30] A,Mekkittikul,N,Mckeown,A practical scheduling algorithm to achieve 100% throughput in
15
input-queued switches,in Proc,IEEE INFOCOM’98,San Francisco,CA,Apr,(1998)792-799,
[31] N,Mckeown,V,Anantharam,and J,Walrand,Achieving 100% throughput in an input-queued
switch,in Proc,IEEE INFOCOM’96,San Francisco,Mar.,1(1996) 296-302
[32] D,Shah,M,Kopikare,Delay bounds for approximate maximum weight matching algorithms for
input queued switches,in Proc,IEEE INFOCOM 2002,(2002) 1-8
[33] P,Giaccone,B,Prabhakar,and D,Shah,Randomized scheduling algorithms for high-aggregate
bandwidth switches,IEEE Journal on Selected Areas in Communications,21(4)(2003),pp546-559,
[34] D.Gale,and L.S,Shapley,College admissions and the stability of marriage,American
Mathematical Monthly,69(1962),9-15,
[35] D,Gusfield,and R.W,Irving,The Stable Marriage Problem,Structure and Algorithms,MIT
Press,Cambridge,MA,1989,
[36] K,Cechlárová,and D,F,Manlov,The exchange-stable marriage problem,Discrete Applied
Mathematics,152(2005)109-122
[37] E,Leonardi,M,Mellia,F,Neri,and M.A,Marsan,On the stability of input-queued switches with
speed-up,IEEE/ACM Transactions on Networking,9:1(2001),104-118,
[38] S.T,Chuang,A,Goel,N,Mckeown,and B,Prabhakar,Matching output queueing with combined
input and output queueing,IEEE J,Selected Areas Communication,17(1999) 1030-1039,
[39] M,Ajmone Marsan,E,Leonardi,M,Mellia,and F,Neri,Stability of maximal size matching
scheduling in input-queued cell switches,in IEEE ICC,New Orleans,LA,June(2000)1758-1763,
[40] Ge Nong,and M,Hamdi,On the provision of integrated QoS guarantees of unicast and multicast
traffic in input-queued switches,in Proc,Global Telecommunications Conference-Globecom’99,
1742-1746,
[41] R,E,Burkard,Selected topics on assignment problems,Discrete Applied Mathematics,
123(2002)257-302,
[42] P.M,Vaidya,Approximate minimum weight matching on points in k-dimensional space,
Algorithmica,1990,
[43] P.M,Vaidya,Geometry helps in matching,SIAM Journal on Computing,18(1989) 1201-1225,
[44] A,Gibbons,Algorithmic Graph Theory,Cambridge University Press,1985,
[45] L,Lováze,and M,D,Plummer,Matching Theory,Annals of Discrete Mathematics,29(1986),
[46] A,Schrijver,Combinatorial Optimization Polyhedra and Efficiency,New York,NY,
Springer-Verlag,2003,
第三章习题
1,证明：一棵树最多只有一个完美匹配。
2,证明一棵树 T 有完美匹配当且仅当对 (),vVG? ∈ 奇分支数 o(T-v)=1。
3,两人在图 G 上做游戏：交替选择相异的顶点 null,,,
210
vvv,使得对每个
i
vi,0> 相邻于
1?i
v,
选择最后一个顶点者获胜。证明：第一个选点人有一个得胜策略当且仅当图 G 没有完美匹配。
16
4,设 M
1
,M
2
是简单图 G 的两个匹配,G′是
12
MM⊕ 在 G 中的边导出子图。证明 G′的每个连通分支必定是下列两种情况之一,
（ 1）边在 M
1
和 M
2
中交替出现的偶长度圈； （ 2）边在 M
1
和 M
2
中交替出现的路。
5,设 M 和 N 是图 G 中两个不相交的匹配，且 |M|>|N|。证明,G 中必存在两个不相交匹配 M′
和 N′，使得,M NMN′′=∪∪且 | |||1,||||1MM NM′ ′=?=+。
6,设 G=(X,Y)是一个二部图,U
1
,U
2
是 X 的两个子集,V
1
,V
2
是 Y 的两个子集。 M
1
是 G 中 U
1
与 V
1
间的一个匹配,M
2
是 G 中 U
2
与 V
2
间的一个匹配。证明：存在匹配
12
MM M? ∪,
它饱和 U
1
和 V
2
。
7,设 G=(X,Y)是一个二部图，利用上题的结论证明,（ 1） G 中存在一个匹配饱和 G 的所有最大度顶点； （ 2） G 的边集可划分成 (G)Δ 个匹配。
8,证明下图没有完美匹配。
9,设 G 是一个 3 正则图且 G 有一个包含所有顶点的圈，证明 G 是可 1－因子分解的。
10,证明：若 3 正则图有割边，则不能 1－因子分解。
11,证明奇数阶完全图 K
2n+1
是可 2－因子分解的，但偶数阶完全图 K
2n+1
不可 2－因子分解。
12,证明,每个无割边的 3 度正则图可分解为一个 1 因子和一个 2 因子的并。
13,证明：一个连通图是可 2－因子化的当且仅当它是偶数度正则的。利用此结论证明：偶数阶完全图可分解为一个 1 因子和 n?1 个 2 因子的并。
14,修改匈牙利算法使其适用于求二部图的最大匹配。
15,已知工人 x
1
,x
2
,x
3
,x
4
,x
5
做工作 y
1
,y
2
,y
3
,y
4
,y
5
的效率 w
ij
如下矩阵所示,
W=(
ij
w ) =
31241
50122
31550
13210
22143
5
4
3
2
1
54321
x
x
x
x
x
yyyyy
,
试给出一种工作效率最大的分配方案。
16,在某届大学毕业生招聘会上，有 n 个毕业生可选择 m 个单位（ mn≥ ） 。已知每个毕业生至少对 r 个单位有工作意向，而每个招聘单位至多看中了其中 r?1 个毕业生（ 1 rm≤≤）,并最终要从中录用一名。问最多有多少个单位可选择到一名看中的毕业生？
