图的最大权匹配

2006全国信息学奥林匹克

冬令营讲稿

两个复杂的经典问题NOI-SC刘汝佳目录后缀树的线性时间构造——Trie,后缀树,Ukkonen算法一般图的最大权匹配——二分图匹配、线性规划、Gabow算法为什么要学习这两个问题加深对相关知识和方法的认识和理解:字符串匹配、图论、线性规划其中包含很多巧妙的思路,很有启发性学习复杂算法是一个挑战.算法的背景、动机、出发点、步骤、正确性证明、复杂度分析、细节处理、程序实现等方面都需要仔细推敲PartII.一般图的最大权匹配一般图的最大权匹配特殊问题二分图最大匹配:基本理论和Hopcroft算法二分图最大权匹配:Kuhn-Munkres算法一般图最大匹配:Edmonds算法一般问题线性规划:几何意义与代数意义互补松弛定理与原始-对偶算法主算法：Edmonds算法与Gabow算法二分图最大匹配二分图：结点可以分为两部分X和Y，每部分内部无边相连匹配：无公共点的边集合未盖点：不与任何匹配边邻接的点最大匹配：包含边数最多的匹配XY增广路从未盖点开始经过非匹配边、匹配边、非匹配边……序列，最终通过一条非匹配边到达另一个未盖点非匹配边个数比匹配边个数多一如果把匹配边和非匹配边互换…匹配仍合法，但基数加一增广路定理匹配是最大匹配当且仅当不存在增广路这个定理适用于任意图011001011010匈牙利树思考：忽略虚线边会导致存在增广路却找不到吗？二分图最大匹配算法BFS找增广路：O(mn)寻找/增广时间均为O(m)最多找O(n)次Hopcroft算法：每次沿多条增广路同时增广每次寻找若干条结点不相交最短增广路每次的最短增广路集是极大的时间复杂度为思考4：每次一定能找到最短增广路吗？思考1：如何从未盖点出发找最短增广路？思考3：如何删除多余边和孤立点？Hopcroft算法可以证明：如果每次找到的最短增广路集是极大的，则只需要增广次关键：用O(m)时间找一个极大最短增广路集步骤1：用距离标号扩展匈牙利树，找到第一个未盖点时并不停止，把此时的距离标号设为上限。这样，找到的所有未盖点距离标号都相同步骤2：每次任取一个未盖点，沿着它对应的增广路增广，并删除它邻接的边，再删除孤立点思考2：这里的孤立点指什么？完全二分图的最大权完美匹配完全二分图，每条边有一个非负整数权值目标：求出权和最大的完美匹配特点：完美匹配容易求，但权最大的不易可行顶标：结点函数l，对任意弧(x,y)满足相等子图：G的生成子图，包含所有点，但只包含满足l(x)+l(y)=w(x,y)的所有弧(x,y)相等子图定理：如果相等子图有完美匹配，则该匹配是原图的最大权匹配证明：设M*是相等子图的完美匹配，则根据定义设M是原图的任意完美匹配，则关键：寻找好的可行顶标，使相等子图有完美匹配算法思想关键：寻找好的可行顶标，使相等子图有完美匹配思想：随便构造一个可行顶标（例如Y结点顶标为0，X结点的顶标为它出发所有弧的最大权值，然后求相等子图的最大匹配存在完美匹配，算法终止否则修改顶标使得相等子图的边变多，有更大机会存在完美匹配考虑相等子图不存在完美匹配时的情形Kuhn-Munkres算法如右图，相等子图的最大匹配基数为6，不是完美匹配算法在寻找增广路失败的同时得到了一棵匈牙利树虽然此匈牙利树并没有包含未盖点（因此没有找到增广路），但仍然含有重要信息Kuhn-Munkres算法设匈牙利树中的X结点集为S，Y结点集为T，则S到T没有边（否则匈牙利树可以继续生长）S到T的边都是非匹配边（想一想，为什么）但若把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图SSTTKuhn-Munkres算法把S中所有点的顶标同时减少一个相同整数a，则S到T中可能会有新边进入相等子图为了保证S-T的匹配边不离开相等子图，把T中所有点的顶标同时增加aSSTT-a+a为保证有新边进入，取如果S中每个顶标的实际减小值比这个值小则不会有新边进入；如果比这个值大则顶标将变得不可行Kuhn-Munkres算法设边(x,y)进入相同子图y是未盖点，则找到增广路y和S中的点z匹配，则把z和y分别加入S和T中每次修改顶标要么找到增广路，要么使匈牙利树增加两个结点因此一共需要O(n2)次修改顶标操作关键：快速修改顶标SSTT-a+a顶标的修改方法1：枚举S和T中的每个元素，根据定义计算最小值，每次修改的时间为O(n2)，总O(n4)方法2：对于T中的每个元素y，定义松弛量则a的计算公式变为顶标的快速修改每次增广后用O(n2)时间计算所有点的初始slack，由于每次生长匈牙利树时所有S-T弧的增量相同，因此修改每个slack值只需要常数时间，计算所有slack值需要O(n)时间每次增广后最多修改n次顶标，因此每次增广后修改顶标总时间降为O(n2)，总O(n3)结论：Kuhn-Munkres算法的总时间复杂度为O(n3)一般图的最大匹配增广路定理仍然成立匈牙利树：所有点标以0/1（奇偶）标号，则在任意时刻都不会要求结点标号改变奇偶性011001011010花朵一般图上可能出现标号奇偶性不符的情况blossom001110100xyw!!base花朵的收缩与花相连的其他边一定是非匹配边人工结点一定是偶结点（编号为0的结点）收缩图中的增广路(1)定理：如果收缩后的图有增广路，则原图也有。因此，收缩过程没有伪造增广路证明：设在增广路中人工结点u的下一个结点v和收缩前圈中的点w相邻，则不管w点在什么位置，都可以在圈中构造出增广路收缩图中的增广路(2)定理：如果原图有增广路，则收缩图也有。因此，收缩过程没有丢失增广路证明：原图中的增广路一定从花基处进入一个花朵，而离开花朵的边一定是非匹配边，与人工结点等价。表面图算法执行过程中在概念上的临时图称为表面图，它是若干花朵的集合每个花朵是奇数个结点构成的圈构成花朵的结点还可以是花朵每个花朵是层次结构，树根对应的花朵称为表面花朵，而其他内结点称为死花朵寻找增广路:方法1取消所有点标号，把一个未盖点标上0并放在队列中，然后每次取出一个i检查情况1：i是奇结点，则有匹配边(i,j)。若j有奇标号则contract(i,j)；否则如果j没有标号则标上偶标号，设pred(j)=i后把j加入队列情况2：i是偶结点，需要逐一检查它的所有邻边。对于每条边(i,j)，如果j有偶标号则执行contract(i,j)；否则如果j是未盖点则找到增广路；否则如果j没有标号则给它奇标号，设pred(j)=i后把j加入队列收缩操作contract(i,j)i和j的最近公共祖先b是花的基。确定基的同时也就找到了整个花收缩需要建立人工结点，把与花中点关联的所有其他边连接到人工结点，最后需要删除花中所有结点，展开时恢复问题1：每次操作的时间复杂度？问题2：算法总时间复杂度？如何求？寻找增广路:方法2若要真正的创建人工结点，删除/恢复原结点，程序比较麻烦，效率也不高还可以一般采取活跃标记法，除了记录每个点的奇偶标号外还给一个活跃标记参考方法：1-奇点2-偶点3-非活跃寻找增广路:方法2队列中只保存偶点。当检查i时发现另一个偶点j则发现了一个花朵。此时记录i和j被作为偶点和奇点时的父亲p0和p1，并沿路径i→b和j→b计算其他结点的p0和p1001110100jip0(i)p1(i)p1(j)p0(j)b方法2的思考(1)算法把活跃结点加到“偶点队列”中吗？算法判断花朵时如何处理检查活跃结点标记2遇到标记3标记3遇到标记3仍然设置p1(i)为j吗？0?111?1?3jij=p1(i)??b破坏了原来的p1(i)花朵不算方法2的思考(2)花朵的层次结构是怎样体现出来的？问题1：如何增广？问题2：需要记录非活跃点的花基吗？问题2：时间复杂度？O(n3)不需要小结引子：二分图最大匹配、匈牙利树二分图最佳匹配：可行顶标任意图最大匹配：带花匈牙利树下一站：线性规划与原始-对偶算法线性函数与线性约束n个变量x1,x2,….,xn的线性函数为线性约束线性等式线性不等式线性规划给定n个变量的m个线性约束，让这n个变量的木个线性函数最大化或最小化标准形式：不等式约束下最大化松弛形式：等式约束下最大化方便问题描述方便算法设计对偶问题标准问题(A,b,c)对偶问题(A,b,c)原始问题的每个约束关联了一个对偶变量互补松弛定理设x和y是原始问题和对偶问题的可行解，则它们分别为两个问题的最优解当且仅当换一种说法：原始问题的解x为最优解当且仅当存在对偶问题可行解y：再谈最小费用最大流问题考虑单源单汇网络的最小费用流问题两类约束分别引入对偶变量，则对偶问题为顶点势互补松弛条件由互补松弛定理，有容易得到顶点势可行的必要条件：它也是充分条件，只需令原始-对偶算法前面说过，只要顶点势可行，则z存在，互补松弛条件得以满足，因此问题的关键是维护顶点势始终可行原始对偶算法：从可行流x=0开始增广，只要随时存在结点势，则增广过程中得到的始终是该流量的最小费用流。初始势可以设为0，显然满足零流的最优性条件连续最短路算法令则原始-对偶算法只沿着的弧增广如只沿一条路增广，则此路一定是最短路，原始-对偶算法退化为连续最短路算法一般的原始-对偶算法求出满足条件的最大流，沿着此流一次性增广多条路径回忆：KM算法中的可行顶标是？？？匹配问题的整数规划模型设弧(i,j)的权为cij,xij=1表示该边是匹配边，xij=0表示非匹配边，则一般图的最大权匹配问题可以描述成0-1整数规划！！全幺模矩阵0-1整数规划问题是NP-难度的，但如果转化为线性规划问题，则可以像最小费用最大流一样用原始-对偶算法求解。幸运的是：有一类特殊整数规划问题与相应的线性规划问题等价如果一个矩阵A的任何子方阵的行列式的值都等于0，1或-1，则称A是全幺模的定理：如线性规划问题的矩阵A为全幺模矩阵，且该线性规划问题有最优解，则一定存在整数最优解一些矩阵有向图的关联矩阵为全幺模矩阵无向图的关联矩阵为全幺模矩阵当且仅当该图为二分图一般图如何“转化”为二分图呢？显然一般图的复杂之处在于奇圈，因此…设包含奇数个（至少3个点）点的点集（奇点集）为OS奇点集Sk包含2sk+1个结点匹配问题的线性规划模型加上刚才的约束，则整数约束可以去掉问题：约束有指数级别个，不能依次处理解决方法：对一类约束建立对偶变量，而不是逐一建立互补松弛条件对顶点约束和奇顶