国家集训队2005论文集 王俊

《国家集训队2005论文集 王俊》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、V0

3、，m=

4、E0

5、，E0中前n-1条边构成一棵生成树T。请将边权进行如下修改，即对于e∈E，把Ce修改成De（De也为非负整数），使得树T成为图G的一棵最小生成树。修改的代价定义为：4152346223574152344

6、24334f=

7、6-4

8、+

9、2-2

10、+

11、5-3

12、+

13、7-4

14、+

15、3-3

16、+

17、2-4

18、+

19、4-4

20、=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≤Duut

21、1t2t3初步分析如果边v，u(u可替换v)，则必须满足Dv≤Du，否则用u替换v可得到一棵权值更小的生成树T-v+u。/对边v，u如果满足条件u∈T，v∈Pu，则称u可替换v。初步分析不等式Dv≤Du中v总为树边，而u总为非树边。那么显然树边的边权应该减小(或不变)，而非树边的边权则应该增大(或不变)。设边权的修改量为Δ，即Δe=

22、De－Ce

23、/当e∈T，Δe=De－Ce,即De=Ce＋Δe当e∈T，Δe=Ce－De，即De=Ce－Δe初步分析那问题就是求出所有的Δ使其满足以上不等式且：最小。那么当u可替换v时，由不等式观察此不等式其中不等号右侧Cv－Cu是一个已知量！大

24、家或许会发现这个不等式似曾相识!这就是在求二分图最佳匹配的经典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－Cj>0,则在X结点i和Y结点j之间添加边(i,j),边权Wi,j=Ci－Cj。12345

25、67XY1234567XY设这些边均为实边。1234567在结点数少的一侧添加虚结点，使得X结点和Y结点的数目相等。构造二分图GXY8如果X结点i和Y结点j之间没有边，则添加一条权值为0的虚边(i,j)。12345678构造二分图GXY算法分析设完备匹配X的所有匹配边的权值和为SX，则对于图G的任意一个完备匹配X，都有设M为图G的最大权匹配，显然M也是完备匹配，则满足显然，此时的可行顶标之和取到最小值。因为虚结点Xi的匹配边肯定是权值为0的虚边，所以li=0。同理对于虚结点Yj，rj=0。显然，SM即是满足树T是图G0的一棵最小生成树的最小代价。那么问题就转化为求图G的最大

26、权完备匹配M，即可用KM算法求解。算法分析问题解决复杂度分析我们来分析一下该算法的时间复杂度。预处理的时间复杂度为O(

27、E

28、)KM算法的时间复杂度为O(

29、V

30、

31、E

32、)由于图G是二分完全图。

33、V

34、=2max{n–1,m–n+1}=O(m)

35、E

36、=

37、V

38、2=O(m2)所以算法总时间复杂度为O(m3)。用KM算法解此题在构图时添加了许多虚结点和虚边，但其并没有太多实际意义。思考那么，算法中是否存在大量冗余呢？还有没有优化的余地呢？下面就介绍一种更优秀的算法！前面用KM算法解此题时构造了一个边上带有权值的二分图。其实不妨换一种思路，将权值由边转移到点上，或许会有新的发现。匹配算法分

39、析答案是肯定的，如果不添加这些虚结点和虚边，可以得到更好的算法。11223344567同样建立两个互补的结点集合X'，Y'。构造二分图G'X'Y'X'结点i表示树边ai(ai∈T)，Y'结点j表示任意边aj(aj∈V0)。11223344567如果图G0中，aj可替换ai，且Ci－Cj>0,则在X'结点i和Y'结点j之间添加边(i,j)。构造二分图G'X'Y'11223344567在X'结点i和Y'结点i之间添加边(i,i)。构造二分图G'X'Y'11223344567给每个Y'结点i一个权值Ci。如果点i被匹配则