图论最优匹配课件.ppt

匈牙利算法思路 注释 上述匈牙利算法步骤中，标记*的作用在于标记X中的M非饱和点（可以能是临时的） 标记（0，1、2、。。）的作用是找M-增广路的过程的标记，从它也能确定是否通过此顶点找过增广路。 M-增广路总是以X中的M-非饱和点为起始，Y中的M-非饱和点结束的，所以找到了Y中的M-非饱和点才能找到M增广路 （或対集 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的的一个匹配, 其边在E\M和M 中交错出现的路, 称为G的一条M–交错路. 起点 和终点都不是M的饱和点的M –交错路, 称为 M –增广路. Berge定理： G的一个匹配M是最大匹配的充要条件是 G不包含M –增广路. 定义 设V=X∪Y 且X∩Y =? , E ?{xy|x∈X,y∈Y}, 称G =(X, Y, E)为二部图或偶图. 二部图可认为是有限简单无向图. 如果X中的每个点都与Y中的每个点邻接,则称G =(X, Y, E)为完全二部图. 若F：E→R +,则称G =(X, Y, E, F )为二部赋权图. 二部赋权图的权矩阵一般记作 A=(aij )|X|×|Y | , 其中aij = F (xi yj ). 注意：此赋权矩阵与图的邻接矩阵不同！ X: x1 x2 x3 Y: y1 y2 6 3 4 8 邻接矩阵 二部图赋权矩阵 邻接矩阵 二部图赋权矩阵 Hall定理 设G = ( X, Y, E )为二部图, 则① G存在 饱和X的每个点的匹配的充要条件是 对任意S　 ,有 | N (S ) | ≥ | S | . 其中, N (S ) = {v | u∈S, 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为M⊕E(P),将所有标记标号清空，转向①. M⊕E(P)=( M∪E(P) )\( M∩E(P)), 是对称差. ⑤ 将yj在M中与之邻接的点xk ,给以标号 j 和标记*, 转向②. 例1