《【课件】Kuhn-Munkres算法》由会员分享，可在线阅读，更多相关《【课件】Kuhn-Munkres算法（33页珍藏版）》请在金锄头文库上搜索。
1、1 Email yc517922 图论及其应用 任课教师 杨春 数学科学学院 2 本次课主要内容 一 匈牙利算法 二 最优匹配算法 匈牙利算法与最优匹配算法 3 一 匈牙利算法 1 偶图中寻找完美匹配 1 问题 设G X Y X Y 在G中求一完美匹配M 2 基本思想 从任一初始匹配M0出发 通过寻求一条M0可扩路P 令M1 M0 E P 得到比M0更大的匹配M1 近似于迭代思想 3 M可扩扩路的寻找方法 1965年 Edmonds首先提出 用扎根于M非饱和点u的M交错树的生长来求M可扩路 4 定义1设G X Y M是G的匹配 u是M非饱和点 称树H是G的扎根于点u的M交错树 如果 1 u V
2、 H 2 对任意v V H u v 路是M交错路 扎根于M非饱和点u的M交错树的生长讨论 5 假如扎根于M非饱和点u的M交错树为H 它有两种情形 情形1除点u外 H中所有点为M饱和点 且在M上配对 情形2H包含除u外的M非饱和点 对于情形1 令S V H X T V H Y 显然 1 若N S T 由于S u 中点与T中点配对 所以有 T S 1 于是有 N S S 1 S 由Hall定理 G中不存在完美匹配 6 2 若 令y N S T 则在树H中存在点x与y邻接 因为H的所有点 除u外 均在M下配对 所以 或者x u 或者x与H的某一顶点配对 但无论哪种情况 都有 当然 y可能为M饱和点
3、也可能为M非饱和点 7 若y为M饱和点 可设yz M 则加上顶点y及z和边xy与yz生长H 得到情形1 若y为M非饱和点 加上顶点y和边xy生长H 得到情形2 8 后一情况下找到一条M可扩路 可以对匹配进行一次修改 过程的反复进行 最终判定G是否有完美匹配或者求出完美匹配 根据上面讨论 可以设计求偶图的完美匹配算法 4 偶图完美匹配算法 匈牙利算法 设M是初始匹配 H是扎根于M非饱和点u的交错树 令 S V H X T V H Y a 若M饱和X所有顶点 停止 否则 设u为X中M非饱和顶点 置S u T b 若N S T 则G中不存在完美匹配 否则设y N S T c 若y为M饱和点 且yz
4、M 置S S z T T y 转 b 否则 设P为M可扩路 置M1 M E P 转 a 9 例1讨论下图G X Y 是否有完美匹配 解 取初始匹配M x1y2 x2y3 a S x3 T 10 b N S y2 y3 N S T 取y2 N S T c y2为M非饱和点 加上y2和边x3y2生长树H 此时 置M M E P x1y1 x2y3 x3y2 11 a S x4 T b N S y2 y3 N S T 取y2 N S T c y2为M饱和点 y2x3 M 此时 置S S x3 T T y2 b N S y2 y3 T 取y3 N S T 12 c y3为M饱和点 x2y3 M 此时
5、置S S x2 T T y3 b N S y2 y3 T 取y3 N S T b N S y2 y3 T 所以 G无完美匹配 5 匈牙利算法复杂性分析 13 1 最多循环 X 次可以找到完美匹配 2 初始匹配最多扩张 X 次可以找到完美匹配 3 每次生长树的生长至多2 X 1次 所以 算法复杂性为O X 3 是好算法 2 偶图中寻找最大匹配 问题 在一般偶图上求最大匹配M 分析 使用匈牙利算法求完美匹配时 当在扎根于M非饱和点u的交错树上有 N S S 时 由Hall定理 算法停止 要求出最大匹配 应该继续检查X S是否为空 如果不为空 则检查是否在其上有M非饱和点 一直到所有M非饱和点均没有
6、M可扩路才停止 14 偶图中寻找最大匹配算法 设M是G X Y 的初始匹配 1 置S T 2 若X S已经M饱和 停止 否则 设u是X S中的一非饱和顶点 置S S u 3 若N S T 转 5 否则 设y N S T 4 若y是M饱和的 设yz M 置S S z T T y 转 3 否则 存在 u y 交错路是M可扩路P 置M M E P 转 1 5 若X S 停止 否则转 2 15 二 最优匹配算法 1 问题 设G X Y 是边赋权完全偶图 且X x1 x2 xn Y y1 y2 yn wij w xiyj 在G中求出一个具有最大权值的完美匹配 由于Kn n有n 个不同完美匹配 所以枚举计
7、算量是n 在匈牙利算法的基础上 Kuhn 1955 与Munkres 1957 提出了上面问题的好算法 2 可行顶点标号与相等子图 16 定义2设G X Y 若对任意的x X y Y 有 称l是赋权完全偶图G的可行顶点标号 对于任意的赋权完全偶图G 均存在G的可行顶点标号 事实上 设 则l是G的一个可行顶点标号 17 定义3设l是赋权完全偶图G X Y 的可行顶点标号 令 称Gl G El 为G的对应于l的相等子图 例如 设如下矩阵是赋权完全偶图G的权值矩阵并注明了一种可行顶点标号l 18 定理设l是赋权完全偶图G X Y 的可行顶点标号 若相等子图Gl有完美匹配M 则M 是G的最优匹配 证明
8、 设M 是Gl的完美匹配 则 又设M是G的任一完美匹配 则 所以 w M w M 即M 是G的最优匹配 19 根据上面定理 如果找到一种恰当可行顶点标号 使得对应的相等子图有完美匹配M 则求出了G的最优匹配 Kuhn采用顶点标号修改策略 找到了求最优匹配好算法 介绍如下 给一初始顶点标号l 在Gl中任选一个匹配M 1 若X是M饱和的 则M是最优匹配 否则 令u是一个M非饱和点 置 S u T 2 若 转 3 否则 计算 20 给出新的可行顶点标号 在新标号下重新开始 3 在NGl S T中选择点y 若y是M饱和的 yz M 则置S S z T T y 转 2 否则 设P是Gl中M可扩路 置M
9、M E P 转 1 注 该算法把匈牙利算法用于其中 主要是用来判定和求完美匹配 21 例2 设如下矩阵是赋权完全偶图G的权值矩阵 求出其最优匹配 解 给出初始可行顶点标号l为 22 对应的相等子图Gl为 给出初始匹配M为 23 1 u x4为M非饱和顶点 置 2 3 取 y2为饱和顶点 y2x1 M 于是 2 3 取 y3为饱和顶点 y3x3 M 于是 24 2 于是修改标号 由得新标号为 25 继续使用算法后得 最优匹配权值为14 例3证明 K6n 2有一个3因子分解 证明 K6n 2 K2 3n 1 所以 可以分解为6n 3个边不重的1因子之和 而任意3个1因子可以并成一个3因子 所以 共
10、可以并成2n 1个3因子 即K6n 2可以分解为2n 1个3因子的和 26 例4证明 对n 1 K4n 1有一个4因子分解 证明 K4n 1 K2 2n 1 所以 可以分解为2n个边不重的2因子之和 而任意2个2因子可以并成一个4因子 所以 共可以并成n个4因子 即K4n 1可以分解为n个4因子的和 例5设H是有限群 K是H的子群 证明 存在元素h1 h2 hn H 使得h1K h2K hnK都是K的左陪集 而Kh1 Kh2 Khn都是K的右陪集 注 1 上面结论是群论学家Hall的一个结论 群论是近世代数的重要组成部分 在数学 计算机科学 理论物理学 量子场论 中都有重要应用 是数学领域里最
11、引人关注的方向和主流研究方向之一 创立者伽罗瓦 27 2 伽罗瓦 1811 1832 中学时受到数学老师里沙的影响而对数学产生极大兴趣 里沙对教学工作十分负责 且具有很高数学才能 但把精力耗在了学生身上 欣慰的是培养了好几位欧洲杰出数学家 中学时的伽罗瓦在里沙帮助下创立了群论 群论是19世纪最突出的数学成就 在法国历史上著名的1830年的 七月革命 中 伽罗瓦两次入狱 成为坚强斗士 1832年5月 21岁的他因为反动派设下的爱情圈套 被迫决斗至死 这是他犯下的草率的错误 28 证明 由陪集的性质 H中的任意两个左 右 陪集 要么相等 要么没有共同元素 所以H可按某子群的左 右 陪集 划分为左
12、右 陪集族 如果K是H的子群 则aK或者Kb的元素个数等于K中元素个数 设 K k 且假设子群K在群H中的指数为n 我们构造偶图G X Y 如下 X表示H关于K的左陪集族 Y表示H关于K的右陪集族 对于x X y Y x与y间连接l条边 当且仅当左陪集x和右陪集y有l个共同元素 显然G是k正则偶图 于是存在完美匹配M M n 在M中的边ei的两端点的陪集中选取共同元素hi 则这些元素为所求 1 i n 29 匹配在矩阵中的应用 1 矩阵与偶图 设A aij 是n阶方阵 构造偶图G X Y 如下 X表示行集合 Y表示列集合 X中元素xi与Y中元素yj连线 当且仅当aij 0 30 2 下面研究detA和GA X Y 之间关系 若 S n 则在A中存在n行 这n行中至多有n 1列元非零 而其余的 n 1列中每个元素为零 即得到A中有一个零子阵 31 于是有如下定理 32 作业 P117 118习题4 13 33 ThankYou
