浅析二分图匹配在信息学竞赛中的应用

浅析二分图匹配在信息学竞赛中的应用长郡中学王俊引言二分图匹配是一类经典的图论算法，在近年来信息学竞赛中有广泛的应用。二分图和匹配的基础知识已经在前辈的集训队论文中有过介绍，本文主要通过一道例题研究其应用。[例题]RoadseeeEfCD请求出修改的最小代价。给定一个无向图G0=（V0，E0，C），V0为顶点集合,E0为边集合（无重边），C为边权（非负整数）。设n=|V0|，m=|E0|，E0中前n-1条边构成一棵生成树T。请将边权进行如下修改，即对于e∈E，把Ce修改成De（De也为非负整数），使得树T成为图G的一棵最小生成树。修改的代价定义为：415234622357415234424334f=|6-4|+|2-2|+|5-3|+|7-4|+|3-3|+|2-4|+|4-4|=9初步分析根据与树T的关系,我们可以把图G0中的边分成树边与非树边两类。设Pe表示边e的两个端点之间的树的路径中边的集合。初步分析如右图，u∈T，t1，t2，t3∈T，且t1，t2，t3连接了u的两个端点，所以Pu={t1，t2，t3}。/那么用非树边u代替树边t1，t2，t3中任意一条都可以得到一棵新的生成树。而如果u的边权比所替换的边的边权更小的话，则可以得到一棵权值更小的生成树。那么要使原生成树T是一棵最小生成树，必须满足条件：Dt1≤Du；Dt2≤Du；Dt3≤Duut1t2t3初步分析如果边v，u(u可替换v)，则必须满足Dv≤Du，否则用u替换v可得到一棵权值更小的生成树T-v+u。/对边v，u如果满足条件u∈T，v∈Pu，则称u可替换v。初步分析不等式Dv≤Du中v总为树边，而u总为非树边。那么显然树边的边权应该减小(或不变)，而非树边的边权则应该增大(或不变)。设边权的修改量为Δ，即Δe=|De－Ce|/当e∈T，Δe=De－Ce,即De=Ce＋Δe当e∈T，Δe=Ce－De，即De=Ce－Δe初步分析那问题就是求出所有的Δ使其满足以上不等式且：vuDDvvuuCCvuvuCC1miif最小。那么当u可替换v时，由不等式观察此不等式其中不等号右侧Cv－Cu是一个已知量！vuvuCC大家或许会发现这个不等式似曾相识!这就是在求二分图最佳匹配的经典KM算法中不可或缺的一个不等式。KM算法中，首先给二分图的每个顶点都设一个可行顶标，X结点i为li，Y结点j为rj。从始至终，边权为Wv,u的边(v,u)都需要满足lv+ru≥Wv,u。1234567我们来构造二分图G建立两个互补的结点集合X，Y。/Y结点j表示图G0中非树边aj(aj∈T)。X结点i表示图G0中树边ai(ai∈T)。XY设这些结点均为实点。1234567XY构造二分图G如果图G0中，aj可替换ai，且Ci－Cj0,则在X结点i和Y结点j之间添加边(i,j),边权Wi,j=Ci－Cj。1234567XY1234567XY设这些边均为实边。1234567在结点数少的一侧添加虚结点，使得X结点和Y结点的数目相等。构造二分图GXY8如果X结点i和Y结点j之间没有边，则添加一条权值为0的虚边(i,j)。12345678构造二分图GXY算法分析,(,)ijijlrWijX,(,)ijijlrWijM,(,)MijijijMiXjYSWlr设完备匹配X的所有匹配边的权值和为SX，则对于图G的任意一个完备匹配X，都有设M为图G的最大权匹配，显然M也是完备匹配，则满足显然，此时的可行顶标之和取到最小值。因为虚结点Xi的匹配边肯定是权值为0的虚边，所以li=0。同理对于虚结点Yj，rj=0。1mMijijiiXjYiXijYjiSlrlrf且为实点且为实点显然，SM即是满足树T是图G0的一棵最小生成树的最小代价。那么问题就转化为求图G的最大权完备匹配M，即可用KM算法求解。算法分析复杂度分析我们来分析一下该算法的时间复杂度。预处理的时间复杂度为O(|E|)KM算法的时间复杂度为O(|V||E|)由于图G是二分完全图。|V|=2max{n–1,m–n+1}=O(m)|E|=|V|2=O(m2)所以算法总时间复杂度为O(m3)。用KM算法解此题在构图时添加了许多虚结点和虚边，但其并没有太多实际意义。思考那么，算法中是否存在大量冗余呢？还有没有优化的余地呢？下面就介绍一种更优秀的算法！前面用KM算法解此题时构造了一个边上带有权值的二分图。其实不妨换一种思路，将权值由边转移到点上，或许会有新的发现。匹配算法分析答案是肯定的，如果不添加这些虚结点和虚边，可以得到更好的算法。11223344567同样建立两个互补的结点集合X'，Y'。构造二分图G'X'Y'X'结点i表示树边ai(ai∈T)，Y'结点j表示任意边aj(aj∈V0)。11223344567如果图G0中，aj可替换ai，且Ci－Cj0,则在X'结点i和Y'结点j之间添加边(i,j)。构造二分图G'X'Y'11223344567在X'结点i和Y'结点i之间添加边(i,i)。构造二分图G'X'Y'11223344567给每个Y'结点i一个权值Ci。如果点i被匹配则得到权值Ci，否则得到权值0。C3C2C1C4C5C6C7构造二分图G'X'Y'算法分析iiaTC设[引理]对于图G中的任何一个完备匹配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'中的一条匹配边(i，j)这里将介绍如何找到图G中匹配M对应的图G'中匹配M'。1122334456712345678图G图G'52673242250边权为2的匹配边(1,7)有匹配边(1,7)与其对应边权为0的匹配边(2,8)边权为2的匹配边(3,5)边权为5的匹配边(4,6)有匹配边(2,2)与其对应有匹配边(3,5)与其对应有匹配边(4,6)与其对应X'Y'XY1122334456712345678图G图G'52673242250图G中这个完备匹配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=20X'Y'XY算法分析因为SM+SM'=μ。所以当SM取到最大值时，SM'取到最小值。又因为M和M'均为完备匹配，所以图G的最大权最大匹配就对应了图G'最小权完备匹配。那么问题转化为求图G'的最小权完备匹配。算法分析由于图G'的权值都集中在Y'结点上，所以SM'的值只与Y'结点中哪些被匹配到有关。那么可以将所有的Y'结点按照权值大小非降序排列，然后每个X'结点都尽量找到权值较小的Y'结点匹配。算法分析用R来记录可匹配点，如果X'结点i∈R，则表示i未匹配，或者从某个未匹配的X'结点有一条可增广路径到达点i，其路径用Pathi来表示。设Bj表示Y'结点j的邻结点集合，Y'结点j能找到匹配当且仅当存在点i，i∈Bj且i∈R。下面给出算法的流程：将Y'结点非降序排列初始化M'，P和Pathj←1q←Y'的第j个结点存在q的某个邻结点p为可匹配点更新M'，R和Pathjmj←j+1结束NNYY复杂度分析下面来分析一下该算法的时间复杂度。算法中执行了如下操作：3更新M'；O(n)2询问是否存在q的某个邻结点p为可匹配点；O(mn)=O(n3)1将所有Y'结点按权值大小非降序排列；O(mlog2m)=O(n2log2n)4更新R以及Path;O(n3)复杂度分析前三个操作复杂度都显而易见，下面讨论操作4的时间复杂度。如果某个点为可匹配点，则它的路径必然为i0→j1→i1→j2→i2→…→jk→ik(k≥0),其中i0为未匹配点而且(jt,it)(t∈[1,k])为匹配边。i0j1i1j2i2jkik复杂度分析也就是说我们在更新R和Path时只需要处理X'结点和已匹配的Y'结点以及它们之间的边构成的子二分图。显然任意时刻图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)，所以该算法相对于算法一O(m3)=O(n6)的复杂度，在效率上有了巨大的飞跃。回顾通过对最小生成树性质的分析得到一组不等式Dv≤Du。将不等式变形后，通过对其观察，联想到了解决二分图最佳匹配经典的KM算法，即得到了算法一。正是通过猜想将权值由图中的边转移到顶点上，重新构造二分图，才得到了更为优秀的算法二！总结信息学竞赛中的各种题目，往往都需要通过对题目的仔细观察，构造出合适的数学模型，然后通过对题目以及模型的进一步分析，挖掘出问题的本质，进行大胆的猜想，转化模型，设计优秀的算法解决问题。结语仔细观察大胆猜想认真分析