二分图匹配 匈牙利算法和KM算法简介.ppt

1、二叉图匹配、匈牙利算法和KM算法概述、二叉图概念、二叉图也被称为二叉图，是图论中的特殊模型。 以G=(V，r )为无向图。 像顶点定径套v一样，可以分割为不相交的两个子定径套，图的各边连接的两个顶点属于两个子定径套。 图g称为二分图。 的双曲馀弦值。 指定最大匹配、2分割格拉夫g。 在g的子格拉夫m中，如果m的边缘定径套e的任何两条边缘没有附着到同一顶点，则m被称为匹配。 如果在最大匹配问题的匹配中选择具有最多边的子定径套，并且如果该图的顶点与该图的某一边相关联，则将该匹配也称为完全匹配。 匈牙利算法，求最大匹配的明显算法之一是找到所有匹配，然后保持匹配数最多的算法。 然而，此算法的复杂度为边

2、数的指数函数。 因此，需要寻求更有效率的算法。 放大路线的定义(也称为放大轨道或隔行的):p是连接图g中两个不整合顶点的路线，如果属于m的边和不属于m的边(即匹配边)交替地出现在p上，那么p也被称为m的放大路线。 匈牙利算法可以根据扩展的定义得出3个结论，其中，1P的路径长度必须是奇数，并且第一边和最后边都不属于m。 2P可以经过反转操作得到更大的匹配m。 3M是g的最大匹配，只有当到m的扩展路径不存在时。 (2)找到扩展的路线p并取反操作，以取代M (3)获得更大的匹配(也称为匈牙利算法)的匈牙利数学家Edmonds于1965年提出了算法轮廓： (1)清空m 伫列，father :阵列1.

3、100整数。 贝根队列1 :=k； st :=1； sf :=1； 过滤器(father，sizeof(father )，0 )； repeat，匈牙利的算法，fori 3360=1条件if (fatheri=0)和(aqueue ST，I=1)条件匹配2 I 0条件匹配队列3360=匹配2 I； fatheri :=请求； end else、匈牙利算法、begin j :=queuest； 真实事件t :=匹配1 j。 match1j :=i； 匹配2 I :=j； if t=0中断； i :=t； j :=fathert； 匈牙利算法end find :=1； 退出； 结束； 结束； 国际

4、航空运输协会(ST )； 中小企业stsf； find :=0； 结束； 匈牙利算法可以通过在主计程仪报中调用下一个计程仪报获得最大匹配数。 b匹配3360=0； fori 3360=1整合式3360=整合式(I )。 写入(b匹配)； 关于二叉图的性质：最大匹配数最大独立集XY，最佳匹配，如果边有权重，找到权重和最大匹配就是求最佳匹配。 实际模型：某公司有员工x1，x2，xn，他们做工作y1，y2，yn，各员工各办事儿利益不一定一致。 制定分工方案，要尽量发挥人才，使公司获得的总利润最大化。 数学模型： g是加权完全二叉图，求总权值最大的完全匹配。 KM算法，贫穷效率n！ 我需要更好的算法。

5、 定理： m为加权完全二分图g的完全匹配，对每个顶点赋予一个可执行掌门人标记(第I个x顶点的可执行标记用lxi表示，第j个y顶点的可执行标记用lyj表示)，对于所有的边(I，j) in G，lxi lyj=wi的证明很简单为什么KM算法不存在任何g和m的所有可执行掌门人标记： l(x)=maxw(x，y) l(y)=0需求完全二叉格拉夫的最佳匹配仅需要在匈牙利算法中与其相等的子格拉夫的完全匹配什么？ 什么？ Kuhn和Munkras提供用于解决该问题的有效算法，以逐步修正可执行的掌门人标签条l(v )的方式将对应的相等子格拉夫的最大匹配逐步扩大，最后出现完全匹配。另外，KM算法和修改方法首先将

