算法合集之《浅析二分图匹配在信息学竞赛中的应用》课件.ppt

1、长郡中学长郡中学 王俊王俊 二分图匹配是一类经典的图论算法，二分图匹配是一类经典的图论算法，在近年来信息学竞赛中有广泛的应用。在近年来信息学竞赛中有广泛的应用。二分图和匹配的基础知识已经在前辈二分图和匹配的基础知识已经在前辈的集训队论文中有过介绍，本文主要通过的集训队论文中有过介绍，本文主要通过一道例题研究其应用。一道例题研究其应用。eee EfCD请求出修改的最小代价。请求出修改的最小代价。给定一个无向图给定一个无向图G0=（V0，E0，C），），V0为顶点为顶点集合集合,E0为边集合（无重边），为边集合（无重边），C为边权（非负整数）为边权（非负整数）。设。设n=|V0|，m=|E0|，E

2、0中前中前n-1条边构成一棵生成树条边构成一棵生成树T。请将边权进行如下修改，即对于。请将边权进行如下修改，即对于eE，把，把Ce修改修改成成De（De也为非负整数），使得树也为非负整数），使得树T成为图成为图G的一棵最的一棵最小生成树。修改的代价定义为：小生成树。修改的代价定义为：415234622357415234424334f=|6-4|+|2-2|+|5-3|+|7-4|+|3-3|+|2-4|+|4-4|=9l根据与树根据与树T T的关系的关系,我们可以把图我们可以把图G0 0中的边分成中的边分成树边与非树边两类。树边与非树边两类。l设设Pe表示边表示边e的两个端点之间的树的路径中边

3、的两个端点之间的树的路径中边的集合。的集合。如右图，如右图，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 ；Dt

4、3 Duut1t2t3 如果边如果边v，u(u可替换可替换v)，则必须满足，则必须满足 Dv 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

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

6、标，X结点结点i为为li，Y结点结点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 设

7、这些边均为实边。设这些边均为实边。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的最大权匹配，显然的

8、最大权匹配，显然M也是完备匹配，也是完备匹配，则满足则满足 显然，此时的可行顶标之和取到最小值。显然，此时的可行顶标之和取到最小值。因为虚结点因为虚结点Xi的匹配边肯定是权值为的匹配边肯定是权值为0的虚边，的虚边，所以所以li=0。同理对于虚结点。同理对于虚结点Yj，rj=0。1mMijijii Xj Yi Xij YjiSlrlrf 且 为实点且 为实点 显然，显然，SM即是满足树即是满足树T是图是图G0的一棵最小生的一棵最小生成树的最小代价。那么问题就转化为求图成树的最小代价。那么问题就转化为求图G的最的最大权完备匹配大权完备匹配M，即可用，即可用KM算法求解算法求解。问题解决问题解决 我

9、们来分析一下该算法的时间复杂度。我们来分析一下该算法的时间复杂度。l预处理的时间复杂度为预处理的时间复杂度为O(|E|)lKM算法的时间复杂度为算法的时间复杂度为O(|V|E|)由于图由于图G是二分完全图。是二分完全图。|V|=2maxn 1,m n+1=O(m)|E|=|V|2=O(m2)所以算法总时间复杂度为所以算法总时间复杂度为O(m3)。用用KM算法解此题算法解此题在构图时添加了许多虚在构图时添加了许多虚结点和虚边，但其并没结点和虚边，但其并没有太多实际意义。有太多实际意义。思考思考 那么，算法中是否那么，算法中是否存在大量冗余呢？还有存在大量冗余呢？还有没有优化的余地呢？没有优化的余

