ppt19匈牙利算法与最优匹配算法
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
图论及其应用
任课教师：杨春 Email: [email protected] 数学科学学院
1
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
本次课主要内容
匈牙利算法与最优匹配算法 (一)、匈牙利算法 (二)、最优匹配算法
2
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
(一)、匈牙利算法
1、偶图中寻找完美匹配
(1) 、问题 设G=(X, Y), |X|=|Y|, 在G中求一完美匹配M. (2) 、基本思想 从任一初始匹配M0出发，通过寻求一条M0可扩路P，令 M1=M0ΔE(P), 得到比M0更大的匹配M1(近似于迭代思想)。 (3) 、M可扩扩路的寻找方法 1965年，Edmonds首先提出: 用扎根于M非饱和点u的M 交错树的生长来求M可扩路。
3
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
定义1 设G=(X, Y), M是G的匹配，u是M非饱和点。称 树H是G的扎根于点u的M交错树,如果： 1) u ∈V(H)；
x1 x2 x3
2) 对任意v ∈V(H), (u, v)路是M交错路。
x4 y2 x4 y4 x2 y3 x3 扎根 x3 的M交错树
y1
y2
y3
y4
G=(X, Y)
扎根于M非饱和点u的M交错树的生长讨论：
4
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
假如扎根于M非饱和点u的M交错树为H。它有两种情形： 情形1 除点u外，H中所有点为M饱和点，且在M上配对；
y2 x4 y4 u 扎根 u 的M交错树H x5 x2 y3 y2 x4 y4 u 扎根 u 的M交错树H x2 y3
情形2 H包含除u外的M非饱和点。 对于情形1，令S=V(H)∩X, T=V(H)∩Y,显然： T N (S ) 1) 若N(S)=T, 由于S - ｛u｝中点与T中点配对，所以有： |T|=|S|-1, 于是有： |N(S)| = |S|-1
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
2) 若 T N (S ) 令y ∈N(S) – T, 则在树H中存在点x与y邻接。因为H的所有 点，除u外，均在M下配对。所以，或者x = u，或者x与H的某 xy M 一顶点配对，但无论哪种情况，都有
y2 y x y4 u 扎根 u 的M交错树H y3 x5 x2 y x y4 u 扎根 u 的M交错树H y3 y2 x5 x2
当然，y可能为M饱和点，也可能为M非饱和点。
6
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
若y为M饱和点，可设yz ∈M,则加上顶点y及z和边xy与yz生 长H，得到情形1；
y2 y x z y4 u 扎根 u 的M交错树H y3 x5 x2
若y为M非饱和点，加上顶点y和边xy生长H，得到情形2.
y2 y x y4 u 扎根 u 的M交错树H 7 y3 x5 x2
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
后一情况下找到一条M可扩路，可以对匹配进行一次修 改，过程的反复进行，最终判定G是否有完美匹配或者求出完 美匹配。 根据上面讨论，可设计求偶图的完美匹配算法。 (4) 、偶图完美匹配算法——匈牙利算法。 设M是初始匹配。H是扎根于M非饱和点u的交错树。 令：S=V(H)∩X, T=V(H)∩Y。 (a) 、若M饱和X所有顶点，停止。否则，
设u为X中M 非饱和顶点，置S=｛u｝,T=Φ; (b) 、若N(S)=T, 则G中不存在完美匹配。否则设 y ∈N(S) – T. (c ) 若y为M饱和点，且y z ∈M, 置S=S∪｛z｝, T=T∪｛y｝, 转(b)。否则，设P为M可扩路，置M1=MΔE(P)，转(a).
8
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
例1 讨论下图G=(X, Y)是否有完美匹配。
x1 x2 x3 x4 x5
y1
y2
y3 G=(X, Y)
y4
y5
解：取初始匹配 M=｛x1y2, x2y3｝。 (a) S=｛x3｝,T=Φ;
x1
x2
x3
x4
x5
y1
y2
y3 G=(X, Y)
y4
y5
9
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
(b ) N(S)= ｛y2, y3｝,N(S)≠T, 取y2 ∈N(S)-T
x1 x2 x3 x4 x5
y1
y2
y3 G=(X, Y)
y4
y5
(c) y2为M非饱和点，加上y2和边x3y2生长树H。此 时，置M=MΔE(P)=｛x1y1, x2y3, x3y2｝
x1 y2 x2 x3 x4 x5
x3
y1
y2
y3 G=(X, Y)
y4
y5 10
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
x1
x2
x3
x4
x5
y1
y2
y3 G=(X, Y)
y4
y5
(a) S=｛x4｝,T=Φ; (b ) N(S)= ｛y2, y3｝,N(S)≠T, 取y2 ∈N(S)-T (c) y2为M饱和点，y2x3 ∈ M。此时，置S=S∪｛x3｝ T=T∪｛y2｝。
x3 y2 x4
(b ) N(S)= ｛y2, y3｝ ≠T，取y3 ∈N(S)-T
11
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
x1
x2
x3
x4
x5
(b ) N(S)= ｛y2, y3｝ ≠T，取y3 ∈N(S)-T
y1 y2 y3 G=(X, Y) y4 y5
(c) y3为M饱和点，x2y3 ∈ M。此时，置S=S∪｛x2｝ T=T∪｛y3｝。 (b ) N(S)= ｛y2, y3｝ =T，所以，G无完美匹配。 (5) 、匈牙利算法复杂性分析
12
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
1) 、最多循环|X|次可以找到完美匹配； 2) 、初始匹配最多扩张|X|次可以找到完美匹配； 3) 、每次生长树的生长至多2|X|-1次。 所以，算法复杂性为O(|X|3),是好算法。
2、偶图中寻找最大匹配
问题：在一般偶图上求最大匹配M. 分析：使用匈牙利算法求完美匹配时，当在扎根于M 非饱和点u的交错树上有|N(S)|
13
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
偶图中寻找最大匹配算法：
设M是G=(X, Y)的初始匹配。 (1) 置S=Φ, T=Φ; (2) 若X-S已经M饱和，停止；否则，设u是X-S中的一 非饱和顶点，置S=S∪｛u｝。 (3) 若N(S)=T,转(5)；否则，设y ∈N(S)-T。 (4) 若y是M饱和的，设yz ∈ M,置S=S∪｛z｝, T=T∪ ｛y｝,转(3);否则，存在(u, y)交错路是M可扩路P,置M=M ΔE(P),转(1). (5) 若X-S=Φ,停止；否则转(2).
14
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
(二)、最优匹配算法
1 、问题 设G=(X, Y)是边赋权完全偶图，且X=｛x1, x2,…,xn｝ Y=｛y1, y2,…,yn｝, wij=w(xiyj)。在G中求出一个具有最大 权值的完美匹配。 由于Kn,n有n!个不同完美匹配，所以枚举计
算量是n!。 在匈牙利算法的基础上，Kuhn（1955）与Munkres(1957)提 出了上面问题的好算法。 2 、可行顶点标号与相等子图
15
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
定义2 设G=(X, Y), 若对任意的x ∈X, y ∈Y,有：
l ( x ) l ( y ) w ( xy )
称 l 是赋权完全偶图G的可行顶点标号。 对于任意的赋权完全偶图G，均存在G的可行顶点标号。 事实上，设：
w ( xy ), 若 x X , l ( x ) max yY l ( y ) 0, 若 y Y .
则 l 是G的一个可行顶点标号。
16
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
定义3 设 l 是赋权完全偶图G=(X, Y)的可行顶点标号，令：
El xy E (G ) l ( x ) l ( y ) w ( xy )
称Gl = G [El]为G的对应于l 的相等子图。 例如，设如下矩阵是赋权完全偶图G的权值矩阵并注 明了一种可行顶点标号l。
3 2 W 2 0 1
0
5 2 4 1 2
0
5 0 4 1 1
0
4 2 1 0 3
0
1 2 0 0 3
0
5 x1 2 4 1 3 y1 y2 y3 G l=(X, Y) y4 y5 x2 x3 x4 x5
17
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
定理 设 l 是赋权完全偶图G=(X, Y)的可行顶点标号， 若相等子图Gl有完美匹配M*,则M*是G的最优匹配。 证明：设M*是Gl的完美匹配，则：
w ( M *)
eM *
w(e)
vV ( G )
l (v )
又设M是G的任一完美匹配，则：
w( M )
eM
w(e)
l (v )
vV ( G )
所以，w (M*)≥w (M)。即M*是G的最优匹配。
18
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
根据上面定理，如果找到一种恰当可行顶点标号，使得 对应的相等子图有完美匹配M*,则求出了G的最优匹配。 Kuhn采用顶点标号修改策略，找到了求最优匹配好算 法，介绍如下： 给一初始顶点标号l ,在Gl中任选一个匹配M。 (1) 若X是M饱和的，则M是最优匹配。否则，令u是一 个M非饱和点，置：S=｛u｝,T=Φ。 (2) 若 N G ( S ) T ，转(3)。否则，计算：
l
l min l ( x ) l ( y ) w ( xy )
xS yT
19
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
l (v ) l , v S lˆ l ( v ) l , v T l ( v ), 其 它
给出新的可行顶点标号，在新标号下重新开始。 (3) 在NGl (S)-T中选择点y。若y是M饱和的，yz ∈M, 则置S=S∪｛z｝,T=T∪｛y｝转(2)。否则，设P是Gl中M 可扩路，置M=MΔE(P),转(1). 注：该算法把匈牙利算法用于其中，主要是用来判定 和求完美匹配。
20
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
例2，设如下矩阵是赋权完全偶图G的权值矩阵，求出 其最优匹配。
3 5 5 4 1 2 2 0 2 2 W 2 4 4 1 0 0 1 1 0 0 1 2 1 3 3
解：给出初始可行顶点标号 l 为：
3 5 5 4 1 2 2
0 2 2 W 2 4 4 1 0 0 1 1 0 0 1 2 1 3 3
0 0 0 0 0 21 5 2 4 1 3
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
对应的相等子图Gl为：
x1 x2 x3 x4 x5
y1
y2
y3 G l=(X, Y)
y4
y5
给出初始匹配M为：
x1 x2 x3 x4 x5
y1
y2
y3 G l=(X, Y)
y4
y5
22
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
(1) u=x4为M非饱和顶点。置：
S x4 , T
x1
x2
x3
x4
x5
(2) N G ( S ) y 2 , y3 T
l
y1
y2
y3 G l=(X, Y)
y4
y5
y2 N G ( S ) T (3) 取：
l
y2为饱和顶点，y2x1 ∈M,于是： S x1 , x4 , T y 2 (2) N G ( S ) y 2 , y3 T
l
(3) 取： y3 N G ( S ) T
l
y3为饱和顶点，y3x3 ∈M,于是：S x1 , x3 , x4 , T y 2 , y3
23
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
(2) N G ( S ) y 2 , y3 T
l
x1
x2
x3
x4
x5
于是修改标号：
l min l ( x ) l ( y ) w ( xy ) 1
xS yT
y1
y2
y3 G l=(X, Y)
y4
y5
由
l (v ) l , v S lˆ l ( v ) l , v T l ( v ), 其 它
4 2 3 0 3
得新标号为：
3 5 5 4 1 2 2 0 2 2 W 2 4 4 1 0 0 1 1 0 0 1 2 1 3 3
0 1 1 0 0
x1
x2
x3
x4
x5
y1
y2
y3 G l=(X, Y)
y4
y5
24
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
继续使用算法后得：
x1 x2 x3 x4 x5
y1
y2
y3 G l=(X, Y)
y4
y5
最优匹配权值为14. 例3 证明：K6n-2有一个3因子分解。 证明：K6n-2= K 2(3n-1) , 所以，可以分解为6n-3个边不重 的1因子之和。而任意3个1因子可以并成一个3因子。所 以，共可以并成2n-1个3因子。即K6n-2可以分解为2n-1个3 因子的和。
25
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
例4 证明：对n≥1,K4n+1有一个4因子分解。 证明：K4n+1= K 2(2n)+1 , 所以，可以分解为2n个边不重 的2因子之和。而任意2个2因子可以并成一个4因子。所 以，共可以并成n个4因子。即K4n+1可以分解为n个4因子 的和。 例5 设H是有限群，K是H的子群。证明：存在元素 h1,h2,…,hn ∈H,使得h1K, h2K, …, hnK都是K的左陪集。而 Kh1, Kh2, …, Khn都是K的右陪集。 注: (1)上面结论是群论学家Hall的一个结论。群论是近 世代数的重要组成部分。在数学、计算机科学、理论物 理学(量子场论)中都有重要应用。是数学领域里最引人关 注的方向和主流研究方向之一。创立者伽罗瓦。
26
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
(2) 伽罗瓦 (1811 ---1832) 中学时受到数学老师里沙的影 响而对数学产生极大兴趣。里沙对教学工作十分负责，且 具有很高数学才能，但把精力耗在了学生身上，欣慰的是 培养了好几位欧洲杰出数学家。中学时的伽罗瓦 在里沙帮
助下创立了群论。群论是19世纪最突出的数学成就。 在法国历史上著名的1830年的“七月革命”中 ，伽罗瓦两 次入狱，成为坚强斗士。1832年5月，21岁的他因为反动 派设下的爱情圈套，被迫决斗至死。这是他犯下的草率的 错误。
27
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
证明：由陪集的性质：H中的任意两个左(右)陪集,要 么相等，要么没有共同元素。所以H可按某子群的左(右) 陪集，划分为左(右)陪集族。如果K是H的子群，则aK或 者Kb的元素个数等于K中元素个数。 设|K|=k。且假设子群K在群H中的指数为n。我们构造 偶图G=(X, Y)如下： X表示H关于K的左陪集族，Y表示H关于K的右陪集族。 对于x ∈X, y ∈Y, x与y间连接 l 条边，当且仅当左陪集x 和右陪集y有l个共同元素。 显然G是k正则偶图，于是存在完美匹配M。 |M|=n 在M中的边ei的两端点的陪集中选取共同元素hi, 则这 些元素为所求。(1≦i≦n）。
28
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
匹配在矩阵中的应用
1、矩阵与偶图 设A=(aij)是n阶方阵。构造偶图G=(X, Y)如下： X表示行集合，Y表示列集合。X中元素xi与Y中元素yj 连线，当且仅当aij≠0
2 0 W 0 1 0
y1
0 0 0 1 0
1
0
4 0 3 7 0 5 0 8
1 0 0 6 0
x1 x2 x3 x4 x5
x1
x2
x3
x4
x5
y1
y2
y3 G w=(X, Y)
y4
y5
y2 y3
y4 y5
29
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
2、下面研究detA和GA=(X, Y)之间关系
A (aij ) , 则det A
j1 j2 j
(1) ( j1 j2 ... j ) a1 j a2 j2 a j
1
对所有的a1 j a2 j2 a j 0 GA中无完美匹配 S X,使得：
1
N(S) S 1 有一个 S ( S 1)阶零矩阵。
若|S|=n, 则在A中存在n行，这n行中至多有n-1列元非 零，而其余的ν-n+1列中每个元素为零。即得到A中有一 个 n ( n 1) 零子阵。
30
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
于是有如下定理：
设A (aij ) , 则 det A展开式中每项为零 n, 使得 A中有一个n ( -n+1)阶零子阵。
31
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
作业
P117---118 习题4 ： 13
32
1 0.5 n 0 0.5 1 2 1.5 t 1 0.5 0 0 0.2 0.4 x 0.6 0.8 1
Thank You !
33