国家集训队2004论文集 汪汀

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

1、最小生成树问题的拓展安徽省芜湖市第一中学汪汀回顾设G=(V,E,ω)是连通的无向图，图G中权值和最小的生成树称为最小生成树。Prim算法O(Vlog2V+E)Kruskal算法O(Elog2V)拓展问题本文主要讨论两类拓展问题最小度限制生成树次小生成树例一通讯线路某地区共有n座村庄，每座村庄的坐标用一对整数(x,y)表示，现在要在村庄之间建立通讯网络。通讯工具有两种，分别是需要铺设的普通线路和卫星设备。卫星设备数量有限，只能给k个村庄配备卫星设备。拥有卫星设备的村庄互相间直接通讯；铺设了线路的村庄之间也可以通讯。卫星分配是不受限制的。例一通讯线路问

2、怎样合理的分配卫星和铺设线路，使得在保证每两座村庄之间都可以直接或间接地通讯的前提下，铺设线路的总长度最短。范围：0≤k≤n≤5000A(10,60)B(10,0)C(90,0)D(90,60)方案一铺设线路总长120支线长度为60A(10,60)B(10,0)C(90,0)D(90,60)方案二铺设线路总长160支线长度为80图的模型ABCD80801001006060如果没有卫星设备，原题等价于求该图的最小生成树。ABCD80801001006060卫星设备ABCD80801001006060改造图的模型v0图中的一个生成树唯一对应一种可行方案

3、一种可行方案唯一对应图中的一个生成树A(10,60)B(10,0)C(90,0)D(90,60)v0可行方案与生成树之间是一一对应的A(10,60)B(10,0)C(90,0)D(90,60)v0铺设线路的长度就是其对应生成树的权值和，生成树中与v0关联的点为分配有卫星设备的村庄A(10,60)B(10,0)C(90,0)D(90,60)v0原问题转化为：当DT(v0)=k时的权值和最小的生成树这就是最小度限制生成树的模型最小度限制生成树设G=(V,E,ω)是连通的无向图，v0∈V是特别指定的一个顶点,k为给定的一个正整数。如果T是G的一个生成树

4、且dT(v0)=k，则称T为G的k度限制生成树。G中权值和最小的k度限制生成树称为G的最小k度限制生成树。明确几个概念T为图G的一个生成树，T+a-b记作(+a,-b)，如果T+a-b仍然是一个生成树，则称(+a,-b）是T的一个可行交换。T为图G的一个生成树，由T进行一次可行交换得到的新的生成树所组成的集合，称为T的邻集,记为N(T)。定理定理：设T是图G的最小k度限制树，E0是G中与v0有关联的边的集合，E1=E0E(T)，E2=E(T)E0，A={(+a,-b)

5、a∈E1,b∈E2}，设ω(a’)－ω(b’)=min{ω(a)－ω(b)

6、

7、(+a,-b)∈A}，则T+a’-b’是G的一个最小k+1度限制生成树。即最小p+1度限制生成树属于最小p度限制生成树的邻集。假设我们已经得到了最小p度限制生成树，如何通过它来求最小p+1度限制生成树呢？由定理可知最小p+1度限制生成树属于最小p度生成树的邻集，因此它可以通过枚举最小p度生成树上的一次可行交换求得。为了使v0的度增加，枚举的可行交换中必须有一条边与v0关联。如图，假设我们已经得到了v0点度为2时的最小生成树，现在要求v0度为3时的最小生成树。我们枚举于V0关联且不在树上边，分别添加到树上，例如：这样就形成了一个环。只有删除环上的边，

8、才能保证得到的仍然是生成树为了使V0的度增加，图中两条边红色的边是不能删除的删去边的权值越大，所得到的生成树的权值和就越小，因此，需要找到环上可删除的权值最大的边并将其删除。简单的枚举时间复杂度非常高！！！造成时间复杂度高的主要原因是有大量的重复计算造成时间复杂度高的主要原因是有大量的重复计算造成时间复杂度高的主要原因是有大量的重复计算红色的边被处理了两次动态规划！！！如何避免重复计算动态规划设最小p度限制生成树为T,T是无根树，为了简便，我们把v0作为该树的根。定义Father(v)为T中v的父结点，Father(v0)无意义。设Best(v)为

9、路径v0->v上与v0无关联且权值最大的边。动态规划Best(v)的状态转移方程为Best(v)=max(Best(Father(v)),ω(Father(v),v))边界条件为Best[v0]=-∞，Best[v’]=-∞

10、(v0,v’)∈E(T)。动态规划状态总共

11、V

12、个，而状态转移的时间复杂度为O(1),因而总的时间复杂度是O(V),即通过最小p度限制生成树求最小p+1度限制生成树的时间复杂度是O(V)。边界情况k>DG(v0),问题无解总存在k度限制生成树,k∈[1,DG(v0)]观察下图k≤2,不存在k度限制生成树将v0从图中删去，图中将

13、会出现3个连通分量而这3个连通分量必须通过v0来连接，k<3无解删去v0,图中出现m个连通分量,k=m是问题有解的最小值。