《图论最优匹配》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：判断下图的匹配判断下图的匹配最大匹配最大匹配非完美匹配非完美匹配完

2、美匹配完美匹配定义定义5 设设M是图是图G的的一个匹配的的一个匹配,其边在其边在EM和和M 中交错出现的路中交错出现的路,称为称为G的一条的一条M交错路交错路.起点起点和终点都不是和终点都不是M的饱和点的的饱和点的M 交错路交错路,称为称为M 增广路增广路.Berge定理：定理：G的一个匹配的一个匹配M是最大匹配的是最大匹配的充要条件充要条件是是G不包含不包含M 增广路增广路.定义定义 设设V V=XY 且且XY=,E xy|xX,yY,称称G=(X,Y,E)为为二部图或偶二部图或偶图图.二部图可认为是有限简单无向图二部图可认为是有限简单无向图.如果如果X中的每个点都与中的每个点都与Y中的每个

3、点邻接中的每个点邻接,则则称称G=(X,Y,E)为为完全二部图完全二部图.若若F：ER+,则称则称G=(X,Y,E,F)为为二部赋二部赋权图权图.二部赋权图的权矩阵一般记作二部赋权图的权矩阵一般记作A=(aij)|X|Y|,其中其中aij=F(xi yj).注意：此赋权矩阵与图的邻接矩阵不同！注意：此赋权矩阵与图的邻接矩阵不同！X:x1 x2 x3Y:y1 y26 3 4 8邻接矩阵邻接矩阵二部图赋权矩阵二部图赋权矩阵邻接矩阵邻接矩阵二部图赋权矩阵二部图赋权矩阵Hall定理定理 设设G=(X,Y,E)为二部图为二部图,则则 G存在存在饱和饱和X的每个点的匹配的充要条件是的每个点的匹配的充要条件

4、是对任意对任意S ,有有|N(S)|S|.其中其中,N(S)=v|uS,v与与u相邻相邻.G存在完美匹配的充要条件是存在完美匹配的充要条件是对任意对任意S 或或S 有有|N(S)|S|.二部图的匹配及其应用工作安排问题之一工作安排问题之一 给给n个工作人员个工作人员x1,x2,xn安排安排n项工作项工作y1,y2,yn.n个工作人员中每个人能胜任一项或几项工作个工作人员中每个人能胜任一项或几项工作,但但并并不是所有工作人员都能从事任何一项工作不是所有工作人员都能从事任何一项工作.比如比如x1能能做做y1,y2工作工作,x2能做能做y2,y3,y4工作等工作等.这样便提出一个问题这样便提出一个问

5、题,对所有的工作人员能不能都对所有的工作人员能不能都分配一件他所能胜任的工作？分配一件他所能胜任的工作？二部图的匹配及其应用 我们构造一个二部图我们构造一个二部图G=(X,Y,E),这里这里X=x1,x2,xn,Y=y1,y2,yn,并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时,xi与与yj才相邻才相邻.于是于是,问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配.因为因为|X|=|Y|,所以完美匹配即为最大匹配所以完美匹配即为最大匹配.二部图的匹配及其应用问题：如何求出二部图的一个完美匹配？问题：如何求出二部图的一个完美匹配？19651965年匈牙利人年

