IOI2004国家集训队
论文
政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载
汪汀
第 1 页 共 7 页
最小生成树问题的拓展
安徽省芜湖一中 汪汀
摘要 本文主要论述最小生成树问题中的两类拓展——最小度限制生成树和次小生成树。首
先分别介绍了这两类拓展问题的模型，然后提出了求解这两类问题的算法，最后，通过一些
例子分析其在实际问题中的应用。
关键字 生成树 拓展 度限制
正文
最小生成树是信息学竞赛中的经典问题，但近年来，竞赛中的题目不再局限于这类经典
模型，难度大大增加。为解决这些问题，我们必须对这些经典模型加以拓展。拓展的类型很
多，本文主要论述其中的两类——最小度限制生成树和次小生成树。
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
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
来看我
们很容易得到度不超过 k的所有最小度限制生成树。
4.2 通讯线路
某地区共有 n座村庄( 1 £ n £ 5000)，每座村庄的坐标用一对整数(x, y)
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示，其中 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
浙公网安备 33021202002483