最小生成树模型与实验.doc

《最小生成树模型与实验.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、最优化模型与实验第六章最小生成树模型与实验树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。§6.1树与树的性质上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使用实例来说明。图6.1例6.1已知有五个城市，要在它们之间架设电话线，要求任何两个城市都可以互相通话（允许通过其它城市），并且电话线的根数最少。用五个点代表五个城市，如果在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可

2、以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。定义6.1一个无圈的连通图称为树.例6.2某大学的组织机构如下所示:第167页最优化模型与实验文科办公室教务处研究处理科办公室校行政办公室研究生院财务科数学系校长行政科物理系理工学院校教学办公室人事学院外语学院……如果用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的

3、性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。树的性质：（1）树必连通，但无回路（圈）；（2）个顶点的树必有条边；（3）树中任意两点间，恰有一条初等链；（4）树连通，但去掉任一条边，必变为不连通；（5）树无回路（圈），但不相邻顶点连一条边，恰得一回路（圈）。生成树与最小树定义6.2设图是图的生成子图，如果是一棵树，记，则称是的一棵生成树。定理6.1图有生成树的充分必要条件是图的连通的。证：必要性是显然的充分性：设是连通图。（i）如果不含圈，由定义6.1可知，本身就是一棵树，

4、从而是它自身的生成树。（ii）如果含圈，任取一圈，从圈中任意去掉一条边，得到图第167页最优化模型与实验的一个生成子图，如果不含圈，那么是的一棵生成树（因为易见是连通的）；如果仍含少量圈，那么从中任取一个圈，从圈中再任意去掉一条边，得到图的一个生成子图，如此重复，最终可以得到的一个生成子图，它不含圈，则是图的一棵生成树。§6.2最小生成树的实例与求解1图6.2e7由以上充分性的证明中，提供了一个寻求连通图的生成树的方法，称这种方法为“破圈法”。例6.4在图6.1中，用破圈法求出图的一棵

5、生成树解：取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉；如图6.3所示，此图是图6.2的一个生成子图，且为一棵树（无圈），所以我们找一棵生成树，其中，。不难发现，图的生成树不是唯一的，对于上例若这样做：取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。第167页最优化模型与实验图6.3图6.4如图的生成树还有另外一种方法“避圈法”，主要步骤是在图中任取一条边，找出一条不与构成圈的边，再找出不与构成圈的边。一般地，设已有，找出一条不与构成圈的边，重复这个过程，直到不能进行下去为止。这时，

6、由所有取出的边所构成的图是图的一棵生成树。定义6.2设是赋权图的一棵生成树，称中全部边上的权数之和为生成树的权，记为。即。(7.1)如果生成树的权是的所有生成树的权中最小者，则称是的最小生成树，简称为最小树。即（7.2）式中对的所有生成树取最小。求最小树通常用以下两种方法。（1）破圈法：在给定连通图中，任取一圈，去掉一条最大权边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条），在余图中（是图的生成子图）任取一圈，去掉一条最大权边，重复下去，直到余图中无圈为止，即可得到图的最小树。例

7、6.4用破圈法求图6.5的最小树。图6.5是一赋权图。第167页最优化模型与实验13512423图6.5，；，；，，，；，；，，，；，。解：取一圈去掉；取一圈去掉；取一圈去掉；取一圈去掉。如图6.6所示，得到一棵生成树，即为所求最小树，。（2）避圈法(Kruskal算法)：在连通图中，任取权值最小的一条边（若有两条或两条以上权相同且最小，则任取一条），在未选边中选一条权值最小的边，要求所选边与已选边不构成圈，重复下去，直到不存在与已选边不构成圈的边为止。已选边与顶点构成的图就是所求最小

8、树。算法的具体步骤如下：第一步：令，（空集）第二步：选一条边，且是使图中不含圈的所有边中权最小的边。如果这样的边不存在，由是最小树。第三步：把换成，返回第二步。例6.5用避圈法求图6.5的最小树。第167页最优化模型与实验2112图6.6解：在中权值最小的边有，从中任取一条；在中选取权值最小的边；在中权值最小边有，，从中任取一条边；在中选取；在中选取。但与都会与已选边构成圈，故停止，得到与图6.6一样的结果。最小生成树（minimalspanningtree,MST）模型概括为：给定网