图论课件匈牙利算法与最优匹配算法.ppt

1、 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 1本次课主要内容本次课主要内容(一一)、匈牙利算法、匈牙利算法(二二)、最优匹配算法、最优匹配算法匈牙利算法与最优匹配算法匈牙利算法与最优匹配算法 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 2 (一一)、匈牙利算法、匈牙利算法 1、偶图中寻找完美匹配、偶图中寻找完美匹配 (1) 、问题、问题 设设G=(X, Y), |X|=|Y|, 在在G中求一完美匹配中求一完美匹配M. (2) 、基本思想、基本思想 从任一初始匹配从任

2、一初始匹配M0出发，通过寻求一条出发，通过寻求一条M0可扩路可扩路P，令，令M1=M0E(P), 得比得比M0更大的匹配更大的匹配M1(近似于迭代思想近似于迭代思想)。 (3) 、M可扩扩路的寻找方法可扩扩路的寻找方法 1965年，年，Edmonds首先提出首先提出: 用扎根于用扎根于M非饱和点非饱和点u的的M交错树的生长来求交错树的生长来求M可扩路。可扩路。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 3 定义定义1 设设G=(X, Y), M是是G的匹配，的匹配，u是是M非饱和点。称非饱和点。称树树H是是G的扎根于点的扎根于点

3、u的的M交错树交错树,如果：如果： 1) u V(T)； 2) 对任意对任意v V(T), (u, v)路是路是M交错路。交错路。x1x2x3x4y2y1y3y4G=(X, Y)x3x2x4y4y3y2扎根扎根 x3 的的M交错树交错树 扎根于扎根于M非饱和点非饱和点u的的M交错树的生长讨论：交错树的生长讨论： 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 4 假如扎根于假如扎根于M非饱和点非饱和点u的的M交错树为交错树为H,对于对于H,有两种有两种情形：情形： 情形情形1 除点除点u外，外，H中所有点为中所有点为M饱和点，且在饱和

4、点，且在M上配对；上配对；x4ux2y4y3y2扎根扎根 u 的的M交错树交错树Hx5 情形情形2 H包含除包含除u外的外的M非饱和点。非饱和点。x4ux2y4y3y2扎根扎根 u 的的M交错树交错树H 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 5 对于情形对于情形1，令，令S=V(H)X, T=V(H)Y,显然：显然： 1) 若若N(S)=T, 由于由于S - u中点与中点与T中点配对，所以有：中点配对，所以有：( )TN S |T|=|S|-1, 于是有：于是有： |N(S)| = |S|-1 |S|.由由Hall定理，定理

5、，G中不存中不存在完美匹配；在完美匹配； 2) 若若( )TN S 令令y N(S) T, 且且x与与y邻接。因为邻接。因为H的所有点，除的所有点，除u外，均外，均在在M下配对。所以，或者下配对。所以，或者x=u，或者，或者x与与H的某一顶点配对，的某一顶点配对，这样，有这样，有xyM 若若y为为M饱和的，设饱和的，设yz M,则加上顶点则加上顶点y及及z和边和边xy与与yz生生长长H，得到情形，得到情形1； 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 6 若若y为为M非饱和的，加上顶点非饱和的，加上顶点y和边和边xy生长生长H，

6、得到情形，得到情形2. 找到一条找到一条M可扩路，可以对匹配进行一次修改，过程的反可扩路，可以对匹配进行一次修改，过程的反复进行，最终判定复进行，最终判定G是否有完美匹配或者求出完美匹配。是否有完美匹配或者求出完美匹配。 根据上面讨论，可以设计求偶图的完美匹配算法。根据上面讨论，可以设计求偶图的完美匹配算法。 (4) 、偶图完美匹配算法、偶图完美匹配算法匈牙利算法。匈牙利算法。 设设M是初始匹配。是初始匹配。 (a) 、若、若M饱和饱和X所有顶点，停止。否则，设所有顶点，停止。否则，设u为为X中中M非饱和顶点，置非饱和顶点，置S=u,T=; ; (b) 、若、若N(S)=T, 则则G中不存在完

7、美匹配。否则设中不存在完美匹配。否则设 y N(S) T. 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 7 (c ) 若若y为为M饱和点，且饱和点，且yz M, 置置S=Sz, T=Ty,转转(b)。否则，设。否则，设P为为M可扩路，置可扩路，置M1=ME(P)，转，转(a). 例例1 讨论下图讨论下图G=(X, Y)是否有完美匹配。是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X, Y) 解：取初始匹配解：取初始匹配 M=x1y2, x2y3。 (a) S=x3,T=; ;x1x2x3x4x5y1y2y3y4y5

