资源描述：
《论文国家队吴景岳》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、最小生成树算冻及其应用江苏省常州高级中学吴景岳【摘要】最小生成树是图论中的经典问题,也是一个重要部分，一般书上往往只介绍求最小生成树的算法，而忽略了更精彩的算法应川部分。本文将对最小生成树算法及其应川作全血的分析说明，使大家对此有更加深刻的认识。本文分三部分：一、基础篇，主要介绍基础概念、求最小生成树的一般算法和常用算法。二、应用篇，具体问题具体分析，侧重于思考和证明的过程。三、总结。【关键字】最小生成树【目录】一、基础篇1.定义2.求最小生成树的一般算法3.常用算法a)Kruskal算法b)Prim算法4・Maintain——1012003二、应用篇1.概述2•
2、例题a)RobotBOI2002b)北极通讯网络WaterlooUniversity2002三、总结笫1页共29页【正文】1.基础篇1.1定义在电路设计小，常常需要把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚，把所有n个插脚连接起来，只要用n・l根电线就可以了。在所有的连接方案中，我们通常对电线总长度最小的连接方案感兴趣。把问题转化为图论模型就是：一个无向连通图G=(V,E),V是插脚的集合，E是插脚两两之间所有可能的连接的集合。给每条边(u,v)—个权值w(u,v),表示连接它们所需的电线氏度。我们的目标就是找到一个无环的边集T,连接其中所有的点
3、且使总权值最小。既然T是连接所有点的无环边集，它一定是一棵树。因为这棵树是从图G中生成出来的，我们把它叫做生成树。如果一棵生成树在所有生成树屮总权值最小，我们就把它称作最小生成树。1.2求最小生成树的一般算法解决最小生成树问题有没有一般的方法呢？下而我们就介绍一种贪心算法。该算法设置了集合A,该集合一直是某最小生成树的子集。算法执行的每一步，都要决策是否把边(u,v)添加到集合A屮，能够添加的条件是保证AU{(u,v)}仍然是最小生成树的子集。我们称像(u,v)这样的边为A的安全边，或称这样的边对集合A是安全的。求最小生成树的一般算法流程如下：GENERIC-MS
4、T(Gfw)1・A—①2.whileA没有形成一棵生成树3・do找出A的一条安全边(u,v)4.A—AU{(u,v)}5・returnA一开始A为①，显然满足最小生成树子集的条件。之后，每一次循环都把一条A的安全边加入A中，A依然是最小生成树。本节的余下部分将提出一条确认安全边的规则(定理1),下一节将具体讨论运用这一规则寻找安全边的两个有效的算法。总权值图1一个图的割(S,V-S)首先定义几个概念。有向图G=(V,E)的割(S,V-S)是V的一个分划。当一条边(u,v)eE的一个端点属于S而另一端点属于V・S,我们说边(u,v)通过割(S,V・S)。若集合A中没
5、有边通过割，就说割不妨碍集合Ao如果某边是通过割的具有最小权值的边，则称该边为通过割的一条轻边。如图1,集合S中的结点为黑色结点，集合V・S中的结点为白色结点。连接白色和黑色结点的那些边为通过该割的边。从边上所标的权值看，边(d,c)为通过该割的唯一一条轻边。子集A包含阴影覆盖的那些边，注意，由于A屮没有边通过割，所以割(S,V-S)不妨碍Ao确认安全边的规则由下列定理给出。定理1设图G(V,E)是一无向连通图，且在E上定义了相应的实数值加权函数w,设A是E的一个子集且包含于G的某个最小生成树中，割(S,V・S)是G的不妨碍A的任意割且边(n,v)是穿过割(S,V
6、-S)的一条轻边，则边(u,v)对集合A是安全的。证明：设T是包含A的一最小生成树。如果T包含轻边(u,v),则T包含AU{(u,v)},证明就完成了。否则，可设法建'、/〔另一棵包含AU{(u,v)}的最小生成树F,(u,v)对集合A仍然是安全的。图2最小生成树「的建立图2示岀了最小生成树T'的建立。S屮的结点为黑色，V・S中的结点为白色，迦u,v)与T屮从u到v的通路P构成一回路。由于迦u,v)通过割(S,V-S),因此在T中的通路P上至少存在一条边也通过这个割。设(x,y)为满足此条件的边。因为割不妨碍A,所以迦x,y)不属于Ao又因为(x,y)处于T中从u
7、到v的唯一通路上，所以去掉边(x,y)就会把T分成两个子图。这时加入边(u,v)以形成一新的生成树T=(T-{(x,y)})U{(u,v)}o下一步我们证明F是一棵最小生成树。因为(u,v)是通过割(S,V-S)的一条轻边，且边(x,y)也通过割，所以有w(u,v)Ww(x,y),因此w(F)=w(T)-w(x,y)+w(u,v)寸VjWw(T)。但T是最小生成树，因此F必定也是最小生成树。乂因为T'包含AU{(u,v)},所以(u,v)对A是安全的。(证毕)通过定理1可以更好地了解算法GENERIC-MST在连通图G=(V,E)上的执行流程。在算法执行过程屮，集
8、合A始终是
