二分图匹配及其应用.ppt
《二分图匹配及其应用.ppt》由会员分享,可在线阅读,更多相关《二分图匹配及其应用.ppt(45页珍藏版)》请在三一文库上搜索。
1、二分图匹配及其应用,刘汝佳,目录,增广路定理与Hall定理 二分图最大基数匹配 二分图最大权匹配 应用,二分图最大匹配,二分图: 结点可以分为两部分X和Y,每部分内部无边相连 匹配:无公共点的边集合 未盖点:不与任何匹配边邻接的点 最大匹配:包含边数最多的匹配,X,Y,增广路,从未盖点开始经过非匹配边、匹配边、非匹配边序列,最终通过一条非匹配边到达另一个未盖点 非匹配边个数比匹配边个数多一 如果把匹配边和非匹配边互换,匹配仍合法,但基数加一,增广路定理,匹配是最大匹配当且仅当不存在增广路,这个定理适用于任意图,0,1,1,0,0,1,0,1,1,0,1,0,匈牙利树,思考:忽略虚线边会导致存在
2、增广路却找不到吗?,增广路定理的证明,必要性. 如果存在则增广后得到更大匹配. 充分性. 如果M不是最大匹配, 取最大匹配M, 作M和M的对称差G, 则G在M中的边应比M中更多. G有三种可能的连通分支 孤立点. 当某边(u,v)同时属于两个匹配, 则u和v都是孤立点. 交互回路. 该回路中属于M和M的边数相同 交互道路. 如果不存在增广路, 则|M|=|M|, 与假设矛盾; 如果存在M关于M的增广路, 又与M是最大匹配矛盾, 因此存在M关于M的增广路,Hall定理,在二分图(X,Y,E)中, X到Y存在完全匹配(X的结点全被匹配)的充要条件是对于X的任意子集A, 恒有 必要性. 若存在A使得
3、右边左边, 则A无法全部匹配 充分性. 假设G的最大匹配M不是完全匹配, 一定存在结点X的结点x0关于M是非饱和点. 如果x0的邻集为空, 则令A=x0引出矛盾; 如果非空则其中每个结点均为饱和点(否则会有增广路). 寻找与x0为端点的关于M的一切交错路, 设其中Y结点的集合为Y, X结点的集合为X, 则Y结点与X-x0的结点一一对应, 因此|X|Y|, 令A=X引出矛盾.,二分图最大匹配算法,匈牙利树是从所有未盖点, 而不是从固定未盖点长出的树 Edmonds-Karp算法: 把所有未盖点放到队列中, BFS 寻找/增广路时间均为O(m) 最多找O(n)次 时间复杂度O(nm) Hopcro
4、ft算法:每次沿多条增广路同时增广 每次寻找若干条结点不相交最短增广路 每次的最短增广路集是极大的 时间复杂度 基于DFS的算法: 每次选一个未盖点u进行DFS. 如果找不到增广路则换一个未盖点, 且以后再也不从u出发找增广路.,Hopcroft算法,可以证明:如果每次找到的最短增广路集是极大的,则只需要增广 次 关键:用O(m)时间找一个极大最短增广路集 步骤1:用距离标号扩展匈牙利树,找到第一个未盖点时并不停止,把此时的距离标号设为上限。这样,找到的所有未盖点距离标号都相同 步骤2:每次任取一个未盖点,用DFS找到它到起点的增广路(只沿着距离标号下降的方向), 标记经过的点, 找所有增广路
5、的总时间为O(m),基于DFS的算法,从贪心匹配, 而不是空匹配开始 每次从一个未盖点开始DFS找增广路, 而不是一次性把所有未盖点放入队列进行BFS 如果从一个未盖点u开始找不到增广路, 则以后再也不用考虑u了. 为什么? 定理: 假设G的匹配为M, 不存在从非饱和点u出发的增广路, 而存在另外一条增广路P, 则G也不存在从u出发关于增广后新匹配的增广路,定理的证明(1),定理: 假设G的匹配为M, 不存在从非饱和点u出发的增广路, 而存在另外一条增广路P, 则G也不存在从u出发关于增广后新匹配M的增广路 证明: 假设增广后从u出发有增广路Q. 若Q与P不相交, 则Q就是M-增广路, 矛盾.
6、 因此Q与P相交. 下面借助P和Q构造出从u出发关于M的增广路, 从而得到矛盾,定理的证明(2),Q与P相交. 设P的两个M-非饱和点为u0和v0, 而Q的两个M-非饱和点是u, v. 从u开始沿Q走, 设第一个P中结点为w, 则w把P分为两段, 其中必有一段以M中边与w关联, 得到从u出发增广路,w,v0,u0,v,u,P,Q,完全二分图的最大权完美匹配,完全二分图,每条边有一个非负整数权值 目标:求出权和最大的完美匹配 特点:完美匹配容易求,但权最大的不易 可行顶标:结点函数l,对任意弧(x,y)满足 相等子图:G的生成子图,包含所有点,但只包含满足l(x)+l(y)=w(x,y)的所有弧
7、(x,y),相等子图,定理:如果相等子图有完美匹配,则该匹配是原图的最大权匹配 证明:设M*是相等子图的完美匹配,则根据定义 设M是原图的任意完美匹配,则 关键:寻找好的可行顶标,使相等子图有完美匹配,算法思想,关键:寻找好的可行顶标,使相等子图有完美匹配 思想:随便构造一个可行顶标(例如Y结点顶标为0,X结点的顶标为它出发所有弧的最大权值,然后求相等子图的最大匹配 存在完美匹配,算法终止 否则修改顶标使得相等子图的边变多,有更大机会存在完美匹配 考虑相等子图不存在完美匹配时的情形,Kuhn-Munkres算法,如右图,相等子图的最大匹配基数为6,不是完美匹配 算法在寻找增广路失败的同时得到了
8、一棵匈牙利树 虽然此匈牙利树并没有包含未盖点(因此没有找到增广路),但仍然含有重要信息,Kuhn-Munkres算法,设匈牙利树中的X结点集为S,Y结点集为T,则 S到T没有边(否则匈牙利树可以继续生长) S到T的边都是非匹配边(想一想,为什么) 但若把S中所有点的顶标同时减少一个相同整数a,则S到T中可能会有新边进入相等子图,S,T,Kuhn-Munkres算法,把S中所有点的顶标同时减少一个相同整数a,则S到T中可能会有新边进入相等子图 为了保证S-T的匹配边不离开相等子图,把T中所有点的顶标同时增加a,S,T,-a,+a,为保证有新边进入,取,如果S中每个顶标的实际减小值比这个值小则不会
9、有新边进入;如果比这个值大则顶标将变得不可行,Kuhn-Munkres算法,设边(x,y)进入相同子图 y是未盖点,则找到增广路 y和S中的点z匹配,则把z和y分别加入S和T中 每次修改顶标要么找到增广路,要么使匈牙利树增加两个结点 因此一共需要O(n2)次修改顶标操作 关键:快速修改顶标,S,T,-a,+a,顶标的修改,方法1:枚举S和T中的每个元素,根据定义计算最小值,每次修改的时间为O(n2),总O(n4) 方法2:对于T中的每个元素y,定义松弛量 则a的计算公式变为,顶标的快速修改,每次增广后用O(n2)时间计算所有点的初始slack,由于每次生长匈牙利树时所有S-T弧的增量相同,因此
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二分 匹配 及其 应用
链接地址:https://www.31doc.com/p-2571232.html