《下载课件二分图的定义匹配-PowerPointPresentation》由会员分享，可在线阅读，更多相关《下载课件二分图的定义匹配-PowerPointPresentation（41页珍藏版）》请在金锄头文库上搜索。
1、 匹配的概念 二分图的定义和判定 二分图的最大匹配 二分图的最小覆盖问题 二分图的最佳匹配问题1、匹配的概念(1)匹配的概念(2)二分图的定义二分图的判定二分图的最大匹配Edmonds于1965年提出了解决二分图的最大匹配的匈牙利算 法：例题：小狗散步Grant喜欢带着他的小狗Pandog散步。Grant以一定的 速度沿着固定路线走，该路线可能自交。Pandog喜 欢游览沿途的景点，不过会在给定的N个点和主人 相遇。小狗和主人同时从点出发，并同时在点汇合 。小狗的速度最快是Grant的两倍。当主人从一个点 以直线走向另一个点时，Pandog跑向一个他感兴趣 的景点。Pandog每次与主人相遇之
2、前最多只去一个 景点。 已知n个定点的坐标和m个景点的坐标。你的任务是 ：为Pandog寻找一条路线（有可能与主人的路线部 分相同），使它能够游览最多的景点，并能够准时 与主人在给定地点相遇或者汇合。 将顶点分成两类由于“当主人从一个点以直线走向另一个点时，Pandog跑向 一个他感兴趣的景点”，并且主人的移动路线是确定的，所 以寻找一条路线可以看作确定在每一段路线上小狗的选择： 或是跑向哪一个景点，或是和主人的路线重合。因此图中的 点被自然的分成了两类： 每一段路线 景点定义边由于在一个线段上，小狗只能跑向一个景 点，所以景点是否可达，只和景点到线段两 端点的距离有关，而小狗的速度最快是主人
3、 的两倍。由此得出线段的定义求二分图的最大匹配由于一条线段只能和一个景点发生关联，而 一个景点也只在第一次访问的时候才有意义 ，因此任何两项关联都不会有任何交点，这 显然满足了匹配的定义。两类顶点组成了一 个二分图。使用匈牙利算法求最大匹配数及 匹配方案 图的最小覆盖问题设D是图G的一个顶点子集，对于G的任一顶点u，要末u是D 集合的一个顶点元素，要末与D中的一个顶点相邻，那末D 称为图G的一个覆盖集。若在D集中去除任何元素D不再是覆 盖集，则覆盖集D是极小覆盖集。称G的所有覆盖集中顶点 个数最少的覆盖集为最小覆盖集D0，一般图的最小覆盖问题 是一个已被证明的NPC问题。换一句话说，一般图的最
4、小覆 盖问题，是没有有效算法的图论模型。所以，将一个实际问 题抽象成最小覆盖问题，是没有任何意义和价值的。 但是，如果问题可以抽象成二分图的最小覆盖问题，结局就 不一样了。由于二分图的特殊性，二分图的最小覆盖问题存 在多项式算法。二分图最大匹配与最小覆盖的关系在证明这个定理的过程中，要用到Hall婚姻定理：1931年Knig给出最大匹配与最小覆盖的关系定理如下： 例题：国际象棋一张大小为n*n的国际象棋棋盘，上面有一些 格子被拿走了，棋盘规模n不超过200。马的 攻击方向如下图，其中S处为马位置，标有X 的点为该马的攻击点。你的任务是确定在这个棋盘上放置尽可能多的 马，并使他们不互相攻击。求最
5、小覆盖集的图论问题将棋盘的每一个格子作为一个顶点，两点间直 接可达（互可攻击）的关系作为边。则题目所 要求的就是在这样一张图中的寻找一个最大独 立子集（即顶点集合中的任意两顶点都不相邻 、且含顶点数最多）。由于对于任意一张图， 其最大独立子集和最小覆盖集互为补集最大 独立子集=n-最小覆盖集，所以本题也是 一个求最小覆盖集的图论问题。 棋盘定义在攻击关系上是一个二分图在一张国际象棋的棋盘上，白格和黑格相交错，一 匹马只能从一个白格跳到一个黑格，或是从一个黑格 跳到一个白格。 必要条件：一个位置上的马只能攻击和其所在位置颜 色不同的格子。即同一颜色的任意两个格子间不存在 边。棋盘格子按照颜色分成
6、两个部分。 如果按照自上而下、由左而右的顺序给格子编号的话 ，在所有未被拿走的格子（i,j）中(1i,jn， mapi,j=true)，同种颜色的格子必须满足如下条件： n为奇数，且(i-1)*n+j为奇数； n为偶数，且i和j的奇偶性不同； 我们将所有同种颜色的格子组成X顶点集。显然X顶点 集中每个顶点跳后位置的颜色是不同的，其中未被拿 走的跳后位置组成Y顶点集。 通过二分图最大匹配计算问题解二分图的最大匹配数与最小覆盖数之间存在着 对应的数量关系，而最大独立子集和最小覆盖 集互为补集，因此我们可以通过求二分图的最 大匹配数，互不攻击情况下马的最多放置数目=未被拿 走的格子数-最多匹配数 二
7、分图的最佳匹配问题由于引入了权，所以最佳匹配不能直接套用最大匹配算法 进行求解。同时，由于对最佳匹配的定义是建立在完全加权 二分图的基础上的，对于不完全图，可以通过引入权为0（ 或是其他不影响最终结果的值），使得二分图称为完全二分 图，从而使用最佳匹配算法来解决。KM算法前的准备在介绍求最佳匹配的KM算法前，首先介绍一些 相关的概念：可以证明，Gl的完备匹配即为G的最佳匹配。 以此为基础，1955年Kuhn，1957年Munkres给出 修改顶标的方法，使新的相等子图的最大匹配逐渐 扩大，最后出现相等子图的完备匹配。 这就是KM算 法。KM算法一个例题某公司有工作人员x1,x2,xn ，他们去
8、 做工作y1,y2,yn ，每个人都能做其中的几 项工作，并且对每一项工作都有一个固定 的效率。问能否找到一种合适的工作分配 方案，使得总的效率最高。要求一个人只 能参与一项工作，同时一项工作也必须由 一个人独立完成。不要求所有的人都有工 作。一个实例Y1Y2Y3Y4Y5X135541X222022X324410X401100X512133若工人x 完全不能 参与工作 y，则 w(x,y)=0流程(1)首先，选取可行顶标l(v)如下：构造Gl，并求其最大匹配：（其流程过长，此处略）流程(2)其最终得到的最大匹配如图所示：图中粗点划线构成最大匹配。 流程(3)Gl中无完备匹配，故修改顶标。 流程
9、(4)根据新的顶标构造Gl ，并求其上的一个完 全匹配如图所示： 图中粗点划线给出了一个最佳匹配，其最大权为42 41314。题目完成。 例题 Roads请求出修改的最小代价。给定一个无向图G0=（V0，E0，C），V0为顶点 集合,E0为边集合（无重边），C为边权（非负整数） 。设n= |V0|，m= |E0|，E0中前n-1条边构成一棵生成树 T。请将边权进行如下修改，即对于eE，把Ce修改 成De（De也为非负整数），使得树T成为图G的一棵最 小生成树。修改的代价定义为：415234622357415234424334f=|6-4|+|2-2|+|5-3|+|7-4|+|3-3|+|2-
10、4|+|4-4|=9初步分析l根据与树T的关系,我们可以把图G0中的边分成 树边与非树边两类。l设Pe表示边e的两个端点之间的树的路径中边的 集合。初步分析如右图，uT，t1，t2，t3T，且t1 ，t2，t3连接了u的两个端点，所以 Pu=t1，t2，t3。/l 那么用非树边u代替树边t1， t2，t3中任意一条都可以得到一 棵新的生成树。l 而如果u的边权比所替换的 边的边权更小的话，则可以得到 一棵权值更小的生成树。l 那么要使原生成树T是一棵 最小生成树，必须满足条件：Dt1 Du ； Dt2 Du ； Dt3 Duut1t2t3初步分析如果边v，u(u可替换v)，则必须满足 Dv D
11、u ，否则用u替换v可得到一棵权值更小 的生成树T-v+u 。/对边v，u如果满足条件uT ，vPu， 则称u可替换v。初步分析不等式DvDu中v总为树边，而u总为 非树边。那么显然树边的边权应该减小(或不变)， 而非树边的边权则应该增大(或不变)。 设边权的修改量为，即 e=|DeCe|/当eT， e=DeCe, 即De=Cee当eT， e=CeDe，即De=Cee初步分析那问题就是求出所有的使其满足以上不等式且：最小。 那么当u可替换v时，由不等式观察此不等式其中不等号右侧CvCu是一个已知量！大家或许会发现这个不等式似曾相识!这就是在求二分图最佳匹配的经典KM算法中 不可或缺的一个不等式
12、。KM算法中，首先给二分图的每个顶点都设一个 可行顶标，X结点i为li，Y结点j为rj。从始至终，边权 为Wv,u的边(v,u)都需要满足lv + ru Wv,u 。1234567我们来构造二分图我们来构造二分图G G建立两个互补的结点集合X，Y。/Y结点j表示图G0中非树边aj(ajT)。X结点i表示图G0中树边ai(aiT)。XY设这些结点均为实点。1234567XY构造二分图构造二分图G G如果图G0中，aj 可替换ai，且CiCj0,则在X结点i和 Y结点j之间添加边(i,j), 边权Wi,j=CiCj。1234567XY1234567XY设这些边均为实边。1234567在结点数少的一
13、侧添加虚结点，使得X结点和Y结 点的数目相等。构造二分图构造二分图G G XY8如果X结点i和Y结点j之间没有边，则添加一条权 值为0的虚边(i,j)。12345678构造二分图构造二分图G G XY算法分析设完备匹配X的所有匹配边的权值和为SX，则对于图G的任意一个完备匹配X，都有设M为图G的最大权匹配，显然M也是完备匹配， 则满足显然，此时的可行顶标之和取到最小值。 因为虚结点Xi的匹配边肯定是权值为0的虚边， 所以li=0。同理对于虚结点Yj，rj = 0。显然，SM即是满足树T是图G0的一棵最小生 成树的最小代价。那么问题就转化为求图G的最 大权完备匹配M，即可用KM算法求解。算法分析
14、问题解决复杂度分析我们来分析一下该算法的时间复杂度。l预处理的时间复杂度为O(|E|) lKM算法的时间复杂度为O(|V|E|)由于图G是二分完全图。|V|=2maxn 1, m n + 1=O(m)|E|=|V|2=O(m2)所以算法总时间复杂度为O(m3) 。小结二分图是一种特殊的图，所以它不但具备了信息量丰富 这个图模型共有的优点，同时它也具备了大量一般图所不 具备的内涵和算法优势。 二分图的结点分成两个部分，这就是它和自然界、数学 界的对应关系，或者说匹配关系有着深刻的联系。因此， 匹配的算法是所有二分图算法的核心。 如果能将实际问题，通过合理的抽象，变成两种事物之 间的矛盾，则这种问题就可以抽象成二分图的模型。所以 ，二分图的模型有着广泛的应用。同时，二分图的算法有 着高效实用的特点，所以也使通过二分图模型解决问题成 为可能。 综上所述，二分图是一种高效的，有着广泛使用价值的 模型。合理、有效的使用二分图模型，将大大提高编程及 解决现实生活中实际问题的能力。
