资源描述：
《算法合集之《最小生成树问题的拓展》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、IOI2004国家集训队论文汪汀最小生成树问题的拓展安徽省芜湖一中汪汀摘要本文主要论述最小生成树问题中的两类拓展——最小度限制生成树和次小生成树。首先分别介绍了这两类拓展问题的模型，然后提出了求解这两类问题的算法，最后，通过一些例子分析其在实际问题中的应用。关键字生成树拓展度限制正文最小生成树是信息学竞赛中的经典问题，但近年来，竞赛中的题目不再局限于这类经典模型，难度大大增加。为解决这些问题，我们必须对这些经典模型加以拓展。拓展的类型很多，本文主要论述其中的两类——最小度限制生成树和次小生成树。1最小生成树1.1最小生成树的定义设G=(V,E,ω)是连通的无向图，G中权值和最小
2、的生成树称为最小生成树。1.2求解最小生成树的算法求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。2、最小度限制生成树2.1、最小度限制生成树的定义对于一个加权的无向图，存在一些满足下面性质的生成树：某个特殊的结点的度等于一个指定的数值。最小度限制生成树就是满足此性质且权值和最小的一棵生成树。把它抽象成数学模型就是：设G=(V,E,ω)是连通的无向图，v0∈V是特别指定的一个顶点,k为给定的一个正整数。第1页共7页IOI2004国家集训队论
3、文汪汀如果T是G的一个生成树且dT(v0)=k，则称T为G的k度限制生成树。G中权值和最小的k度限制生成树称为G的最小k度生成树。2.2、求解最小度限制生成树的算法约定：T为图G的一个生成树，T+a-b记作(+a,-b)，如果T+a-b仍然是一个生成树，则称(+a,-b)是T的一个可行交换。引理1：设T1,T2是图G的两个不同的生成树，E(T1)E(T2)={a1,a2,……,an},E(T2)E(T1)={b1,b2,……,bn},则存在一个排序bi1,bi2,……,bin,使得T2+ej-fij(j=1,2,……,n)仍然是G的生成树。定理1：设T是G的k度限制生成树，
4、则T是G的最小k度限制生成树当且仅当下面三个条件同时成立：Ⅰ对于G中任何两条与v0关联的边所产生的T的可行交换都是不可改进的。Ⅱ对于G中任何两条与v0不关联的边所产生的T的可行交换都是不可改进的。Ⅲ对于T的任何两个可行交换(+a1,-b1)和(+a2,-b2)，若a1,b2与v0关联，b1,a2不于v0关联，则有ω(b1)+ω(b2)≤ω(a1)+ω(a2)证明：⑴必要性设T是最小k度限制生成树，则Ⅰ,Ⅱ显然成立。以下证明Ⅲ：由Ⅰ,Ⅱ可知如果(+a1,-b2)和(+a2,-b1)都是T的可行交换，则有ω(b2)≤ω(a1),ω(b1)≤ω(a2)，故ω(b1)+ω(b2)≤ω(
5、a1)+ω(a2);否则，或者(+a1,-b2)或者(+a2,-b1)不是T的’可行交换，根据引理1，T=T+{a1,a2}-{b1,b2}仍然是T的k度限制生成树，则ω’(T)≤ω(T),故ω(b1)+ω(b2)≤ω(a1)+ω(a2)。⑵充分性设T是k度限制生成树且满足Ⅰ,Ⅱ,Ⅲ，假如有另一个k度限制生成树T’，ω(T’)<ω(T)，设E(T’)E(T)={a1,a2,……，an}E(T)E(T’)={b1,b2,……，bn}显然有∑ω(ai)<∑ω(bi)，根据引理1，存在一个排列b1’,b2’,……,bn’，满足T+ai-bi’仍然是G的生成树。由ω(T’)<ω(T
6、)得∑(ω(bi’)－ω(ai))>0，因而，在T的这n个可行交换中，一定存在某个可以改进的交换（+ai,-bi’）。由于T满足Ⅰ,Ⅱ,则ai,bi’若同时与v0关联或不关联都是不可改进的。也就是说，ai和bi’中必定恰好有一个不与v0关联。不妨设ai与v0无关联，因为DT’(v0)也等于k，所以必存在另一个交换(+aj,-bj’),满足aj与v0关联，bj’与v0无关联，且(ω(bi’)－ω(ai))+(ω(bj’)－ω(aj))>0,此与Ⅲ矛盾。因此，T’是不存在的，即T是G的最小k度限制生成树。定理2：设T是G的最小k度限制生成树，E0是G中与v0有关联的边的集合，E1=
7、E0E(T)，E2=E(T)E0，A={(+a,-b)
8、a∈E1,b∈E2}，设ω(a’)－ω(b’)=min{ω(a)－ω(b)
9、(+a,-b)∈A}，则T+a’-b’是G的一个最小k+1度限制生成树。第2页共7页IOI2004国家集训队论文汪汀如何求最小k度限制生成树呢？首先考虑边界情况。先求出问题有解时k的最小值：把v0点从图中删去后，图中可能会出现m个连通分量，而这m个连通分量必须通过v0来连接，所以，在图G的所有生成树中dT(v0)≥m。也就是说，当k
