图论课件--最小生成树.ppt

本次课主要内容
最小生成树
(一)、克鲁斯克尔算法
(二)、管梅谷的破圈法
(三)、Prim算法
(四)、计算机中的树简介
*
第一页，共34页。
最小连接问题：
交通网络中，常常关注能把所有站点连接起来的生成树，使得该生成树各边权值之和为最小。例如：
假设要在某地建造5个工厂，拟修筑道路连接这5处。经勘探，其道路可按下图的无向边铺设。现在每条边的长度已经测出并标记在图的对应边上，如果我们要求铺设的道路总长度最短，这样既能节省费用 ，又能缩短工期 ，如何铺设？
v1
v2
v3
v4
v5
1
2
2
4
3
4
5
5
*
第二页，共34页。
v1
v2
v3
v4
v5
1
2
2
3
不难发现：最小代价的连接方式为：
最小连接问题的一般提法为：
在连通边赋权图G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。
(一)、克鲁斯克尔算法
*
第三页，共34页。
克鲁斯克尔(Kruskal):1928年生，一家3弟兄都是数学家，1954年在普林斯顿大学获博士学位，导师是ErdÖs,他大部分研究工作是数学和语言学，主要在贝尔实验室工作。1956年发表包含克鲁斯克尔算法论文，使他名声大振。
1、算法思想
从G中的最小边开始，进行避圈式扩张。
2、算法
(1)、选择边e1,使得其权值最小；
(2)、若已经选定边e1, e2,…, ek, 则从E-｛ e1, e2,…, ek ｝中选择边ek+1,使得：
(a)、G[e1, e2,…, ek+1]为无圈图
(b)、ek+1的权值w(ek+1)尽可能小。
*
第四页，共34页。
(3)、当(2)不能进行时，停止。
例1 用克鲁斯克尔算法求下图的最小生成树。
3
v7
2
1
5
4
6
7
8
9
10
11
12
v1
v2
v3
v4
v5
v6
v8
*
第五页，共34页。
解：过程如下：
1
v5
v8
2
1
v1
v5
v8
3
2
1
v1
v4
v5
v8
3
v7
2
1
5
v1
v4
v5
v8
3
v7
2
1
5
6
v1
v4
v5
v8
v3
*
第六页，共34页。
3
v7
2
1
5
6
v1
v4
v5
v8
v3
v6
8
3
v7
2
1
5
6
v1
v4
v5
v8
v3
v6
8
v2
9
2、算法证明
定理1 由克鲁斯克尔算法得到的任何生成树一定是最小生成树。
证明：设G是一个n阶连通赋权图，用T*=G[｛e1,e2,…,en-1｝]表示由克鲁斯克尔算法得到的一棵生成树，我们证明：它是最小生成树。
*
第七页，共34页。
设T是G的一棵最小生成树。若T*≠T
由克鲁斯克尔算法容易知道：T∩T*≠Φ。
于是令f (T)= k 表示T*中的边ei不在T中的最小i值。即可令T=G[｛e1,e2,…,ek-1, e'k,…,e'n｝]
考虑：T∪ek ,则由树的性质，它必然为G中圈。
作 T1= T ∪ek- e ,容易知道：T1还为G的一棵生成树。
设e是圈T ∪ek中在T中，但不在T*中的边。
由克鲁斯克尔算法知道：
所以：
这说明T1是最小树，但这与f(T)的选取假设矛盾！所以：T = T*.
*
第八页，共34页。
例2 在一个边赋权G中，下面算法是否可以产生有最小权值的生成路？为什么？
算法: (1) 选一条边e1,使得w(e1)尽可能小；
(2) 若边e1,e2,…,ei已经选定，则用下述方法从E\｛e1,..,ei｝中选取边ei+1：
(a) G[｛ e1,e2,…,ei ,ei+1｝]为不相交路之并；
(b) w(ei+1)是满足(a)的尽可能小的权。
(3)当 (2)不能继续执行时停止。
解：该方法不能得到一条最小生成路。
*
第九页，共34页。
例如，在下图G中我们用算法求生成路：
3
1
2
2
3
4
3
6
6
7
9
10
用算法求出的生成路为：
1
2
2
6
9
3
*
第十页，共34页。