最小生成树问题的拓展
   安徽省芜湖一中汪汀
摘要 本文主要论述最小生成树问题中的两类拓展——最小度限制生成树和次小生成树。首
先分别介绍了这两类拓展问题的模型，然后提出了求解这两类问题的算法，最后，通过一些
例子分析其在实际问题中的应用。
关键字生成树拓展 度限制
正文
最小生成树是信息学竞赛中的经典问题，但近年来，竞赛中的题目不再局限于这类经典
模型，难度大大增加。为解决这些问题，我们必须对这些经典模型加以拓展。拓展的类型很
多，本文主要论述其中的两类——最小度限制生成树和次小生成树。
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,a2
1,……,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)=k
4.3 秘密的牛奶运输
Farmer John要把他的牛奶运输到各个销售点。运输过程中，可以先把牛奶运输到一些
销售点，再由这些销售点分别运输到其他销售点。
运输的总距离越小，运输的成本也就越低。低成本的运输是Farmer John所希望的。不过，
他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而
不是最小的。现在请你帮忙找到该运输方案。
[解答]本题是一个典型的求次小生成树的模型，可以把销售点看成图中的点，每两点间有一
条加权的无向边，边的权值为销售点间的距离。那么，直接套用上文所讲述的求次小生成树
的算法即可
5、结语
本文主要论述最小生成树问题的两个拓展——度限制生成树和k小生成树。其实最小生
成树问题的拓展是多种多样的，并非只有本文所提到的两种。当然，不仅仅是最小生成树，
A
B C
A (10, 60) B (10, 0) C (90, 0)
v0
A
B
C
0
0
0
60
80
100
IOI2004国家集训队论文汪汀
第 7 页共 7 页
其他经典模型亦是如此。这就需要我们在解决实际问题中，不能拘泥于经典模型，要因“题”
制宜，适当地对经典模型加以拓展，建立出符合题目本身特点的模型。
但是，这并不是说，经典模型已经被淘汰。因为一切拓展都是建立在原模型的基础上的，
两者之间有着密切的联系。这就需要我们一方面熟练掌握各种经典模型；另一方面，根据实
际情况，灵活运用，大胆创新。只有这样，才能在难度日益增加的信息学竞赛中，始终立于
不败之地。
参考文献：
[1] 网络算法与复杂性理论谢政 李建平著
[2] 数据结构（第二版） 严蔚敏 吴伟民著
[3] Introduction to Algorithms, Second Edition Thomas H. Cormen Charles E. Leiserson
Ronald L. Rivest Clifford Stein

评论