10、地呢？下面就介绍一种更优秀的下面就介绍一种更优秀的 算法！算法！前面用前面用KM算法解此题时构造了一个边算法解此题时构造了一个边上带有权值的二分图。其实不妨换一种思路，上带有权值的二分图。其实不妨换一种思路，将权值由将权值由边边转移到转移到点点上，或许会有新的发现。上，或许会有新的发现。匹配 答案是肯定的，如果不添加这些虚结点和虚答案是肯定的，如果不添加这些虚结点和虚边，可以得到更好的算法。边，可以得到更好的算法。112 23344567同样建立两个互补的结点集合同样建立两个互补的结点集合X，Y。构造二分图构造二分图GXYX结点结点i表示树边表示树边ai(aiT)，Y结点结点j表示任意边表示任

11、意边aj(ajV0)。11223344567 如果图如果图G0中，中，aj 可替换可替换ai，且，且CiCj0,则在则在X结点结点i和和Y结点结点j之间添加边之间添加边(i,j)。构造二分图构造二分图GXY11223344567 在在X结点结点i和和Y结点结点i之间添加边之间添加边(i,i)。构造二分图构造二分图GXY11223344567 给每个给每个Y结点结点i一个权值一个权值Ci。如果点。如果点i被匹配则被匹配则得到权值得到权值Ci，否则得到权值否则得到权值0。C3C2C1C4C5C6C7构造二分图构造二分图GXYiiaTC设引理引理对于图对于图G中的任何一个完备匹配中的任何一个完备匹配

12、M，都可，都可以在图以在图G中找到一个唯一的完备匹配中找到一个唯一的完备匹配M与其对与其对应，且应，且SM=SM。对于图对于图G中的任何一个完备中的任何一个完备匹配匹配M，同样可以在图，同样可以在图G中找到一组以中找到一组以M为代表为代表的匹配与其对应，且的匹配与其对应，且SM=SM。对于图对于图G中虚结点中虚结点Xi的匹配边的匹配边(i，j)M，显然有，显然有Wi,j=0，对，对SM值没有影响。值没有影响。对于图对于图G中实结点中实结点Xi的匹配边的匹配边(i，j)M，若若Wi,j=0,则对应图则对应图G中的一条匹配边中的一条匹配边(i，i)若若Wi,j0,则对应图则对应图G中的一条匹配边中

13、的一条匹配边(i，j)这里将介绍如何找到图这里将介绍如何找到图G中匹配中匹配M对应的图对应的图G中匹配中匹配M。1122334456712345678图G图G52673242250边权为边权为2的匹配边的匹配边(1,7)有匹配边有匹配边(1,7)与其对应与其对应边权为边权为0的匹配边的匹配边(2,8)边权为边权为2的匹配边的匹配边(3,5)边权为边权为5的匹配边的匹配边(4,6)有匹配边有匹配边(2,2)与其对应与其对应有匹配边有匹配边(3,5)与其对应与其对应有匹配边有匹配边(4,6)与其对应与其对应XYXY1122334456712345678图G图G52673242250图图G中这个完备

14、匹配中这个完备匹配M为：为：(1,7),(2,8),(3,5),(4,6)SM=2+0+2+5=9图图G中对应的完备匹配中对应的完备匹配M为：为：(1,7),(2,2),(3,5),(4,6)SM=4+2+3+2=11SM=-SM=6+2+5+7=20XYXY 因为因为SM+SM=。所以当所以当SM取到最大值时，取到最大值时，SM取到最小值。取到最小值。又因为又因为M和和M均为完备匹配，所以图均为完备匹配，所以图G的最的最大权最大匹配就对应了图大权最大匹配就对应了图G最小权完备匹配。那最小权完备匹配。那么问题转化为求图么问题转化为求图G的最小权完备匹配。的最小权完备匹配。由于图由于图G的权值都

15、集中在的权值都集中在Y结点上，所结点上，所以以SM的值只与的值只与Y结点中哪些被匹配到有关。结点中哪些被匹配到有关。那么可以将所有的那么可以将所有的Y结点按照权值大小结点按照权值大小非降序排列，然后每个非降序排列，然后每个X结点都尽量找到权结点都尽量找到权值较小的值较小的Y结点匹配。结点匹配。用用R来记录可匹配点，如果来记录可匹配点，如果X结点结点iR，则表，则表示示i未匹配，或者从某个未匹配的未匹配，或者从某个未匹配的X结点有一条可增结点有一条可增广路径到达点广路径到达点i，其路径用，其路径用Pathi来表示。来表示。设设Bj表示表示Y结点结点j的邻结点集合，的邻结点集合，Y结点结点j能找能