6、匈牙利人EdmondsEdmonds基于基于HallHall定理提出一个定理提出一个算法，一般称为匈牙利（算法，一般称为匈牙利（HungarianHungarian）算法）算法 匈牙利算法思路匈牙利算法思路 求二部图求二部图G=(X,Y,E)的最大匹配算法的最大匹配算法(匈牙匈牙利算法）迭代步骤利算法）迭代步骤:从从G的任意匹配的任意匹配M开始开始.若若X中的顶点皆是中的顶点皆是M饱和点，停止，饱和点，停止，M即即完美匹配；否则将完美匹配；否则将X中中M的所有的所有非饱和点非饱和点都给以都给以标号标号0 0和标记和标记*,*,转向转向.若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去

7、掉了标记*,*,则则M是是G的最大匹配，无完美匹配的最大匹配，无完美匹配.否则任取否则任取X中中一个既有标号又有标记一个既有标号又有标记*的点的点xi,去掉去掉xi的标记的标记*,*,转向转向.找出找出在在G G中所有中所有与与xi邻接的点邻接的点yj,若所有这若所有这样的样的yj都已有标号都已有标号,则转向则转向,否则转向否则转向.对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号i.若所有的若所有的 yj 都是都是M的的饱和点饱和点,则转向则转向,否则否则逆向返回逆向返回.即由其中即由其中M的任一个非饱和点的任一个非饱和点 yj 的标的标号号i 找到找到xi,再由再由

8、 xi 的标号的标号k 找到找到 yk,最后由最后由 yt 的标号的标号s找到标号为找到标号为0 0的的xs时结束时结束,获得获得M-增广路增广路xs yt xi yj,记记E E(P)=xs yt,xi yj ,重新记重新记M为为M E(P),将所有标记标号清空将所有标记标号清空，转向，转向.M E(P)=(ME(P)(ME(P),是对称差是对称差.将将yj在在M中与之邻接中与之邻接的点的点xk,给以标号给以标号 j 和标记和标记*,*,转向转向.注释上述匈牙利算法步骤中，标记上述匈牙利算法步骤中，标记*的作用在于的作用在于标记标记X中的中的M非饱和点（可以能是临时的）非饱和点（可以能是临时

9、的）标记（标记（0，1、2、。）的作用是找、。）的作用是找M-增广增广路的过程的标记，从它也能确定是否通过路的过程的标记，从它也能确定是否通过此顶点找过增广路。此顶点找过增广路。M-增广路总是以增广路总是以X中的中的M-非饱和点为起始，非饱和点为起始，Y中的中的M-非饱和点结束的，所以找到了非饱和点结束的，所以找到了Y中中的的M-非饱和点才能找到非饱和点才能找到M增广路增广路例例17：求下图最大匹配：求下图最大匹配Hungarian算法：算法：二部图的匹配及其应用注意到注意到S=x1,x3,x4时，时，N(S)=y1,y3,由由Hall定理，定理，G没有完美匹配。没有完美匹配。例例18：求下图

10、的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：解解 取初始匹配取初始匹配M=x2 y2,x3 y3,x5 y5 给给X中中M的两个非饱和点的两个非饱和点x1,x4都给以标号都给以标号0 0和标和标记记*(*(如下图所示如下图所示).).00*二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：00 去掉去掉x1的标记的标记*,将与将与x1邻接的两个点邻接的两个点y2,y3都给都给以标号以标号1.1.因为因为y2,y3都是都是M的两个饱和点的两个饱和点,所以将它们在所以将它们在M中邻接的两个点中邻接的两个点x2,x3都给以相应的标号和标记都给以相

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

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

13、两个点中邻接的两个点x1,x3都给以相应的标号和标记都给以相应的标号和标记*.*23二部图的匹配及其应用例例18：求下图的最大匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：044*23 去掉去掉x1的标记的标记*,因为与因为与x1邻接的两个点邻接的两个点y2,y3都有标号都有标号4,所以去掉所以去掉x3的标记的标记*.而与而与x3邻接的两个点邻接的两个点y2,y3也都有标号也都有标号4,此时此时X中所中所有有标号的点都已去掉了标记有有标号的点都已去掉了标记*(如上图所示如上图所示),因此因此M是是G的最大匹配的最大匹配.没有完美匹配。没有完美匹配。二部图的匹配及其应用例例18：求下图的最大

14、匹配。：求下图的最大匹配。匈亚利算法：匈亚利算法：注意到注意到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 y).定理定理3 设设L是完备的二部赋权图是完备的二部赋权图G=(X,Y,E,F)的可行点标记的可行点

15、标记,若若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时的工作效率时的工

16、作效率.则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配.在求在求G 的最佳匹配时的最佳匹配时,总可以假设总可以假设G为完备二部赋权为完备二部赋权图图.若若xi与与yj不相邻不相邻,可令可令F(xi yj)=0.同样地同样地,还可虚设点还可虚设点x或或y,使使|X|=|Y|.如此就将如此就将G 转化为完备二部赋权图转化为完备二部赋权图,而且而且不会影响结果不会影响结果.二部图的匹配及其应用 求完备二部赋权图求完备二部赋权图G=(X,Y,E,F)的最佳匹的最佳匹配算法迭代步骤：配算法迭代步骤：设设G=(X,Y,E,F)为完备的二部赋权图为完备的二部赋权图,L是其是其一个

17、初始可行点标记一个初始可行点标记,通常取通常取 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,则

18、则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=M P,转向转向.1 用用Hungarian算法求下图最大匹配算法求下图最大匹配作业（任选其一）利用利用k-m算法求赋权矩阵为算法求赋权矩阵为的完备二部赋权图的完备二部赋权图G=(X,Y,E,F)的最佳匹配。的最佳匹配。作业2