10算法合集之浅析二分图匹配在信息学竞赛中的应用

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,浅析二分图匹配在信息学竞赛中的应用,长郡中学 王俊,引言,二分图匹配是一类经典的图论算法，在近年来信息学竞赛中有广泛的应用。,二分图和匹配的根底知识已经在前辈的集训队论文中有过介绍，本文主要通过一道例题研究其应用。,例题,Roads,请求出修改的最小代价。,给定一个无向图G0=V0，E0，C，V0为顶点集合,E0为边集合无重边，C为边权非负整数。设n=|V0|，m=|E0|，E0中前n-1条边构成一棵生成树T。请将边权进行如下修改，即对于eE，把Ce修改成DeDe也为非负整数，使得树T成为图G的一棵最小生成树。修改的代价定义为：,4,1,5,2,3,4,6,2,2,3,5,7,4,1,5,2,3,4,4,2,4,3,3,4,f,=|6-4|+|2-2|+|5-3|+|7-4|+|3-3|+|2-4|+|4-4|=9,初步分析,根据与树,T,的关系,我们可以把图,G,0,中的边分成树边与非树边两类。,设,P,e,表示边,e,的两个端点之间的树的路径中边的集合。,初步分析,如右图，,u,T,，,t,1,，,t,2,，,t,3,T,，且,t,1,，,t,2,，,t,3,连接了,u,的两个端点，所以,P,u,=,t,1,，,t,2,，,t,3,。,/,那么用非树边u代替树边t1，t2，t3中任意一条都可以得到一棵新的生成树。,而如果u的边权比所替换的边的边权更小的话，那么可以得到一棵权值更小的生成树。,那么要使原生成树T是一棵最小生成树，必须满足条件：,D,t,1,D,u,；,D,t,2,D,u,；,D,t,3,D,u,u,t,1,t,2,t,3,初步分析,如果边v，u(u可替换v)，那么必须满足 Dv Du，否那么用u替换v可得到一棵权值更小的生成树T-v+u。,/,对边,v,，,u,如果满足条件,u,T,，,v,P,u,，,则称,u,可替换,v,。,初步分析,不等式,D,v,D,u,中,v,总为树边,，,而,u,总为非树边。,那么显然树边的边权应该减小(或不变)，而非树边的边权那么应该增大(或不变)。,设边权的修改量为,，即,e,=|,D,e,C,e,|,/,当,e,T,，,e,=,D,e,C,e,即,D,e,=,C,e,e,当,e,T,，,e,=,C,e,D,e,，即,D,e,=,C,e,e,初步分析,那问题就是求出所有的,使其满足以上不等式且：,最小。,那么当,u,可替换,v,时，由不等式,观察此不等式,其中不等号右侧CvCu是一个量！,大家或许会发现这个不等式似曾相识,!,这就是在求二分图最正确匹配的经典KM算法中不可或缺的一个不等式。,KM,算法中，首先给二分图的每个顶点都设一个可行顶标，,X,结点,i,为,l,i,，,Y,结点,j,为,r,j,。从始至终，边权为,W,v,u,的边,(,v,u,),都需要满足,l,v,+,r,u,W,v,u,。,1,2,3,4,5,6,7,我们来构造二分图,G,建立两个互补的结点集合,X,，,Y,。,/,Y,结点,j,表示图,G,0,中,非树边,a,j,(,a,j,T,),。,X,结点,i,表示图,G,0,中,树边,a,i,(,a,i,T,),。,X,Y,设这些结点均为实点。,1,2,3,4,5,6,7,X,Y,构造二分图,G,如果图G0中，aj 可替换ai，且CiCj0,那么在X结点i和Y结点j之间添加边(i,j),边权Wi,j=CiCj。,1,2,3,4,5,6,7,X,Y,1,2,3,4,5,6,7,X,Y,设这些边均为实边。,1,2,3,4,5,6,7,在结点数少的一侧添加虚结点，使得,X,结点和,Y,结点的数目相等。,构造二分图,G,X,Y,8,如果X结点i和Y结点j之间没有边，那么添加一条权值为0的虚边(i,j)。,1,2,3,4,5,6,7,8,构造二分图,G,X,Y,算法分析,设完备匹配X的所有匹配边的权值和为SX，那么,对于图,G,的任意一个完备匹配,X,，都有,设M为图G的最大权匹配，显然M也是完备匹配，那么满足,显然，此时的可行顶标之和取到最小值。,因为虚结点,X,i,的匹配边肯定是权值为,0,的虚边，所以,l,i,=0,。同理对于虚结点,Y,j,，,r,j,=0,。,显然，,S,M,即是满足树,T,是图,G,0,的一棵最小生成树的最小代价。那么问题就转化为求图,G,的最大权完备匹配,M,，即可用,KM,算法求解,。,算法分析,问题解决,复杂度分析,我们来分析一下该算法的时间复杂度。,预处理的时间复杂度为,O,(|,E,|),KM,算法的时间复杂度为,O,(|,V,|,E,|),由于图,G,是二分完全图。,|,V,|=2,max,n,1,m,n,+1=,O,(,m,),|,E,|=|,V,|,2,=,O,(,m,2,),所以算法总时间复杂度为,O,(,m,3,),。,用,KM,算法解此题在构图时添加了许多虚结点和虚边，但其并没有太多实际意义。,思考,那么，算法中是否存在大量冗余呢？还有没有优化的余地呢？,下面就介绍一种更优秀的 算法！,前面用,KM,算法解此题时构造了一个边上带有权值的二分图。其实不妨换一种思路，将权值由,边,转移到,点,上，或许会有新的发现。,匹配,算法分析,答案是肯定的，如果不添加这些虚结点和虚边，可以得到更好的算法。,1,1,2,2,3,3,4,4,5,6,7,同样建立两个互补的结点集合,X,，,Y,。,构造二分图,G,X,Y,X,结点,i,表示树边,a,i,(,a,i,T,),，,Y,结点,j,表示任意边,a,j,(,a,j,V,0,),。,1,1,2,2,3,3,4,4,5,6,7,如果图G0中，aj 可替换ai，且CiCj0,那么在X结点i和Y结点j之间添加边(i,j)。,构造二分图,G,X,Y,1,1,2,2,3,3,4,4,5,6,7,在,X,结点,i,和,Y,结点,i,之间添加边,(,i,i,),。,构造二分图,G,X,Y,1,1,2,2,3,3,4,4,5,6,7,给每个Y结点i一个权值Ci。如果点i被匹配那么得到权值Ci，否那么得到权值0。,C,3,C,2,C,1,C,4,C,5,C,6,C,7,构造二分图,G,X,Y,算法分析,引理,对于图,G,中的任何一个完备匹配,M,，都可以在图,G,中找到一个唯一的完备匹配,M,与其对应，且,S,M,=,S,M,。,对于图,G,中的任何一个完备匹配,M,，同样可以在图,G,中找到一组以,M,为代表的匹配与其对应，且,S,M,=,S,M,。,证明引理,对于图,G,中虚结点,X,i,的匹配边,(,i,，,j,),M,，显然有,W,i,j,=0,，对,S,M,值没有影响。,对于图,G,中实结点,X,i,的匹配边,(,i,，,j,),M,，,假设Wi,j=0,那么对应图G中的一条匹配边(i，i),假设Wi,j0,那么对应图G中的一条匹配边(i，j),这里将介绍如何找到图,G,中匹配,M,对应的图,G,中匹配,M,。,1,1,2,2,3,3,4,4,5,6,7,1,2,3,4,5,6,7,8,图,G,图,G,5,2,6,7,3,2,4,2,2,5,0,边权为,2,的匹配边,(1,7),有匹配边,(1,7),与其对应,边权为,0,的匹配边,(2,8),边权为,2,的匹配边,(3,5),边权为,5,的匹配边,(4,6),有匹配边,(2,2),与其对应,有匹配边,(3,5),与其对应,有匹配边,(4,6),与其对应,X,Y,X,Y,1,1,2,2,3,3,4,4,5,6,7,1,2,3,4,5,6,7,8,图,G,图,G,5,2,6,7,3,2,4,2,2,5,0,图,G,中这个完备匹配,M,为：,(1,7),(2,8),(3,5),(4,6),S,M,=2+0+2+5=9,图,G,中对应的完备匹配,M,为：,(1,7),(2,2),(3,5),(4,6),S,M,=4+2+3+2=11,S,M,=,-,S,M,=,6+2+5+7=20,X,Y,X,Y,算法分析,因为,S,M,+,S,M,=,。,所以当,S,M,取到最大值时，,S,M,取到最小值。,又因为,M,和,M,均为完备匹配，所以图,G,的最大权最大匹配就对应了图,G,最小权完备匹配。那么问题转化为求图,G,的最小权完备匹配。,算法分析,由于图,G,的权值都集中在,Y,结点上，所以,S,M,的值只与,Y,结点中哪些被匹配到有关。,那么可以将所有的,Y,结点按照权值大小非降序排列，然后每个,X,结点都尽量找到权值较小的,Y,结点匹配。,算法分析,用R来记录可匹配点，如果X结点iR，那么表示i未匹配，或者从某个未匹配的X结点有一条可增广路径到达点i，其路径用Pathi来表示。,设,B,j,表示,Y,结点,j,的邻结点集合，,Y,结点,j,能找到匹配当且仅当存在点,i,，,i,B,j,且,i,R,。,下面给出算法的流程：,将,Y,结点非降序排列,初始化,M,，,P,和,Path,j,1,q,Y,的第,j,个结点,存在,q,的某个邻结点,p,为可匹配点,更新,M,，,R,和,Path,j,m,j,j,+1,结束,N,N,Y,Y,复杂度分析,下面来分析一下该算法的时间复杂度。,算法中执行了如下操作：,3,更新,M,；,O,(,n,),2,询问是否存在,q,的某个邻结点,p,为可匹配点；,O,(,mn,)=,O,(,n,3,),1,将所有,Y,结点按权值大小非降序排列；,O,(,mlog,2,m,),=,O,(,n,2,log,2,n,),4,更新,R,以及,Path,;,O,(,n,3,),复杂度分析,前三个操作复杂度都显而易见，下面讨论操作,4,的时间复杂度。,如果某个点为可匹配点，那么它的路径必然为,i0j1i1j2i2 jk ik (k0),其中i0为未匹配点而且(jt,it)(t 1,k)为匹配边。,i,0,j,1,i,1,j,2,i,2,j,k,i,k,复杂度分析,也就是说我们在更新,R,和,Path,时只需要处理,X,结点和已匹配的,Y,结点以及它们之间的边构成的子二分图。,显然任意时刻图,G,的匹配边数都不超过,n,-1,，所以该子图的点数为,O,(,n,),，边数为,O,(,n,2,),。所以该操作执行一次的复杂度即为,O,(,n,2,),，最多执行,n,次，所以其复杂度为,O,(,n,3,),。,所以,Y,结点中的未匹配点是不可能出现在某个,X,结点,i,的,Path,i,中的。,复杂度分析,那么算法总的时间复杂度为：,O,(,n,2,log,2,n,)+,O,(,n,3,)+,O,(,n,)+,O,(,n,3,)=,O,(,n,3,),因为,O,(,m,)=,O,(,n,2,),，所以该算法相对于算法一,O,(,m,3,)=,O,(,n,6,),的复杂度，在效率上有了巨大的飞跃。,回忆,通过对最小生成树性质的,分析,得到一组不等式,D,v,D,u,。,将不等式变形后，通过对其观察，联想到了解决二分图最正确匹配经典的KM算法，即得到了算法一。,正是通过猜测将权值由图中的边转移到顶点上，重新构造二分图，才得到了更为优秀的算法二！,总结,信息学竞赛中的各种题目，往往都需要通过对题目的仔细观察，构造出适宜的数学模型，然后通过对题目以及模型的进一步分析，挖掘出问题的本质，进行大胆的猜测，转化模型，设计优秀的算法解决问题。,结语,仔细观察,大胆猜测,认真分析,谢谢,