下载课件二分图的定义匹配 - PowerPoint Presentation

1、1. 匹配的概念2. 二分图的定义和判定3. 二分图的最大匹配4. 二分图的最小覆盖问题5. 二分图的最佳匹配问题1、匹配的概念(1) ,GV GE GME GMMGMM定义1 设图，而是的一个子集，如果中的任两条边均不邻接，则称是 的一个匹配。中的一条边的两个端点叫做在下是配对的。MvMvvM 若匹配中的某条边与定点 关联，则称饱和顶点 ，并称 是饱和的。匹配的概念(2)MGGRMMRRM 设是图 的一个匹配，若 中存在一条基本路径，路径的边是由属于的匹配边和不属于的非匹配边交替出现组成，则称 为交替路。若 的两个端点都是的非饱和点，则称这条交替路为可增广路。 ,GV GE GV GXYGM

2、E GXXYMG 设图，被分成两个非空的互补顶点子集 和 ，若图 的一个匹配能饱和 中的每个顶点，换言之， 中的全部顶点和 中的一个子集的顶点之间确定一个一一对应关系，则称是图 的一个完备匹配。二分图的定义 12121212( ,)( ,;)GV EVVVEVVGV V EVVP VVV定义2 设图，若能把 分成两个集合 和，使得 中的每条边的两个端点，一个在 中，另一个在中，这样的图称为偶图，也叫二分图，或是二部图。偶图也可表示为。 对于顶点集，用表示中所有和 相连的顶点的集合。1GVG2定义3 如果偶图 的互补结点子集 中的每一结点都与V中的所有结点邻接，则称 为完全偶图。二分图的判定0,

3、0GG定理1 当且仅当无向图 的每一个回路的次数均为偶数时， 才是一个偶图。如果无回路，相当于任一回路的次数为视为偶数。二分图的最大匹配 (1)(2) ,(3)(4) , (3),( )(2)GMXMMXMuSu TP STyP STyMyzMSSz TTyR u yMME R 从 中取一个初始匹配。若 中的顶皆为中边的端点，止，即为完备匹配；否则，取 中不与中边关联的顶 ，记。若，止，无完备匹配，否则，取。若 是中边的端点，设，令，转；否则，取可增广路径，令，转。Edmonds于1965年提出了解决二分图的最大匹配的匈牙利算法：例题：小狗散步例题：小狗散步Grant喜欢带着他的小狗Pando

4、g散步。Grant以一定的速度沿着固定路线走，该路线可能自交。Pandog喜欢游览沿途的景点，不过会在给定的N个点和主人相遇。小狗和主人同时从点出发，并同时在点汇合。小狗的速度最快是Grant的两倍。当主人从一个点以直线走向另一个点时，Pandog跑向一个他感兴趣的景点。Pandog每次与主人相遇之前最多只去一个景点。已知n个定点的坐标和m个景点的坐标。你的任务是：为Pandog寻找一条路线（有可能与主人的路线部分相同），使它能够游览最多的景点，并能够准时与主人在给定地点相遇或者汇合。 将顶点分成两类由于“当主人从一个点以直线走向另一个点时，Pandog跑向一个他感兴趣的景点”，并且主人的移动

5、路线是确定的，所以寻找一条路线可以看作确定在每一段路线上小狗的选择：或是跑向哪一个景点，或是和主人的路线重合。因此图中的点被自然的分成了两类：1.每一段路线2.景点定义边 由于在一个线段上，小狗只能跑向一个景点，所以景点是否可达，只和景点到线段两端点的距离有关，而小狗的速度最快是主人的两倍。由此得出线段的定义求求二分图的最大匹配二分图的最大匹配由于一条线段只能和一个景点发生关联，而一个景点也只在第一次访问的时候才有意义，因此任何两项关联都不会有任何交点，这显然满足了匹配的定义。两类顶点组成了一个二分图。使用匈牙利算法求最大匹配数及匹配方案 图的最小覆盖问题设D是图G的一个顶点子集，对于G的任一

6、顶点u，要末u是D集合的一个顶点元素，要末与D中的一个顶点相邻，那末D称为图G的一个覆盖集。若在D集中去除任何元素D不再是覆盖集，则覆盖集D是极小覆盖集。称G的所有覆盖集中顶点个数最少的覆盖集为最小覆盖集D0，一般图的最小覆盖问题是一个已被证明的NPC问题。换一句话说，一般图的最小覆盖问题，是没有有效算法的图论模型。所以，将一个实际问题抽象成最小覆盖问题，是没有任何意义和价值的。但是，如果问题可以抽象成二分图的最小覆盖问题，结局就不一样了。由于二分图的特殊性，二分图的最小覆盖问题存在多项式算法。二分图二分图最大匹配与最小覆盖的关系最大匹配与最小覆盖的关系在证明这个定理的过程中，要用到HallH

