最优匹配PPT学习教案

1、会计学1 最优匹配最优匹配 定义定义3 若匹配若匹配M的某条边与点的某条边与点v关联关联, 则称则称M饱和饱和 点点v, 并且称并且称v是是M的的饱和点饱和点, 否则称否则称v是是M的的非饱非饱 和点和点. 定义定义4 设设M是图是图G的一个匹配的一个匹配, 如果如果G的每一个点的每一个点 都是都是M的饱和点的饱和点, 则称则称M是是完美匹配完美匹配；如果；如果G中中 没有另外的匹配没有另外的匹配M0, 使使 | M0 | M |, 则称则称M是是最最 大匹配大匹配. 每个完美匹配都是最大匹配每个完美匹配都是最大匹配, 反之不一定成立反之不一定成立. 第1页/共32页 例例16： 判断下图的匹

2、配判断下图的匹配 最大匹配最大匹配 非完美匹配非完美匹配 完美匹配完美匹配 第2页/共32页 定义定义5 设设M是图是图G的的一个匹配的的一个匹配, 其边在其边在EM和和M 中交错出现的路中交错出现的路, 称为称为G的一条的一条M交错路交错路. 起点起点 和终点都不是和终点都不是M的饱和点的的饱和点的M 交错路交错路, 称为称为 M 增广路增广路. Berge定理：定理： G的一个匹配的一个匹配M是最大匹配的是最大匹配的充要条件充要条件是是 G不包含不包含M 增广路增广路. 第3页/共32页 定义定义 设设V V= =XY 且且XY = , , E xy| |xX, ,yY, , 称称G =(

3、X, Y, E)为为二部图或偶二部图或偶 图图. . 二部图可认为是有限简单无向图二部图可认为是有限简单无向图. . 如果如果X中的每个点都与中的每个点都与Y中的每个点邻接中的每个点邻接, ,则则 称称G =(X, Y, E)为为完全二部图完全二部图. . 若若F：ER + +, ,则称则称G =(X, Y, E, F )为为二部赋二部赋 权图权图. . 二部赋权图的权矩阵一般记作二部赋权图的权矩阵一般记作 A=(aij )|X| |Y | , , 其中其中aij = F (xi yj ). . 第4页/共32页 注意：此赋权矩阵与图的邻接矩阵不同！注意：此赋权矩阵与图的邻接矩阵不同！ X:

