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

《图论匈牙利算法与最优匹配算法精.ppt》由会员分享，可在线阅读，更多相关《图论匈牙利算法与最优匹配算法精.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论课件匈牙利算法与最优匹配算法1第1页，本讲稿共32页本次课主要内容本次课主要内容(一一)、匈牙利算法、匈牙利算法(二二)、最优匹配算法、最优匹配算法匈牙利算法与最优匹配算法匈牙利算法与最优匹配算法2第2页，本讲稿共32页 (一一)、匈牙利算法、匈牙利算法 1、偶图中寻找完美匹配、偶图中寻找完美匹配 (1)、问题、问题 设设G=(X,Y),|X|=|Y|,在在G中求一完美匹配中求一完美匹配M.(2)、基本思想、基本思想 从任一初始匹配从任一初始匹配M0出发，通过寻求一条出发，通过寻求一条M0可扩路可扩路P，令，令M1=M0E(P),得比得比M0更大的匹配更大的匹配M1(近似于迭代思想近似于迭

2、代思想)。(3)、M可扩扩路的寻找方法可扩扩路的寻找方法 1965年，年，Edmonds首先提出首先提出:用扎根于用扎根于M非饱和点非饱和点u的的M交错树的交错树的生长来求生长来求M可扩路。可扩路。3第3页，本讲稿共32页 定义定义1 设设G=(X,Y),M是是G的匹配，的匹配，u是是M非饱和点。称树非饱和点。称树H是是G的的扎根于点扎根于点u的的M交错树交错树,如果：如果：1)u V(T)；2)对任意对任意v V(T),(u,v)路是路是M交错路。交错路。x1x2x3x4y2y1y3y4G=(X,Y)x3x2x4y4y3y2扎根扎根 x3 的的M交错树交错树 扎根于扎根于M非饱和点非饱和点u

3、的的M交错树的生长讨论：交错树的生长讨论：4第4页，本讲稿共32页 假如扎根于假如扎根于M非饱和点非饱和点u的的M交错树为交错树为H,对于对于H,有两种情形：有两种情形：情形情形1 除点除点u外，外，H中所有点为中所有点为M饱和点，且在饱和点，且在M上配对；上配对；x4ux2y4y3y2扎根扎根 u 的的M交错树交错树Hx5 情形情形2 H包含除包含除u外的外的M非饱和点。非饱和点。x4ux2y4y3y2扎根扎根 u 的的M交错树交错树H5第5页，本讲稿共32页 对于情形对于情形1，令，令S=V(H)X,T=V(H)Y,显然：显然：1)若若N(S)=T,由于由于S-u中点与中点与T中点配对，所

4、以有：中点配对，所以有：|T|=|S|-1,于是有：于是有：|N(S)|=|S|-1|S|.由由Hall定理，定理，G中不存在完美中不存在完美匹配；匹配；2)若若 令令y N(S)T,且且x与与y邻接。因为邻接。因为H的所有点，除的所有点，除u外，均在外，均在M下配下配对。所以，或者对。所以，或者x=u，或者，或者x与与H的某一顶点配对，这样，有的某一顶点配对，这样，有 若若y为为M饱和的，设饱和的，设yz M,则加上顶点则加上顶点y及及z和边和边xy与与yz生长生长H，得，得到情形到情形1；6第6页，本讲稿共32页 若若y为为M非饱和的，加上顶点非饱和的，加上顶点y和边和边xy生长生长H，得

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

6、匹配。否则设 y N(S)T.7第7页，本讲稿共32页 (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=;x1x2x3x4x5y1y2y3y4y5G=(X,Y)8第8页，本讲稿共32页 (b)N(S)=y2,y3,N(S)T,取取y2 N(S)-T (c)y2为为M非饱和点，加上非饱和点，加

7、上y2和边和边x3y2生长树生长树H。此时，置。此时，置M=ME(P)=x1y1,x2y3,x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X,Y)9第9页，本讲稿共32页 (a)S=x4,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)-Tx4y2x310第10页，本讲稿共32页 (c)y3为为M饱和点，饱和点，x2

8、y3 M。此时，置。此时，置S=Sx2T=Ty3。(b)N(S)=y2,y3 T，取取y3 N(S)-Tx1x2x3x4x5y1y2y3y4y5G=(X,Y)(b)N(S)=y2,y3=T，所以，所以，G无完美匹配。无完美匹配。(5)、匈牙利算法复杂性分析、匈牙利算法复杂性分析11第11页，本讲稿共32页 1)、最多循环、最多循环|X|次可以找到完美匹配；次可以找到完美匹配；2)、初始匹配最多扩张、初始匹配最多扩张|X|次可以找到完美匹配；次可以找到完美匹配；3)、每次生长树的生长至多、每次生长树的生长至多2|X|-1次。次。所以，算法复杂性为所以，算法复杂性为O(|X|3),是好算法。是好算

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

