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

《浅析二分图匹配在信息学竞赛中的应用.ppt》由会员分享，可在线阅读，更多相关《浅析二分图匹配在信息学竞赛中的应用.ppt（39页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、浅析二分图匹配在信息学竞赛中的应用长郡中学 王俊引言 二分图匹配是一类经典的图论算法，在近年来信息学竞赛中有广泛的应用。二分图和匹配的基础知识已经在前辈的集训队论文中有过介绍，本文主要通过一道例题研究其应用。例题 Roads请求出修改的最小代价。给定一个无向图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-2|+|5-3|+|7-4|+|3-3|+|2-4|+|4-4|=9初步分析l 根据与树T的关系,我们可以把图G0中的边分成树边与非树边两类。l 设Pe表示边e的两个端点之间的树的路径中边的集合。初步分析 如右图，u T，t1，t2，t3T，且t1，t2，t3连接了u的两个端点，所以Pu=t1，t2，t3。/l 那么用非树边u代替树边t1，t2，t3中任意一条都可以得到一棵新的生成树。l 而如果u的边权比所替换的边的边权更小的话，则可以得到一棵权值更小的生成树。l 那么要使原生成树T是一棵最小生成树，必须满足条件：Dt1 Du；Dt2 Du；Dt3 Duut1t2t3初步分析 如果边

3、v，u(u可替换v)，则必须满足 Dv Du，否则用u替换v可得到一棵权值更小的生成树T-v+u。/对边v，u如果满足条件u T，v Pu，则称u可替换v。初步分析 不等式DvDu中v总为树边，而u总为非树边。那么显然树边的边权应该减小(或不变)，而非树边的边权则应该增大(或不变)。设边权的修改量为，即 e=|DeCe|/当e T，e=DeCe,即De=Cee当e T，e=CeDe，即De=Cee初步分析 那问题就是求出所有的使其满足以上不等式且：最小。那么当u可替换v时，由不等式观察此不等式其中不等号右侧CvCu是一个已知量！大家或许会发现这个不等式似曾相识!这就是在求二分图最佳匹配的经典K

4、M算法中不可或缺的一个不等式。KM算法中，首先给二分图的每个顶点都设一个可行顶标，X结点i为li，Y结点j为rj。从始至终，边权为Wv,u的边(v,u)都需要满足lv+ru Wv,u。1234567我们来构造二分图G建立两个互补的结点集合X，Y。/Y结点j表示图G0中非树边aj(ajT)。X结点i表示图G0中树边ai(aiT)。X Y设这些结点均为实点。1234567X Y构造二分图G 如果图G0中，aj 可替换ai，且CiCj0,则在X结点i和Y结点j之间添加边(i,j),边权Wi,j=CiCj。1234567X Y1234567X Y 设这些边均为实边。1234567 在结点数少的一侧添加

5、虚结点，使得X结点和Y结点的数目相等。构造二分图GX Y8 如果X结点i和Y结点j之间没有边，则添加一条权值为0的虚边(i,j)。12345678构造二分图GX Y算法分析设完备匹配X的所有匹配边的权值和为SX，则 对于图G的任意一个完备匹配X，都有 设M为图G的最大权匹配，显然M也是完备匹配，则满足 显然，此时的可行顶标之和取到最小值。因为虚结点Xi的匹配边肯定是权值为0的虚边，所以li=0。同理对于虚结点Yj，rj=0。显然，SM即是满足树T是图G0的一棵最小生成树的最小代价。那么问题就转化为求图G的最大权完备匹配M，即可用KM算法求解。算法分析问题解决复杂度分析 我们来分析一下该算法的时

6、间复杂度。l预处理的时间复杂度为O(|E|)lKM算法的时间复杂度为O(|V|E|)由于图G是二分完全图。|V|=2maxn 1,m n+1=O(m)|E|=|V|2=O(m2)所以算法总时间复杂度为O(m3)。用KM算法解此题在构图时添加了许多虚结点和虚边，但其并没有太多实际意义。思考 那么，算法中是否存在大量冗余呢？还有没有优化的余地呢？下面就介绍一种更优秀的 算法！前面用KM算法解此题时构造了一个边上带有权值的二分图。其实不妨换一种思路，将权值由边转移到点上，或许会有新的发现。匹配算法分析 答案是肯定的，如果不添加这些虚结点和虚边，可以得到更好的算法。1 12 23 34 4567同样建

7、立两个互补的结点集合X，Y。构造二分图GX YX结点i表示树边ai(aiT)，Y结点j表示任意边aj(ajV0)。1 12 23 34 4567 如果图G0中，aj 可替换ai，且CiCj0,则在X结点i和Y结点j之间添加边(i,j)。构造二分图GX Y1 12 23 34 4567 在X结点i和Y结点i之间添加边(i,i)。构造二分图GX Y1 12 23 34 4567 给每个Y结点i一个权值Ci。如果点i被匹配则得到权值Ci，否则得到权值0。C3C2C1C4C5C6C7构造二分图GX Y算法分析引理对于图G中的任何一个完备匹配M，都可以在图G中找到一个唯一的完备匹配M与其对应，且SM=S

8、M。对于图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。1 12 23 34 456712345678图G 图G5267324225 0边权为2的匹配边(1,7)有匹配边(1,7)与其对应边权为0的匹配边(2,8)边权为2的匹配边(3,5)边权为5的匹配边(4,6)有匹配边(

9、2,2)与其对应有匹配边(3,5)与其对应有匹配边(4,6)与其对应X YX Y1 12 23 34 456712345678图G 图G5267324225 0图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 YX Y算法分析 因为SM+SM=。所以当SM取到最大值时，SM取到最小值。又因为M和M均为完备匹配，所以图G的最大权最大匹配就对应了图G最小权完备匹配。那么问题转化为求图G的最小权完备匹配。算法分析 由于图G

10、的权值都集中在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复杂度分析下面来分析一下该算法的时间复杂度。算法中执行了

11、如下操作：3 更新M；O(n)2 询问是否存在q的某个邻结点p为可匹配点；O(mn)=O(n3)1 将所有Y结点按权值大小非降序排列；O(mlog2m)=O(n2log2n)4 更新R以及Path;O(n3)复杂度分析 前三个操作复杂度都显而易见，下面讨论操作4的时间复杂度。如果某个点为可匹配点，则它的路径必然为 i0j1i1j2i2 jk ik(k0),其中i0为未匹配点而且(jt,it)(t 1,k)为匹配边。i0j1i1j2i2jkik复杂度分析 也就是说我们在更新R和Path时只需要处理X结点和已匹配的Y结点以及它们之间的边构成的子二分图。显然任意时刻图G的匹配边数都不超过n-1，所以

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