16、找到匹配当且仅当存在点到匹配当且仅当存在点i，iBj且且i R。下面给出算法的流程：下面给出算法的流程：将将Y结点非降序排列结点非降序排列初始化初始化M，P和和Pathj 1q Y的第的第j个结点个结点存在存在q的某个邻结点的某个邻结点p为可匹配点为可匹配点更新更新M，R和和Pathjmj j+1结束结束NNYY下面来分析一下该算法的时间复杂度。下面来分析一下该算法的时间复杂度。算法中执行了如下操作：算法中执行了如下操作：33 更新更新M；O(n)2 2 询问是否存在询问是否存在q的某个邻结点的某个邻结点p为可匹配点；为可匹配点；O(mn)=O(n3)11 将所有将所有Y结点按权值大小非降序排

17、列；结点按权值大小非降序排列；O(mlog2m)=O(n2log2n)44 更新更新R以及以及Path;O(n3)前三个操作复杂度都显而易见，下面讨论前三个操作复杂度都显而易见，下面讨论操作操作4的时间复杂度。的时间复杂度。如果某个点为可匹配点，如果某个点为可匹配点，则它的路径必然为则它的路径必然为 i0j1i1j2i2 jk ik (k0),其中其中i0为未匹配点而且为未匹配点而且(jt,it)(t 1,k)为匹配边。为匹配边。i0j1i1j2i2jkik 也就是说我们在更新也就是说我们在更新R和和Path时只需要处理时只需要处理X结点和已匹配的结点和已匹配的Y结点以及它们之间的边构成结点以

18、及它们之间的边构成的子二分图。的子二分图。显然任意时刻图显然任意时刻图G的匹配边数都不超过的匹配边数都不超过n-1，所以该子图的点数为所以该子图的点数为O(n)，边数为，边数为O(n2)。所以该。所以该操作执行一次的复杂度即为操作执行一次的复杂度即为O(n2)，最多执行，最多执行n次，次，所以其复杂度为所以其复杂度为O(n3)。所以所以Y结点中的未匹配点是不可能出现在某结点中的未匹配点是不可能出现在某个个X结点结点i的的Pathi中的。中的。那么算法总的时间复杂度为：那么算法总的时间复杂度为：O(n2log2n)+O(n3)+O(n)+O(n3)=O(n3)因为因为O(m)=O(n2)，所以该

19、算法相对于，所以该算法相对于算法一算法一O(m3)=O(n6)的复杂度，在效率上有的复杂度，在效率上有了巨大的飞跃。了巨大的飞跃。l通过对最小生成树性质的通过对最小生成树性质的分析分析得到一组不得到一组不等式等式DvDu。l将不等式变形后，通过对其将不等式变形后，通过对其观察观察，联想到，联想到了解决二分图最佳匹配经典的了解决二分图最佳匹配经典的KM算法，即算法，即得到了算法一。得到了算法一。l正是通过正是通过猜想猜想将权值由图中的边转移到顶将权值由图中的边转移到顶点上，重新构造二分图，才得到了更为优秀点上，重新构造二分图，才得到了更为优秀的算法二！的算法二！信息学竞赛中的各种题目，往往都需要通过信息学竞赛中的各种题目，往往都需要通过对题目的仔细对题目的仔细观察观察，构造出合适的数学模型，然，构造出合适的数学模型，然后通过对题目以及模型的进一步后通过对题目以及模型的进一步分析分析，挖掘出问挖掘出问题的本质，进行大胆的题的本质，进行大胆的猜想猜想，转化模型，转化模型，设计优设计优秀的算法解决问题。秀的算法解决问题。仔细观察大胆猜想认真分析