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

,（或対集 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 增广路.,定义 设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 或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|, 所以完美匹配即为最大匹配.,二部图的匹配及其应用,问题：如何求出二部图的一个完美匹配？,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邻接且尚未给标号的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-增广路的过程的标记，从它也能确定是否通过此顶点找过增广路。 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, 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 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的标记*, 因为与x1邻接的两个点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 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 )=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 , 重新给出