《图论最优匹配》PPT课件.ppt

《《图论最优匹配》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图论最优匹配》PPT课件.ppt（32页珍藏版）》请在三一办公上搜索。

1、,（或対集 Matching),定义3 若匹配M的某条边与点v关联,则称M饱和点v,并且称v是M的饱和点,否则称v是M的非饱和点.,定义4 设M是图G的一个匹配,如果G的每一个点都是M的饱和点,则称M是完美匹配；如果G中没有另外的匹配M0,使|M0|M|,则称M是最大匹配.,每个完美匹配都是最大匹配,反之不一定成立.,例16：判断下图的匹配,最大匹配非完美匹配,完美匹配,定义5 设M是图G的的一个匹配,其边在EM和M 中交错出现的路,称为G的一条M交错路.起点和终点都不是M的饱和点的M 交错路,称为M 增广路.,Berge定理：G的一个匹配M是最大匹配的充要条件是G不包含M 增广路.,定义 设

2、V=XY 且XY=,E xy|xX,yY,称G=(X,Y,E)为二部图或偶图.二部图可认为是有限简单无向图.如果X中的每个点都与Y中的每个点邻接,则称G=(X,Y,E)为完全二部图.若F：ER+,则称G=(X,Y,E,F)为二部赋权图.二部赋权图的权矩阵一般记作A=(aij)|X|Y|,其中aij=F(xi yj).,注意：此赋权矩阵与图的邻接矩阵不同！,邻接矩阵,二部图赋权矩阵,邻接矩阵,二部图赋权矩阵,Hall定理 设G=(X,Y,E)为二部图,则 G存在饱和X的每个点的匹配的充要条件是对任意S,有|N(S)|S|.其中,N(S)=v|uS,v与u相邻.G存在完美匹配的充要条件是对任意S

3、或S 有|N(S)|S|.,二部图的匹配及其应用,工作安排问题之一 给n个工作人员x1,x2,xn安排n项工作y1,y2,yn.n个工作人员中每个人能胜任一项或几项工作,但并不是所有工作人员都能从事任何一项工作.比如x1能做y1,y2工作,x2能做y2,y3,y4工作等.这样便提出一个问题,对所有的工作人员能不能都分配一件他所能胜任的工作？,二部图的匹配及其应用,我们构造一个二部图G=(X,Y,E),这里X=x1,x2,xn,Y=y1,y2,yn,并且当且仅当工作人员xi胜任工作yj时,xi与yj才相邻.于是,问题转化为求二部图的一个完美匹配.因为|X|=|Y|,所以完美匹配即为最大匹配.,二