10、算法：偶图中寻找最大匹配算法：设设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),转转(1).(1).(5)若若X-S=,停止；否则转停止；否则转(2).(2).13第13页，本讲稿共32页(二二)

11、、最优匹配算法、最优匹配算法 1、问题、问题 设设G=(X,Y)是边赋权完全偶图，且是边赋权完全偶图，且X=x1,x2,xnY=y1,y2,yn,wij=w(xiyj)。在。在G中求出一个具有最大权值的中求出一个具有最大权值的完美匹配。完美匹配。由于由于Kn,n有有n!个不同完美匹配，所以枚举计算量是个不同完美匹配，所以枚举计算量是n!。在匈牙利算法的基础上，在匈牙利算法的基础上，Kuhn（1955）与）与Munkres(1957)提出了上提出了上面问题的好算法。面问题的好算法。2、可行顶点标号与相等子图、可行顶点标号与相等子图14第14页，本讲稿共32页 定义定义2 设设G=(X,Y),若对

12、任意的若对任意的x X,y Y,有：有：称称 l 是赋权完全偶图是赋权完全偶图G的可行顶点标号。的可行顶点标号。对于任意的赋权完全偶图对于任意的赋权完全偶图G，均存在，均存在G的可行顶点标号。事的可行顶点标号。事实上，设：实上，设：则则 l 是是G的一个可行顶点标号。的一个可行顶点标号。15第15页，本讲稿共32页 定义定义3 设设 l 是赋权完全偶图是赋权完全偶图G=(X,Y的可行顶点标号，令：的可行顶点标号，令：称称Gl=G El为为G的对应于的对应于l 的相等子图。的相等子图。例如，设如下矩阵是赋权完全偶图例如，设如下矩阵是赋权完全偶图G的权值矩阵并注明了一的权值矩阵并注明了一种可行顶点

13、标号种可行顶点标号l0000054213x1x2x3x4x5y1y2y3y4y5G l=(X,Y)16第16页，本讲稿共32页 定理定理 设设 l 是赋权完全偶图是赋权完全偶图G=(X,Y的可行顶点标号，若相等子的可行顶点标号，若相等子图图Gl有完美匹配有完美匹配M*,则则M*是是G的最优匹配。的最优匹配。证明：设证明：设M*是是Gl的完美匹配，则：的完美匹配，则：又设又设M是是G的任一完美匹配，则：的任一完美匹配，则：所以，所以，w(M*)w(M)。即。即M*是是G的最的最优优匹配。匹配。17第17页，本讲稿共32页 根据上面定理，如果找到一种恰当可行顶点标号，使得对根据上面定理，如果找到一

14、种恰当可行顶点标号，使得对应的相等子图有完美匹配应的相等子图有完美匹配M*,则求出了则求出了G的最优匹配。的最优匹配。Kuhn采用顶点标号修改策略，找到了求最优匹配好算法，采用顶点标号修改策略，找到了求最优匹配好算法，介绍如下：介绍如下：给一初始顶点标号给一初始顶点标号l,在在Gl中任选一个匹配中任选一个匹配M。(1)若若X是是M饱和的，则饱和的，则M是最优匹配。否则，令是最优匹配。否则，令u是一个是一个M非非饱和点，置：饱和点，置：S=u,T=。(2)若若 ，转，转(3)。否则，计算：。否则，计算：18第18页，本讲稿共32页 给出新的可行顶点标号。给出新的可行顶点标号。(3)在在NGl(S

15、)-T中选择点中选择点y。若。若y是是M饱和的，饱和的，yz M,则置则置S=Sz,T=Ty转转(2)。否则，设。否则，设P是是Gl中中M可扩路，置可扩路，置M=ME(P),E(P),转转(1).(1).注：该算法把匈牙利算法用于其中，主要是用来判定和求完美匹注：该算法把匈牙利算法用于其中，主要是用来判定和求完美匹配。配。19第19页，本讲稿共32页 例例2，设如下矩阵是赋权完全偶图，设如下矩阵是赋权完全偶图G的权值矩阵，求出其最的权值矩阵，求出其最优匹配。优匹配。解：给出初始可行顶点标号解：给出初始可行顶点标号 l 为：为：000005421320第20页，本讲稿共32页 对应的相等子图对应

16、的相等子图Gl为：为：给出初始匹配给出初始匹配M为：为：x1x2x3x4x5y1y2y3y4y5G l=(X,Y)x1x2x3x4x5y1y2y3y4y5G l=(X,Y)21第21页，本讲稿共32页 (1)u=x4为为M非饱和顶点。置：非饱和顶点。置：x1x2x3x4x5y1y2y3y4y5G l=(X,Y)(2)(3)取：取：y2为饱和顶点，为饱和顶点，y2x1 M,于是：于是：(2)(3)取：取：y3为饱和顶点，为饱和顶点，y3x3 M,于是：于是：22第22页，本讲稿共32页x1x2x3x4x5y1y2y3y4y5G l=(X,Y)(2)于是修改标号：于是修改标号：由由 得新标号为：得

17、新标号为：0110043203x1x2x3x4x5y1y2y3y4y5G l=(X,Y)23第23页，本讲稿共32页 继续使用算法后得：继续使用算法后得：x1x2x3x4x5y1y2y3y4y5G l=(X,Y)最优匹配权值为最优匹配权值为14.例例3 证明：证明：K6n-2有一个有一个3因子分解。因子分解。证明：证明：K6n-2=K 2(3n-1),所以，可以分解为所以，可以分解为6n-3个边不重的个边不重的1因子因子之和。而任意之和。而任意3个个1因子可以并成一个因子可以并成一个3因子。所以，共可以并成因子。所以，共可以并成2n-1个个3因子。即因子。即K6n-2可以分解为可以分解为2n-

18、1个个3因子的和。因子的和。24第24页，本讲稿共32页 例例4 证明：对证明：对n1,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的左陪集。而的左陪

19、集。而Kh1,Kh2,Khn都是都是K的右陪集。的右陪集。注注:(1)上面结论是群论学家上面结论是群论学家Hall的一个结论。群论是近世代的一个结论。群论是近世代数的重要组成部分。在数学、计算机科学、理论物理学数的重要组成部分。在数学、计算机科学、理论物理学(量量子场论子场论)中都有重要应用。是数学领域里最引人关注的方向和主流研中都有重要应用。是数学领域里最引人关注的方向和主流研究方向之一。创立者伽罗瓦。究方向之一。创立者伽罗瓦。25第25页，本讲稿共32页 (2)伽罗瓦伽罗瓦(1811-1832)中学时受到数学老师里沙的影响中学时受到数学老师里沙的影响而对数学产生极大兴趣。里沙对教学工作十分

20、负责，且具有而对数学产生极大兴趣。里沙对教学工作十分负责，且具有很高数学才能，但把精力耗在了学生身上，欣慰的是培养了很高数学才能，但把精力耗在了学生身上，欣慰的是培养了好几位欧洲杰出数学家。中学时的伽罗瓦好几位欧洲杰出数学家。中学时的伽罗瓦 在里沙帮助下创在里沙帮助下创立了群论。群论是立了群论。群论是19世纪最突出的数学成就。有点象相对论在物世纪最突出的数学成就。有点象相对论在物理学中的地位。理学中的地位。在法国历史上著名的在法国历史上著名的1830年的年的“七月革命七月革命”中中，伽罗瓦两，伽罗瓦两次入狱，成为坚强斗士。次入狱，成为坚强斗士。1832年年5月，月，21岁的他因为反动派设岁的他

21、因为反动派设下的爱情圈套，被迫决斗至死。这是他犯下的草率的错误。下的爱情圈套，被迫决斗至死。这是他犯下的草率的错误。26第26页，本讲稿共32页 证明：由陪集的性质：证明：由陪集的性质：H中的任意两个左中的任意两个左(右右)陪集陪集,要么相等，要么相等，要么没有共同元素。所以要么没有共同元素。所以H可按某子群的左可按某子群的左(右右)陪集，划分为左陪集，划分为左(右右)陪集族。如果陪集族。如果K是是H的子群，则的子群，则aK或者或者Kb的元素个数等于的元素个数等于K中元素个数。中元素个数。设设|K|=k。且假。且假设设子群子群K在群在群H中的指数中的指数为为n。我。我们们构造偶构造偶图图G=(

22、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）。）。27第27页，本讲稿共32页 匹配在矩阵中的应用匹配在矩阵中的应用 1、矩阵与偶图、矩阵与偶图 设设A=(aij)是是n阶方

23、阵。构造偶图阶方阵。构造偶图G=(X,Y)如下：如下：X表示行集合，表示行集合，Y表示列集合。表示列集合。X中元素中元素xi与与Y中元素中元素yj连线，连线，当且仅当当且仅当aij0y1y2y3y4y5x1x3x2x4x5x1x2x3x4x5y1y2y3y4y5G w=(X,Y)28第28页，本讲稿共32页 2、下面研究、下面研究detA和和GA=(X,Y)之间关系之间关系 若若|S|=n,则则在在A中存在中存在n行，行，这这n行中至多有行中至多有n-1列元非零，而列元非零，而其余的其余的-n+1-n+1列中每个元素列中每个元素为为零。即得到零。即得到A A中有一个中有一个 零子零子阵阵。29第29页，本讲稿共32页 于是有如下定理：于是有如下定理：30第30页，本讲稿共32页 作业作业 P117-118 习题习题4：1331第31页，本讲稿共32页Thank You!32第32页，本讲稿共32页