6、不匹配的顶点u(u in x )同时扩展以记录哪些节点不网站数据库至这些节点。 求出d=minlxi lyj-wi，j其中I结点被访问，j结点没有被访问。 然后调整lx和ly。 对于网站数据库的x顶点，从其可执行标记中减去d，对于网站数据库的y顶点，将该可执行标记增加d。 修正的掌门人标记仍然是可执行掌门人标记，导致了m的扩展，因为原始匹配m仍存在，且不属于至少一个m的边出现在相等子格拉夫中。 KM算法，上述算法的证明也容易KuhnMunkras算法的流程： (1)初始化可执行的掌门人营销对象的值；(2)在匈牙利算法寻找完全一致；(3)如果没有找到完全一致就修正可执行的掌门人营销对象的值；(4

7、)直到找到同等的子图；(2) (3)重复王树禾离散数学引用论吴文虎王建德图论算法和普计程仪设订刘汝佳黄亮算法艺术和情报学大赛2002年冬令营论文孙方成偶图的算法和应用2004年冬令营论文黄源河浅谈图论模型的建构和应用，例题1 Place the Robots(ZOJ1654 )，问题的描述是一个n 在同一行或同一列中的两个机械人，如果它们之间没有墙壁则可以相互攻击。 在给定的棋盘上，最多可以放置几台机械人，以免互相攻击？ 例题1 Place the Robots(ZOJ )、模型1和问题被转换成求图的最大独立集问题。 在问题的原型中，草坪、墙壁等信息不是我们所关心的，我们所关心的只是空地和空地

8、的联系。 因此，以空地为顶点，有冲突的空地之间的联系，可以得到右侧的图这样简单的模型是自然考虑的：例题1 Place the Robots(ZOJ )，模型1，在问题的原型中，草地、墙这样的信息是我们不关心的，所以以空地为顶点，冲突的空地的双曲馀弦值。 各行、各列由墙壁分隔，包含空地的连续区域称为“封摇滾乐”。 当然，一个封摇滾乐中最多只能放一个机械人。 我们在这些个的封摇滾乐上加上号码。 同样，也对垂直方向的子摇滾乐进行编号。 例题1 Place the Robots(ZOJ )、模型2、1、2、3、4、5、例题1 Place the Robots(ZOJ )、模型2、1、2、3的话，问题是

9、2，因为各边表示空地，冲突的空地之间必定有共同的顶点例题1 Place the Robots(ZOJ )、模型2、1、2、3、5、4、比较前的两个模型：模型1过于简单，解决问题没有任何方便的模型2将问题的内在联系作为一盏茶，巧妙地建构了两个图模型。 为什么会产生这样完全不同的结果呢？ 其一是因为相对于问题分析的角度不同：模型1以空地为点，模型2以空地为边的其二是因为手板模型中的要素的选择不同：模型一对要素的选择不一盏茶，模型2保持着手板模型中的“盘”的重要性质。 由此可见，要素的选择在图论建模中是重要的一头地。 例题1 Place the Robots(ZOJ )，总结，例题2救护伤员(TOJ

10、1148 )，无情的海啸波夺去了无数人的生命。 许多医疗工作团队被派往灾区抢救伤员。 当时医疗工作团队发现突然地自各儿携带的药品脚丫子丢失，只剩下n种。 (1 n=20 )随着患者病情的发展，每种药物每天所取得的效果不同。 对云同步，一天只能服用一种药。 也就是说，这些个的药还通讯端口n天。显示现在你的各种药每天使用的效果。 判断使用各种药物后，所有药物能达到的效果之和最大有多少。 例题3打猎，猎人在n*n的格子中打鸟。 他能在某一行开一枪。 这样，该行的所有鸟被断开。 也可以在某一列打。 这样，该列的所有鸟被断开。 杀所有鸟，至少需要打几枪？ 建图：二分图的x部分按行，y部分按列，(I，j )有鸟的话，连接x部分的I和y部分的j。 这个二分图的最大匹配数是最低射击枪数。 例题4的最小根盖是在不包括循环的有向图g中，g的根盖是该节点不相交的根集合p，并且格拉夫中的各节点仅包含在p中的任何根上。 路径可以从任何节点开始和结束，长度也可以是任何值，包括0。 请给我不含环的有向图g的最小路径复盖数。 整理一个关系：最小路径观盖数g的定点数最小路径观盖中的边数，例题4最小路径观盖，应尽量增加最小路径观盖中的边数