8、G=(X, Y) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 (b ) N(S)= y2, y3,N(S)T, 取取y2 N(S)-T (c) y2为为M非饱和点，加上非饱和点，加上y2和边和边x3y2生长树生长树H。此时，。此时，置置M=ME(P)=x1y1, x2y3, x3y2x1x2x3x4x5y1y2y3y4y5G=(X, Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X, Y) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 9 (a) S=x

9、4,T=; ;x1x2x3x4x5y1y2y3y4y5G=(X, Y) (b ) N(S)= y2, y3,N(S)T, 取取y2 N(S)-T (c) y2为为M饱和点，饱和点，y2x3 M。此时，置。此时，置S=Sx3T=Ty2。 (b ) N(S)= y2, y3 T，取取y3 N(S)-Tx4y2x3 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 10 (c) y3为为M饱和点，饱和点，x2y3 M。此时，置。此时，置S=Sx2T=Ty3。 (b ) N(S)= y2, y3 T，取取y3 N(S)-Tx1x2x3x4x5y

10、1y2y3y4y5G=(X, Y) (b ) N(S)= y2, y3 =T，所以，所以，G无完美匹配。无完美匹配。 (5) 、匈牙利算法复杂性分析、匈牙利算法复杂性分析 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 11 1) 、最多循环、最多循环|X|次可以找到完美匹配；次可以找到完美匹配； 2) 、初始匹配最多扩张、初始匹配最多扩张|X|次可以找到完美匹配；次可以找到完美匹配； 3) 、每次生长树的生长至多、每次生长树的生长至多2|X|-1次。次。 所以，算法复杂性为所以，算法复杂性为O(|X|3),是好算法。是好算法。 2、

11、偶图中寻找最大匹配、偶图中寻找最大匹配 问题问题：在一般偶图上求最大匹配：在一般偶图上求最大匹配M. 分析：使用匈牙利算法求完美匹配时，当在扎根于分析：使用匈牙利算法求完美匹配时，当在扎根于M非饱和点非饱和点u的交错树上有的交错树上有|N(S)|S|时，由时，由Hall定理，算法定理，算法停止。要求出最大匹配，应该继续检查停止。要求出最大匹配，应该继续检查X-S是否为空，如是否为空，如果不为空，则检查是否在其上有果不为空，则检查是否在其上有M非饱和点。一直到所非饱和点。一直到所有有M非饱和点均没有非饱和点均没有M可扩路才停止。可扩路才停止。 0.8 1 0.6 0.4 0.2 0 x t 0

12、0.5 1 1.5 2 1 0.5 0 0.5 1 n 12 偶图中寻找最大匹配算法：偶图中寻找最大匹配算法： 设设M是是G=(X, Y)的初始匹配。的初始匹配。 (1) 置置S=, T=, T=; ; (2) 若若X-S已经已经M饱和，停止；否则，设饱和，停止；否则，设u是是X-S中的一中的一非饱和顶点，置非饱和顶点，置S=Su。 (3) 若若N(S)=T,转转(5)；否则，设；否则，设y N(S)-T。 (4) 若若y是是M饱和的，设饱和的，设yz M,置置S=Sz, T=Ty,转转(3);否则，存在否则，存在(u, y)交错路是交错路是M可扩路可扩路P,置置M=ME(P),E(P),转转

13、(1).(1). (5) 若若X-S=, ,停止；否则转停止；否则转(2).(2). 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 13(二二)、最优匹配算法、最优匹配算法 1 、问题、问题 设设G=(X, Y)是边赋权完全偶图，且是边赋权完全偶图，且X=x1, x2,xnY=y1, y2,yn, wij=w(xiyj)。在。在G中求出一个具有最大中求出一个具有最大权值的完美匹配。权值的完美匹配。 由于由于Kn,n有有n!个不同完美匹配，所以枚举计算量是个不同完美匹配，所以枚举计算量是n!。 在匈牙利算法的基础上，在匈牙利算法的基础

14、上，Kuhn（1955）与）与Munkres(1957)提提出了上面问题的好算法。出了上面问题的好算法。 2 、可行顶点标号与相等子图、可行顶点标号与相等子图 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 14 定义定义2 设设G=(X, Y), 若对任意的若对任意的x X, y Y,有：有：( )( )()l xl yw xy 称称 l 是赋权完全偶图是赋权完全偶图G的可行顶点标号。的可行顶点标号。 对于任意的赋权完全偶图对于任意的赋权完全偶图G，均存在，均存在G的可行顶点标号。的可行顶点标号。事实上，设：事实上，设：( )max