7、all婚姻定理婚姻定理： 1211GVVGVSVSP S 设 是一个偶图，顶集划分成 和， 中存在对于 的完备匹配的充要条件是，对于一切，都有。1931年Knig给出最大匹配与最小覆盖的关系定理如下： *GMKMK 在偶图 中，若是最大匹配，是最小覆盖集，则。例题：国际象棋例题：国际象棋一张大小为n*n的国际象棋棋盘，上面有一些格子被拿走了，棋盘规模n不超过200。马的攻击方向如下图，其中S处为马位置，标有X的点为该马的攻击点。你的任务是确定在这个棋盘上放置尽可能多的马，并使他们不互相攻击。求最小覆盖集的图论问题求最小覆盖集的图论问题将棋盘的每一个格子作为一个顶点，两点间直接可达（互可攻击）的

8、关系作为边。则题目所要求的就是在这样一张图中的寻找一个最大独立子集（即顶点集合中的任意两顶点都不相邻、且含顶点数最多）。由于对于任意一张图，其最大独立子集和最小覆盖集互为补集最大独立子集=n-最小覆盖集，所以本题也是一个求最小覆盖集的图论问题。 棋盘定义在攻击关系上是一个二分图 在一张国际象棋的棋盘上，白格和黑格相交错，一匹马只能从一个白格跳到一个黑格，或是从一个黑格跳到一个白格。必要条件：一个位置上的马只能攻击和其所在位置颜色不同的格子。即同一颜色的任意两个格子间不存在边。 棋盘格子按照颜色分成两个部分。 如果按照自上而下、由左而右的顺序给格子编号的话，在所有未被拿走的格子（i,j）中(1i

9、,jn，mapi,j=true)，同种颜色的格子必须满足如下条件：n为奇数，且(i-1)*n+j为奇数；n为偶数，且i和j的奇偶性不同；我们将所有同种颜色的格子组成X顶点集。显然X顶点集中每个顶点跳后位置的颜色是不同的，其中未被拿走的跳后位置组成Y顶点集。 通过二分图最大匹配计算问题解二分图的最大匹配数与最小覆盖数之间存在着对应的数量关系，而最大独立子集和最小覆盖集互为补集，因此我们可以通过求二分图的最大匹配数， 互不攻击情况下马的最多放置数目=未被拿走的格子数-最多匹配数 二分图的最佳匹配问题121122124,;,.,.,0nnijGV V EVx xxVy yyw x yMMW MW M

10、MG定义是加权完全偶图，权。如果有一完备匹配，对所有完备匹配，都有，则称为偶图的最佳匹配。由于引入了权，所以最佳匹配不能直接套用最大匹配算法进行求解。同时，由于对最佳匹配的定义是建立在完全加权二分图的基础上的，对于不完全图，可以通过引入权为0（或是其他不影响最终结果的值），使得二分图称为完全二分图，从而使用最佳匹配算法来解决。KM算法前的准备在介绍求最佳匹配的KM算法前，首先介绍一些相关的概念： 125:|,llll V GRxVyVl xl yw xyl vGExy xyE Gl xl yw xyEG 定义映射满足，成立，则称是偶图 的可行顶标；令称以 为边集的生成子图为“相等子图”，记做。

11、可以证明，Gl的完备匹配即为G的最佳匹配。 以此为基础，1955年Kuhn，1957年Munkres给出修改顶标的方法，使新的相等子图的最大匹配逐渐扩大，最后出现相等子图的完备匹配。 这就是KM算法。KM算法 1,(1)(2) ,(3),(4),min,(4)lllllx S y TlllGMVMMGMuSu TP STP STl va vSal xl yw xyl vl va vTl vll GGP STyyMy 选定初始可行顶标 ，在上选取一个初始匹配。若 中的顶皆为中边的端点，止，即为最佳匹配；否则，取中不与中边关联的顶 ，记。若转；若，取，其它。选中的一点 ，若 是中边的端点，且 ,

12、(3),( )(2)lzMSSz TTyGMR u yMME R，则，转；否则，取中可增广路径，令，转。一个例题某公司有工作人员x1,x2,xn ，他们去做工作y1,y2,yn ，每个人都能做其中的几项工作，并且对每一项工作都有一个固定的效率。问能否找到一种合适的工作分配方案，使得总的效率最高。要求一个人只能参与一项工作，同时一项工作也必须由一个人独立完成。不要求所有的人都有工作。一个实例Y1Y2Y3Y4Y5X135541X222022X324410X401100X512133若工人x完全不能参与工作y，则w(x,y)=0流程(1)首先，选取可行顶标l(v)如下： 123410,1,2,3,4