4、x1 x2 x3 Y: y1 y2 6 3 4 8 12 1 2 3 60 34 80 yy x Ax x 12312 1 2 3 1 2 00060 00034 00080 63800 04000 xxxyy x x Ax y y 邻接矩邻接矩 阵阵 二部图赋权矩二部图赋权矩 阵阵 邻接矩邻接矩 阵阵 12 1 2 3 60 34 80 yy x Ax x 二部图赋权矩二部图赋权矩 阵阵 第5页/共32页 Hall定理定理 设设G = ( X, Y, E )为二部图为二部图, 则则 G存在存在 饱和饱和X的每个点的匹配的充要条件是的每个点的匹配的充要条件是 对任意对任意S ,有有 | N (

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

6、y2工作工作, x2能做能做y2, y3, y4工作等工作等. 这样便提出一个问题这样便提出一个问题, 对所有的工作人员能不能都对所有的工作人员能不能都 分配一件他所能胜任的工作？分配一件他所能胜任的工作？ 二部图的匹配及其应用 第7页/共32页 我们构造一个二部图我们构造一个二部图G = ( X, Y, E ), 这里这里 X = x1, x2, , xn,Y = y1, y2, , yn, 并且当且仅当工作人员并且当且仅当工作人员xi胜任工作胜任工作yj时时, xi与与yj才相邻才相邻. 于是于是, 问题转化为求二部图的一个完美匹配问题转化为求二部图的一个完美匹配. 因为因为 |X|=|Y

7、|, 所以完美匹配即为最大匹配所以完美匹配即为最大匹配. 二部图的匹配及其应用 问题：如何求出二部图的一个完美匹配？问题：如何求出二部图的一个完美匹配？ 19651965年匈牙利人年匈牙利人EdmondsEdmonds基于基于HallHall定理提出一定理提出一 个算法，一般称为匈牙利（个算法，一般称为匈牙利（HungarianHungarian）算法）算法 第8页/共32页 第9页/共32页 从从G的任意匹配的任意匹配M开始开始. . 若若X中的顶点皆是中的顶点皆是M饱和点，停止，饱和点，停止， M即即 完美匹配；完美匹配；否则将否则将X中中M的所有的所有非饱和点非饱和点都给以都给以 标号标

8、号0 0和标记和标记* *,转向转向. . 若若X中所有有标号的点都已去掉了标记中所有有标号的点都已去掉了标记* *, , 则则M是是G的最大匹配，无完美匹配的最大匹配，无完美匹配. . 否则任取否则任取X 中一个既有标号又有标记中一个既有标号又有标记* *的点的点xi , , 去掉去掉xi的标记的标记 * *, , 转向转向. . 找出找出在在G G中所有中所有与与xi邻接的点邻接的点yj , , 若所有若所有 这样的这样的yj都已有标号都已有标号, , 则转向则转向, , 否则转向否则转向. . 第10页/共32页 对与对与xi邻接且尚未给标号的邻接且尚未给标号的yj都给定标号都给定标号

9、i. . 若所有的若所有的 yj 都是都是M的的饱和点饱和点, ,则转向则转向, ,否则否则 逆向返回逆向返回. . 即由其中即由其中M的任一个非饱和点的任一个非饱和点 yj 的标的标 号号i 找到找到xi , ,再由再由 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

10、) )( ME(P), , 是对称差是对称差. . 将将yj在在M中与之邻接中与之邻接的点的点xk , ,给以标号给以标号 j 和标记和标记* *, , 转向转向. . 第11页/共32页 第12页/共32页 1 x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y 5 y 例例17：求下图最大匹配：求下图最大匹配 Hungarian算法：算法： 二部图的匹配及其应用 第13页/共32页 注意到注意到S=x1,x3,x4时，时，N(S)=y1,y3, ,N SS 由由Hall定理，定理，G没有完美匹配。没有完美匹配。 第14页/共32页 例例18：求下图的最大匹配。：求下图的最大

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

12、中邻接的两个点x2, x3都给以相应的标号和标记都给以相应的标号和标记*. * * 11 *2 3 * 二部图的匹配及其应用 第16页/共32页 例例18：求下图的最大匹配。：求下图的最大匹配。 匈亚利算法：匈亚利算法： 00 * 11 *2 3 * 去掉去掉x2的标记的标记*, 将与将与x2邻接且尚未给标号的三邻接且尚未给标号的三 个点个点y1, y4, y5都给以标号都给以标号2. 222 二部图的匹配及其应用 第17页/共32页 例例18：求下图的最大匹配。：求下图的最大匹配。 匈亚利算法：匈亚利算法： 00 * 11 23 * 222 因为因为y1是是M的非饱和点的非饱和点, 逆向返回

13、逆向返回, 直到直到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页/共32页 例例18：求下图的最大匹配。：求下图的最大匹配。 匈亚利算法：匈亚利算法： 0 * 清空所有标记和标号。清空所有标记和标号。再给再给X中中M的非饱和点的非饱和点x4 给以标号给以标号0和标记和标记*, 然后去掉然后去掉x4的标记的标记*, 将与将与x4邻接的两邻接

14、的两 个点个点y2, y3都给以标号都给以标号4. 44 二部图的匹配及其应用 第19页/共32页 例例18：求下图的最大匹配。：求下图的最大匹配。 匈亚利算法：匈亚利算法： 0 44 因为因为y2, y3都是都是M1的两个饱和点的两个饱和点, , 所以将它们在所以将它们在M1 中邻接的两个点中邻接的两个点x1, x3都给以相应的标号和标记都给以相应的标号和标记*. *2 3 二部图的匹配及其应用 第20页/共32页 例例18：求下图的最大匹配。：求下图的最大匹配。 匈亚利算法：匈亚利算法： 0 44 *2 3 去掉去掉x1的标记的标记*, 因为与因为与x1邻接的两个点邻接的两个点 y2, y

15、3都有标号都有标号4, 所以去掉所以去掉x3的标记的标记*. 而与而与x3邻接的两个点邻接的两个点y2, y3也都有标号也都有标号4, 此时此时X中所中所 有有标号的点都已去掉了标记有有标号的点都已去掉了标记*(如上图所示如上图所示), 因此因此M是是 G的最大匹配的最大匹配.没有完美匹配。没有完美匹配。 二部图的匹配及其应用 第21页/共32页 例例18：求下图的最大匹配。：求下图的最大匹配。 匈亚利算法：匈亚利算法： 注意到注意到S=x1,x3,x4时，时，N(S)=y1,y3, ,N SS 所以没有完美匹配。所以没有完美匹配。 二部图的匹配及其应用 第22页/共32页 定义定义6 设设G

16、 = ( 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). 第23页/共32页 定理定理3 设设L是完备的二部赋权图是完备的二部赋权图G = ( X, Y, E , F ) 的可行点标记的可行点标记, 若若M *是是GL的完美匹配的完美

17、匹配, 则则M *是是G 的的权数最大的匹配。称为权数最大的匹配。称为最佳（或最优）匹配最佳（或最优）匹配. 第24页/共32页 工作安排问题之二工作安排问题之二 给给n个工作人员个工作人员x1, x2, , xn安排安排n项工作项工作y1, y2, , yn. . 如果每个工作人员工作效率不同如果每个工作人员工作效率不同, 要求工作分配的要求工作分配的 同时考虑同时考虑总效率最高总效率最高. 二部图的匹配及其应用 第25页/共32页 我们构造一个二部赋权图我们构造一个二部赋权图G = ( X, Y, E , F ), 这里这里X = x1, x2, , xn,Y = y1, y2, , yn

18、, F(xi yj )为工作人员为工作人员xi胜胜 任工作任工作yj时的工作效率时的工作效率. 则问题转化为：求二部赋权图则问题转化为：求二部赋权图G的最佳匹配的最佳匹配. 在求在求G 的最佳匹配时的最佳匹配时, 总可以假设总可以假设G为完备二部赋权为完备二部赋权 图图. .若若xi与与yj不相邻不相邻, 可令可令F(xi yj )=0. 同样地同样地, 还可虚设点还可虚设点x 或或y, ,使使|X|=|Y|. .如此就将如此就将G 转化为完备二部赋权图转化为完备二部赋权图, ,而且而且 不会影响结果不会影响结果. 二部图的匹配及其应用 第26页/共32页 求完备二部赋权图求完备二部赋权图G

19、= (X, Y, E, F )的最佳匹的最佳匹 配算法迭代步骤：配算法迭代步骤： 设设G =( (X, Y, E, F) )为完备的二部赋权图为完备的二部赋权图, ,L是是 其一个初始可行点标记其一个初始可行点标记, ,通常取通常取 L(x) = max F (x y) | yY , xX, L(y) = 0, , yY. 可行顶点标号法可行顶点标号法(Kuhn-Munkres算法算法)： 二部图的最佳匹配算法：二部图的最佳匹配算法： 算法基本思想：通过顶点标记将赋权图转化为非赋权算法基本思想：通过顶点标记将赋权图转化为非赋权 图，再用匈牙利算法求最大匹配图，再用匈牙利算法求最大匹配 第27页/共32页 M是是GL的一个匹配的一个匹配 . . 若若X的每个点都是饱和的的每个点都是饱和的,则则M是最佳匹