15、(),( )0,.y Yl xw xyxXl yyY若若 则则 l 是是G的一个可行顶点标号。的一个可行顶点标号。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 15 定义定义3 设设 l 是赋权完全偶图是赋权完全偶图G=(X, Y的可行顶点标号，的可行顶点标号，令：令： 称称Gl = G El为为G的对应于的对应于l 的相等子图。的相等子图。() ( )( )()lExyE G l xl yw xy 例如，设如下矩阵是赋权完全偶图例如，设如下矩阵是赋权完全偶图G的权值矩阵并注的权值矩阵并注明了一种可行顶点标号明了一种可行顶点标号l

16、3554122022244100110012133W0000054213x1x2x3x4x5y1y2y3y4y5G l=(X, Y) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 16 定理定理 设设 l 是赋权完全偶图是赋权完全偶图G=(X, Y的可行顶点标号，的可行顶点标号，若相等子图若相等子图Gl有完美匹配有完美匹配M*,则则M*是是G的最优匹配。的最优匹配。 证明：设证明：设M*是是Gl的完美匹配，则：的完美匹配，则：*()(*)( )( )e Mv V Gw Mw el v 又设又设M是是G的任一完美匹配，则：的任一完美匹

17、配，则：()()( )( )e Mv V Gw Mw el v 所以，所以，w (M*)w (M)。即。即M*是是G的最优匹配。的最优匹配。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 17 根据上面定理，如果找到一种恰当可行顶点标号，使得根据上面定理，如果找到一种恰当可行顶点标号，使得对应的相等子图有完美匹配对应的相等子图有完美匹配M*,则求出了则求出了G的最优匹配。的最优匹配。 Kuhn采用顶点标号修改策略，找到了求最优匹配好算采用顶点标号修改策略，找到了求最优匹配好算法，介绍如下：法，介绍如下： 给一初始顶点标号给一初始顶点

18、标号l ,在在Gl中任选一个匹配中任选一个匹配M。 (1) 若若X是是M饱和的，则饱和的，则M是最优匹配。否则，令是最优匹配。否则，令u是是一个一个M非饱和点，置：非饱和点，置：S=u,T=。 (2) 若若 ，转，转(3)。否则，计算：。否则，计算：( )lGNSTmin( )( )()lx Sy Tl xl yw xy 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 18 给出新的可行顶点标号。给出新的可行顶点标号。( ),( ),( ),lll vvSll vvTl v其 它 (3) 在在NGl (S)-T中选择点中选择点y。若。

19、若y是是M饱和的，饱和的，yz M,则置则置S=Sz,T=Ty转转(2)。否则，设。否则，设P是是Gl中中M可扩路，置可扩路，置M=ME(P),E(P),转转(1).(1). 注：该算法把匈牙利算法用于其中，主要是用来判定注：该算法把匈牙利算法用于其中，主要是用来判定和求完美匹配。和求完美匹配。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 19 例例2，设如下矩阵是赋权完全偶图，设如下矩阵是赋权完全偶图G的权值矩阵，求出的权值矩阵，求出其最优匹配。其最优匹配。3554122022244100110012133W 解：给出初始可行顶

20、点标号解：给出初始可行顶点标号 l 为：为：3554122022244100110012133W0000054213 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 20 对应的相等子图对应的相等子图Gl为：为： 给出初始匹配给出初始匹配M为：为：x1x2x3x4x5y1y2y3y4y5G l=(X, Y)x1x2x3x4x5y1y2y3y4y5G l=(X, Y) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 21 (1) u=x4为为M非饱和顶点。置：非饱和顶点。置：x

21、1x2x3x4x5y1y2y3y4y5G l=(X, Y)4,SxT (2)23( ),lGNSyyT (3) 取：取：2( )lGyNST y2为饱和顶点，为饱和顶点，y2x1 M,于是：于是：142,Sx xTy (2) 23( ),lGNSyyT (3) 取：取：3( )lGyNST y3为饱和顶点，为饱和顶点，y3x3 M,于是：于是：13423,Sx xxTyy 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 22x1x2x3x4x5y1y2y3y4y5G l=(X, Y) (2) 23( ),lGNSyyT 于是修改标号：

22、于是修改标号：min( )( )()1lx Sy Tl xl yw xy 由由 得新标号为：得新标号为： ( ),( ),( ),lll vvSll vvTl v其 它3554122022244100110012133W0110043203x1x2x3x4x5y1y2y3y4y5G l=(X, Y) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 23 继续使用算法后得：继续使用算法后得：x1x2x3x4x5y1y2y3y4y5G l=(X, Y) 最优匹配权值为最优匹配权值为14. 例例3 证明：证明：K6n-2有一个有一个3因子分

23、解。因子分解。 证明：证明：K6n-2= K 2(3n-1) , 所以，可以分解为所以，可以分解为6n-3个边不重个边不重的的1因子之和。而任意因子之和。而任意3个个1因子可以并成一个因子可以并成一个3因子。所因子。所以，共可以并成以，共可以并成2n-1个个3因子。即因子。即K6n-2可以分解为可以分解为2n-1个个3因子的和。因子的和。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 24 例例4 证明：对证明：对n1,K4n+1有一个有一个4因子分解。因子分解。 证明：证明：K4n+1= K 2(2n)+1 , 所以，可以分解为所

24、以，可以分解为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的一个结论。群论是的一个结论。群论是近世代数的重要组成部分

25、。在数学、计算机科学、理论近世代数的重要组成部分。在数学、计算机科学、理论物理学物理学(量子场论量子场论)中都有重要应用。是数学领域里最引人中都有重要应用。是数学领域里最引人关注的方向和主流研究方向之一。创立者伽罗瓦。关注的方向和主流研究方向之一。创立者伽罗瓦。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 25 (2) 伽罗瓦伽罗瓦 (1811 -1832) 中学时受到数学老师里沙的中学时受到数学老师里沙的影响而对数学产生极大兴趣。里沙对教学工作十分负责，影响而对数学产生极大兴趣。里沙对教学工作十分负责，且具有很高数学才能，但把精

26、力耗在了学生身上，欣慰且具有很高数学才能，但把精力耗在了学生身上，欣慰的是培养了好几位欧洲杰出数学家。中学时的伽罗瓦的是培养了好几位欧洲杰出数学家。中学时的伽罗瓦 在在里沙帮助下创立了群论。群论是里沙帮助下创立了群论。群论是19世纪最突出的数学成世纪最突出的数学成就。有点象相对论在物理学中的地位。就。有点象相对论在物理学中的地位。 在法国历史上著名的在法国历史上著名的1830年的年的“七月革命七月革命”中中 ，伽，伽罗瓦两次入狱，成为坚强斗士。罗瓦两次入狱，成为坚强斗士。1832年年5月，月，21岁的岁的他因为反动派设下的爱情圈套，被迫决斗至死。这是他因为反动派设下的爱情圈套，被迫决斗至死。这

27、是他犯下的草率的错误。他犯下的草率的错误。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 26 证明：由陪集的性质：证明：由陪集的性质：H中的任意两个左中的任意两个左(右右)陪集陪集,要要么相等，要么没有共同元素。所以么相等，要么没有共同元素。所以H可按某子群的左可按某子群的左(右右)陪集，划分为左陪集，划分为左(右右)陪集族。如果陪集族。如果K是是H的子群，则的子群，则aK或或者者Kb的元素个数等于的元素个数等于K中元素个数。中元素个数。 设设|K|=k。且假设子群。且假设子群K在群在群H中的指数为中的指数为n。我们构造。我们构造

28、偶图偶图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, 则这则这些元素为所求。些元素为所求。(1inin）。）。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0

29、.5 1 n 27 匹配在矩阵中的应用匹配在矩阵中的应用 1、矩阵与偶图、矩阵与偶图 设设A=(aij)是是n阶方阵。构造偶图阶方阵。构造偶图G=(X, Y)如下：如下： X表示行集合，表示行集合，Y表示列集合。表示列集合。X中元素中元素xi与与Y中元素中元素yj连线，当且仅当连线，当且仅当aij02010100400003701105600080Wy1y2y3y4y5x1x3x2x4x5x1x2x3x4x5y1y2y3y4y5G w=(X, Y) 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 28 2、下面研究、下面研究detA和

30、和GA=(X, Y)之间关系之间关系1 2211 2(.)12(),det( 1)j jjijjjjj jjAaAa aa 则211201(1)jjjAa aaGSSS 中无完美匹配SX,使得：N(S)有一个阶零矩阵。 若若|S|=n, 则在则在A中存在中存在n行，这行，这n行中至多有行中至多有n-1列元非列元非零，而其余的零，而其余的-n+1-n+1列中每个元素为零。即得到列中每个元素为零。即得到A A中有一中有一个个 零子阵。零子阵。(1)nn 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 29 于是有如下定理：于是有如下定理：(),det,ijAaAn 设则展开式中每项为零使得A中有一个n ( -n+1)阶零子阵。 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 30 作业作业 P117-118 习题习题4 ： 13 0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 31Thank You !