4、部图的匹配及其应用,问题：如何求出二部图的一个完美匹配？,1965年匈牙利人Edmonds基于Hall定理提出一个算法，一般称为匈牙利（Hungarian）算法,匈牙利算法思路,求二部图G=(X,Y,E)的最大匹配算法(匈牙利算法）迭代步骤:,从G的任意匹配M开始.若X中的顶点皆是M饱和点，停止，M即完美匹配；否则将X中M的所有非饱和点都给以标号0和标记*,转向.若X中所有有标号的点都已去掉了标记*,则M是G的最大匹配，无完美匹配.否则任取X中一个既有标号又有标记*的点xi,去掉xi的标记*,转向.找出在G中所有与xi邻接的点yj,若所有这样的yj都已有标号,则转向,否则转向.,对与xi邻接且

5、尚未给标号的yj都给定标号i.,若所有的 yj 都是M的饱和点,则转向,否则逆向返回.即由其中M的任一个非饱和点 yj 的标号i 找到xi,再由 xi 的标号k 找到 yk,最后由 yt 的标号s找到标号为0的xs时结束,获得M-增广路xs yt xi yj,记E(P)=xs yt,xi yj,重新记M为ME(P),将所有标记标号清空，转向.ME(P)=(ME(P)(ME(P),是对称差.将yj在M中与之邻接的点xk,给以标号 j 和标记*,转向.,注释,上述匈牙利算法步骤中，标记*的作用在于标记X中的M非饱和点（可以能是临时的）标记（0，1、2、。）的作用是找M-增广路的过程的标记，从它也能

6、确定是否通过此顶点找过增广路。M-增广路总是以X中的M-非饱和点为起始，Y中的M-非饱和点结束的，所以找到了Y中的M-非饱和点才能找到M增广路,例17：求下图最大匹配,Hungarian算法：,二部图的匹配及其应用,注意到S=x1,x3,x4时，N(S)=y1,y3,由Hall定理，G没有完美匹配。,例18：求下图的最大匹配。,匈亚利算法：,解 取初始匹配M=x2 y2,x3 y3,x5 y5 给X中M的两个非饱和点x1,x4都给以标号0和标记*(如下图所示).,0,0,*,*,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,0,去掉x1的标记*,将与x1邻接的两个点y2,

7、y3都给以标号1.因为y2,y3都是M的两个饱和点,所以将它们在M中邻接的两个点x2,x3都给以相应的标号和标记*.,*,*,1,1,*,2,3,*,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,0,*,1,1,*,2,3,*,去掉x2的标记*,将与x2邻接且尚未给标号的三个点y1,y4,y5都给以标号2.,2,2,2,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,0,*,1,1,2,3,*,2,2,2,因为y1是M的非饱和点,逆向返回,直到x1为0为止.于是得到M的增广路x1 y2x2 y1,记P=x1 y2,y2x2,x2 y1.取M MP=x1

8、 y2,x2 y1,x3 y3,x5 y5,则新M是比原M多一边的匹配.,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,*,清空所有标记和标号。再给X中M的非饱和点x4给以标号0和标记*,然后去掉x4的标记*,将与x4邻接的两个点y2,y3都给以标号4.,4,4,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,4,4,因为y2,y3都是M1的两个饱和点,所以将它们在M1中邻接的两个点x1,x3都给以相应的标号和标记*.,*,*,2,3,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,0,4,4,*,*,2,3,去掉x1的标记*,因为与x

9、1邻接的两个点y2,y3都有标号4,所以去掉x3的标记*.,而与x3邻接的两个点y2,y3也都有标号4,此时X中所有有标号的点都已去掉了标记*(如上图所示),因此M是G的最大匹配.没有完美匹配。,二部图的匹配及其应用,例18：求下图的最大匹配。,匈亚利算法：,注意到S=x1,x3,x4时，N(S)=y1,y3,所以没有完美匹配。,二部图的匹配及其应用,定义6 设G=(X,Y,E,W)为完备的二部赋权图,若L：X Y R+满足：对任意xX,yY,L(x)+L(y)W(x y),则称L为G的一个可行点标记,记相应的生成子图为GL=(X,Y,EL,W),这里EL=x yE|L(x)+L(y)=W(x

10、 y).,定理3 设L是完备的二部赋权图G=(X,Y,E,F)的可行点标记,若M*是GL的完美匹配,则M*是G的权数最大的匹配。称为最佳（或最优）匹配.,工作安排问题之二 给n个工作人员x1,x2,xn安排n项工作y1,y2,yn.如果每个工作人员工作效率不同,要求工作分配的同时考虑总效率最高.,二部图的匹配及其应用,我们构造一个二部赋权图G=(X,Y,E,F),这里X=x1,x2,xn,Y=y1,y2,yn,F(xi yj)为工作人员xi胜任工作yj时的工作效率.则问题转化为：求二部赋权图G的最佳匹配.在求G 的最佳匹配时,总可以假设G为完备二部赋权图.若xi与yj不相邻,可令F(xi yj

11、)=0.同样地,还可虚设点x或y,使|X|=|Y|.如此就将G 转化为完备二部赋权图,而且不会影响结果.,二部图的匹配及其应用,求完备二部赋权图G=(X,Y,E,F)的最佳匹配算法迭代步骤：设G=(X,Y,E,F)为完备的二部赋权图,L是其一个初始可行点标记,通常取 L(x)=max F(x y)|yY,xX,L(y)=0,yY.,可行顶点标号法(Kuhn-Munkres算法)：,二部图的最佳匹配算法：,算法基本思想：通过顶点标记将赋权图转化为非赋权图，再用匈牙利算法求最大匹配,M是GL的一个匹配.,若X的每个点都是饱和的,则M是最佳匹配.否则取M的非饱和点uX,令S=u,T=,转向.记NL(S)=v|uS,uvGL.若NL(S)=T,则GL没有完美匹配,转向.否则转向.调整标记,计算aL=minL(x)+L(y)-F(xy)|xS,yYT.由此得新的可行点标记,令L=H,GL=GH,重新给出GL的一个匹配M,转向.,取yNL(S)T,若y是M的饱和点,转向.否则,转向.,设x yM,则令S=S x,T=T y,转向.,在GL中的u-y路是M-增广路,设为P,并令 M=MP,转向.,1 用Hungarian算法求下图最大匹配,作业（任选其一）,利用k-m算法求赋权矩阵为,的完备二部赋权图G=(X,Y,E,F)的最佳匹配。,作业2,