资源描述：
《二分图匹配及其应》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、二分图匹配及其应用刘汝佳目录增广路定理与Hall定理二分图最大基数匹配二分图最大权匹配应用二分图最大匹配二分图：结点可以分为两部分X和Y，每部分内部无边相连匹配：无公共点的边集合未盖点：不与任何匹配边邻接的点最大匹配：包含边数最多的匹配XY增广路从未盖点开始经过非匹配边、匹配边、非匹配边……序列，最终通过一条非匹配边到达另一个未盖点非匹配边个数比匹配边个数多一如果把匹配边和非匹配边互换…匹配仍合法，但基数加一增广路定理匹配是最大匹配当且仅当不存在增广路这个定理适用于任意图011001011010匈牙利树思
2、考：忽略虚线边会导致存在增广路却找不到吗？增广路定理的证明必要性.如果存在则增广后得到更大匹配.充分性.如果M不是最大匹配,取最大匹配M’,作M’和M的对称差G’,则G’在M’中的边应比M’中更多.G’有三种可能的连通分支孤立点.当某边(u,v)同时属于两个匹配,则u和v都是孤立点.交互回路.该回路中属于M和M’的边数相同交互道路.如果不存在增广路,则
3、M’
4、=
5、M
6、,与假设矛盾;如果存在M关于M’的增广路,又与M’是最大匹配矛盾,因此存在M’关于M的增广路Hall定理在二分图(X,Y,E)中,X到Y存在
7、完全匹配(X的结点全被匹配)的充要条件是对于X的任意子集A,恒有必要性.若存在A使得右边>左边,则A无法全部匹配充分性.假设G的最大匹配M不是完全匹配,一定存在结点X的结点x0关于M是非饱和点.如果x0的邻集为空,则令A={x0}引出矛盾;如果非空则其中每个结点均为饱和点(否则会有增广路).寻找与x0为端点的关于M的一切交错路,设其中Y结点的集合为Y’,X结点的集合为X’,则Y’结点与X’-{x0}的结点一一对应,因此
8、X’
9、>
10、Y’
11、,令A=X’引出矛盾.二分图最大匹配算法匈牙利树是从所有未盖点,而不是
12、从固定未盖点长出的树Edmonds-Karp算法:把所有未盖点放到队列中,BFS寻找/增广路时间均为O(m)最多找O(n)次时间复杂度O(nm)Hopcroft算法：每次沿多条增广路同时增广每次寻找若干条结点不相交最短增广路每次的最短增广路集是极大的时间复杂度基于DFS的算法:每次选一个未盖点u进行DFS.如果找不到增广路则换一个未盖点,且以后再也不从u出发找增广路.Hopcroft算法可以证明：如果每次找到的最短增广路集是极大的，则只需要增广次关键：用O(m)时间找一个极大最短增广路集步骤1：用距离标号
13、扩展匈牙利树，找到第一个未盖点时并不停止，把此时的距离标号设为上限。这样，找到的所有未盖点距离标号都相同步骤2：每次任取一个未盖点，用DFS找到它到起点的增广路(只沿着距离标号下降的方向),标记经过的点,找所有增广路的总时间为O(m)基于DFS的算法从贪心匹配,而不是空匹配开始每次从一个未盖点开始DFS找增广路,而不是一次性把所有未盖点放入队列进行BFS如果从一个未盖点u开始找不到增广路,则以后再也不用考虑u了.为什么?定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也
14、不存在从u出发关于增广后新匹配的增广路定理的证明(1)定理:假设G的匹配为M,不存在从非饱和点u出发的增广路,而存在另外一条增广路P,则G也不存在从u出发关于增广后新匹配M’的增广路证明:假设增广后从u出发有增广路Q.若Q与P不相交,则Q就是M-增广路,矛盾.因此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
15、关联,得到从u出发增广路wv0u0vuPQ完全二分图的最大权完美匹配完全二分图，每条边有一个非负整数权值目标：求出权和最大的完美匹配特点：完美匹配容易求，但权最大的不易可行顶标：结点函数l，对任意弧(x,y)满足相等子图：G的生成子图，包含所有点，但只包含满足l(x)+l(y)=w(x,y)的所有弧(x,y)相等子图定理：如果相等子图有完美匹配，则该匹配是原图的最大权匹配证明：设M*是相等子图的完美匹配，则根据定义设M是原图的任意完美匹配，则关键：寻找好的可行顶标，使相等子图有完美匹配算法思想关键：寻找好
16、的可行顶标，使相等子图有完美匹配思想：随便构造一个可行顶标（例如Y结点顶标为0，X结点的顶标为它出发所有弧的最大权值，然后求相等子图的最大匹配存在完美匹配，算法终止否则修改顶标使得相等子图的边变多，有更大机会存在完美匹配考虑相等子图不存在完美匹配时的情形Kuhn-Munkres算法如右图，相等子图的最大匹配基数为6，不是完美匹配算法在寻找增广路失败的同时得到了一棵匈牙利树虽然此匈牙利树并没有包含未盖点（因此没有找到增广路），但