13、,5;max 3,5,5,4,15,max 2,2,0,2,22,max 2,4,4,1,04,max 0,1,1,0,01,max 1,2,1,3,33l yil xl xl xl xl x构造Gl，并求其最大匹配：（其流程过长，此处略）流程(2)其最终得到的最大匹配如图所示：1x5x4x3x2x1y2y3y4y5y图中粗点划线构成最大匹配。 流程(3)Gl中无完备匹配，故修改顶标。 443132,1234512345,min14,2,3,0,3;0,1,1,0,0lx S y Tux Sx x xTyyal xl yw xyxxxxxyyyyy由于，所以修改后的顶标为：流程(4)根据新的顶

14、标构造Gl ，并求其上的一个完全匹配如图所示： 1x5x4x3x2x1y2y3y4y5y图中粗点划线给出了一个最佳匹配，其最大权为4241314。题目完成。 例题例题 Roadseee EfCD请求出修改的最小代价。请求出修改的最小代价。 给定一个无向图给定一个无向图G0=（V0，E0，C），），V0为顶点为顶点集合集合,E0为边集合（无重边），为边集合（无重边），C为边权（非负整数）为边权（非负整数）。设。设n= |V0|，m= |E0|，E0中前中前n-1条边构成一棵生成树条边构成一棵生成树T。请将边权进行如下修改，即对于。请将边权进行如下修改，即对于eE，把，把Ce修改修改成成De（De

15、也为非负整数），使得树也为非负整数），使得树T成为图成为图G的一棵最的一棵最小生成树。修改的代价定义为：小生成树。修改的代价定义为：415234622357415234424334f=|6-4|+|2-2|+|5-3|+|7-4|+|3-3|+|2-4|+|4-4|=9初步分析初步分析l根据与树根据与树T T的关系的关系, ,我们可以把图我们可以把图G0 0中的边分成中的边分成树边与非树边两类。树边与非树边两类。l设设Pe表示边表示边e的两个端点之间的树的路径中边的两个端点之间的树的路径中边的集合。的集合。初步分析初步分析 如右图，如右图，uT，t1，t2，t3T，且，且t1，t2，t3连接了

16、连接了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

17、Du ，否则用否则用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初步分析初步分析 那问题就是求出

18、所有的那问题就是求出所有的使其满足以上不等式且：使其满足以上不等式且：vuDDvvuuCC vuvuCC 1miif最小。最小。 那么当那么当u可替换可替换v时，由不等式时，由不等式观察此不等式观察此不等式其中不等号右侧其中不等号右侧CvCu是一个已知量！是一个已知量！vuvuCC 大家或许会发现这个不等式似曾相识大家或许会发现这个不等式似曾相识! 这就是在求二分图最佳匹配的经典这就是在求二分图最佳匹配的经典KM算法中算法中不可或缺的一个不等式。不可或缺的一个不等式。 KM算法中，首先给二分图的每个顶点都设一个算法中，首先给二分图的每个顶点都设一个可行顶标，可行顶标，X结点结点i为为li，Y结

19、点结点j为为rj。从始至终，边权。从始至终，边权为为Wv,u的边的边(v,u)都需要满足都需要满足lv + ru Wv,u 。1234567建立两个互补的结点集合建立两个互补的结点集合X，Y。/Y结点结点j表示图表示图G0中中非树边非树边aj(ajT)。X结点结点i表示图表示图G0中中树边树边ai(aiT)。XY设这些结点均为实点。设这些结点均为实点。1234567XY 如果图如果图G0中，中，aj 可替换可替换ai，且，且CiCj0,则在则在X结点结点i和和Y结点结点j之间添加边之间添加边(i,j), 边权边权Wi,j=CiCj。1234567XY1234567XY 设这些边均为实边。设这些

20、边均为实边。1234567 在结点数少的一侧添加虚结点，使得在结点数少的一侧添加虚结点，使得X结点和结点和Y结结点的数目相等。点的数目相等。XY8 如果如果X结点结点i和和Y结点结点j之间没有边，则添加一条权之间没有边，则添加一条权值为值为0的虚边的虚边(i,j)。12345678XY算法分析算法分析,( , )iji jlrWi jX,( , )iji jlrWi jM,( , )Mi jiji jMi Xj YSWlr设完备匹配设完备匹配X的所有匹配边的权值和为的所有匹配边的权值和为SX，则则 对于图对于图G的任意一个完备匹配的任意一个完备匹配X，都有，都有 设设M为图为图G的最大权匹配，显然的最大权匹配，显然M也是完备匹配，也是完备匹配，则满足则满足 显然，此时的可行顶标之和取到最小值。显然，此时的可行顶标之和取到最小值。 因为虚结点因为虚结点Xi的匹配边肯定是权值为的匹配边肯定是权值为0的虚边，的虚边，所以所以li=0