最小生成树问题的拓展   安徽省芜湖一中汪汀摘要 本文主要论述最小生成树问题中的两类拓展——最小度限制生成树和次小生成树。首先分别介绍了这两类拓展问题的模型，然后提出了求解这两类问题的算法，最后，通过一些例子分析其在实际问题中的应用。关键字生成树拓展 度限制正文最小生成树是信息学竞赛中的经典问题，但近年来，竞赛中的题目不再局限于这类经典模型，难度大大增加。为解决这些问题，我们必须对这些经典模型加以拓展。拓展的类型很多，本文主要论述其中的两类——最小度限制生成树和次小生成树。1 最小生成树1.1最小生成树的定义设 G=(V,E,ω)是连通的无向图，G 中权值和最小的生成树称为最小生成树。1.2求解最小生成树的算法求最小生成树，比较常用的算法有Prim算法和Kruskal算法。前者借助Fibonacci堆可以使复杂度降为O(Vlog2V+E)，后者一般应用于稀疏图，其时间复杂度为O(Elog2V)。2、最小度限制生成树2.1、最小度限制生成树的定义对于一个加权的无向图，存在一些满足下面性质的生成树：某个特殊的结点的度等于一个指定的数值。最小度限制生成树就是满足此性质且权值和最小的一棵生成树。把它抽象成数学模型就是：设 G=(V,E,ω)是连通的无向图，v0 ∈V是特别指定的一个顶点,k为给定的一个正整数。IOI2004国家集训队论文汪汀第 2 页共 7 页如果 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 度限制生成树，则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)≤ω(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)得Σ(ω(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=E0\E(T)，E2=E(T)\E0，A={(+a,-b)| a∈E1,b∈E2}，设ω(a’)－ω(b’)=min{ω(a)－ω(b)| (+a,-b)∈A}，则T+a’-b’是G的一个最小k+1度限制生成树。IOI2004国家集训队论文汪汀第 3 页共 7 页如何求最小k度限制生成树呢？首先考虑边界情况。先求出问题有解时k 的最小值：把v0点从图中删去后，图中可能会出现m 个连通分量，而这m 个连通分量必须通过v0来连接，所以，在图G 的所有生成树中dT(v0)≥m。也就是说，当k<m时，问题无解。再根据上述定理，得出算法的框架：下面分别考虑每一步首先，将 v0和与之关联的边分别从图中删去，此时的图可能不再连通，对各个连通分量，分别求最小生成树。接着，对于每个连通分量V’，求一点v1，v1∈V’,且ω(v0,v1)=min{ω(v0,v’)|v’∈V’}，则该连通分量通过边(v1,v0)与v0相连。于是，我们就得到了一个m度限制生成树，不难证明，这就是最小m度限制生成树。这一步的时间复杂度为O(Vlog2V+E)我们所求的树是无根树，为了解题的简便，把该树转化成以v0为根的有根树。假设已经得到了最小p度限制生成树，如何求最小p+1 度限制生成树呢？根据定理2，最小p+1度限制生成树肯定是由最小p度限制生成树经过一次可行交换(+a1,-b1)得到的。我们自然就有了一个最基本的想法——枚举！但是，简单的枚举，时间复杂度高达O(E2)，显然是不能接受的。深入思考不难发现，任意可行的交换，必定是一条边跟v0关联，另一条与v0无关，所以，只要先枚举与v0关联的边，再枚举另一条边，然后判断该交换是否可行，最后在所有可行交换中取最优值即可。于是时间复杂度降到了O(VE)，但这仍然不能令人满意。进一步分析，在原先的树中加入一条与v0相关联的边后，必定形成一个环。若想得到一棵p+1 度限制生成树，需删去一条在环上的且与v0无关联的边。删去的边的权值越大，则所得到的生成树的权值和就越小。如果每添加一条边，都需要对环上的边一一枚举，时间复杂度将比较高，因为有不少边重复统计多次（下图中红色的边统计了多次）。1 先求出最小m度限制生成树；2由最小m度限制生成树得到最小m+1度限制生成树;3 当dT(v0)=k时停止。IOI2004国家集训队论文汪汀第 4 页共 7 页这里，动态规划就有了用武之地。设Best(v)为路径v0—v上与v0无关联且权值最大的边。定义father(v)为v的父结点，动态转移方程：Best(v)=max(Best(father(v)),ω(father(v),v))，边界条件为Best[v0]=-∞，Best[v’]=-∞| (v0,v’)∈E(T)。状态共|V|个，状态转移的时间复杂度O(1)，所以总的时间复杂度为O(V)。故由最小p度限制生成树得到最小p+1度限制生成树的时间复杂度为O(V)。综上，求最小k度限制生成树算法总的时间复杂度为O(Vlog2V+E+kV)。3、次小生成树3.1、次小生成树的定义设 G=(V,E,w)是连通的无向图，T 是图G 的一个最小生成树。如果有另一棵树T1，满足不存在树T’,ω（T’）<ω（T1） ，则称T1是图G的次小生成树。3.2、求解次小生成树的算法约定：由T 进行一次可行交换得到的新的生成树所组成的集合，称为树T的邻集,记为N(T)。定理 3：设T是图G的最小生成树，如果T1满足ω(T1)=min{ω(T’)| T’∈N(T)},则T1是G的次小生成树。证明：如果 T1 不是G 的次小生成树，那么必定存在另一个生成树T’,T’=T 使得ω(T)≤ω(T’)<ω(T1)，由T1的定义式知T不属于N(T)，则E(T’)\E(T)={a1,a21,……,at}，E(T)\E(T’)={b1,b2,……,bt}，其中t≥2。根据引理1 知，存在一个排列bi1,bi2,……,bit，使得T+aj-bij仍然是G 的生成树，且均属于N(T),所以ω(aj)≥ω(bij)，所以ω(T’)≥ω(T+aj-bij)≥ω(T1)，故矛盾。所以T1是图G 的次小生成树。通过上述定理，我们就有了解决次小生成树问题的基本思路。首先先求该图的最小生成树T。时间复杂度O(Vlog2V+E)然后，求T的邻集中权值和最小的生成树，即图G 的次小生成树。如果只是简单的枚举，复杂度很高。首先枚举两条边的复杂度是O(VE)，再判断该交换是否可行的复杂度是O(V)，则总的时间复杂度是O(V2E)。这样的算法显得很盲目。经过简单的分析不难发现，每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。我们可以以此将复杂度降为O(VE)。这已经前进了一大步，但仍不够好。回顾上一个模型——最小度限制生成树，我们也曾面临过类似的问题，并且最终采用动态规划的方法避免了重复计算，使得复杂度大大降低。对于本题，我们可以采用类似的思想。首先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在IOI2004国家集训队论文汪汀第 5 页共 7 页树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。预处理所要的时间复杂度为O(V2)。这样，这一步时间复杂度降为O(V2)。综上所述，次小生成树的时间复杂度为O(V2)。4、实际问题中的应用4.1 野餐计划矮人虽小却喜欢乘坐巨大的轿车，轿车大到可以装下无论多少矮人。某天，N(N≤20)个矮人打算到野外聚餐。为了集中到聚餐地点，矮人A 要么开车到矮人B 家中，留下自己的轿车在矮人B 家，然后乘坐B 的轿车同行；要么直接开车到聚餐地点，并将车停放在聚餐地。虽然矮人的家很大，可以停放无数量轿车，但是聚餐地点却最多只能停放K 辆轿车。现在给你一张加权无向图，它描述了N 个矮人的家和聚餐地点，要你求出所有矮人开车的最短总路程。[解答]这是一个比较明显的度限制生成树的模型，可以把矮人的家和聚餐地看成图上的点，两个矮人家之间的距离看成一条带权的无向边，聚餐地为有度限制的点。需要注意的是，本题是求度不超过k的最小生成树，不过这并没有带来更大的难度，因为从算法的流程来看我们很容易得到度不超过k的所有最小度限制生成树。4.2 通讯线路某地区共有n座村庄( 1 £ n £ 5000)，每座村庄的坐标用一对整数(x, y)表示，其中0 £ x,y £ 10000。为了加强联系，决定在村庄之间建立通讯网络。通讯工具可以是需要铺设的普通线路，也可以是卫星设备。卫星设备数量有限，只能给一部分村庄配备。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。而互相间铺设了线路的村庄也可以通讯。现在有k台（0 £ k £ 100）卫星设备，请你编一个程序，计算出应该如何分配这k台卫星设备，才能使铺设线路最短，并保证每两座村庄之间都可以直接或间接地通讯。[解答]首先构造图，把村庄作为图中的点，村庄间的距离作为边。如果没有或只有一台卫星设备，就可以直接用最小生成树来解决。卫星设备的作用实际就是连接k 个点且代价为０，不妨设一个虚点v0，v0与原图中的每一个点连接一条代价为０的边，v0的度限制为k，再套用度限制生成树的算法即可。例如下图：IOI2004国家集训队论文汪汀第 6 页共 7 页则新构造的图为：其中，DT(v0)=k4.3 秘密的牛奶运输Farmer John要把他的牛奶运输到各个销售点。运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。运输的总距离越小，运输的成本也就越低。低成本的运输是Farmer John所希望的。不过，他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。现在请你帮忙找到该运输方案。[解答]本题是一个典型的求次小生成树的模型，可以把销售点看成图中的点，每两点间有一条加权的无向边，边的权值为销售点间的距离。那么，直接套用上文所讲述的求次小生成树的算法即可5、结语本文主要论述最小生成树问题的两个拓展——度限制生成树和k小生成树。其实最小生成树问题的拓展是多种多样的，并非只有本文所提到的两种。当然，不仅仅是最小生成树，AB CA (10, 60) B (10, 0) C (90, 0)v0ABC0006080100IOI2004国家集训队论文汪汀第 7 页共 7 页其他经典模型亦是如此。这就需要我们在解决实际问题中，不能拘泥于经典模型，要因“题”制宜，适当地对经典模型加以拓展，建立出符合题目本身特点的模型。但是，这并不是说，经典模型已经被淘汰。因为一切拓展都是建立在原模型的基础上的，两者之间有着密切的联系。这就需要我们一方面熟练掌握各种经典模型；另一方面，根据实际情况，灵活运用，大胆创新。只有这样，才能在难度日益增加的信息学竞赛中，始终立于不败之地。参考文献：[1] 网络算法与复杂性理论谢政 李建平著[2] 数据结构（第二版） 严蔚敏 吴伟民著[3] Introduction to Algorithms, Second Edition Thomas H. Cormen Charles E. LeisersonRonald L. Rivest Clifford Stein

评论