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

1 图论及其应用应用数学学院 2 本次课主要内容最小生成树(一)、克鲁斯克尔算法(二)、管梅谷的破圈法(三)、 Prim 算法(四)、计算机中的树简介 3 最小连接问题: 交通网络中,常常关注能把所有站点连接起来的生成树,使得该生成树各边权值之和为最小。例如: 假设要在某地建造 5个工厂,拟修筑道路连接这 5处。经勘探,其道路可按下图的无向边铺设。现在每条边的长度已经测出并标记在图的对应边上,如果我们要求铺设的道路总长度最短,这样既能节省费用,又能缩短工期,如何铺设? v 1v 2v 3v 4v 512 24345 54 v 1v 2v 3v 4v 512 23不难发现:最小代价的连接方式为: 最小连接问题的一般提法为: 在连通边赋权图 G中求一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。(一)、克鲁斯克尔算法 5 克鲁斯克尔(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) 尽可能小。 6 (3) 、当(2) 不能进行时,停止。例1 用克鲁斯克尔算法求下图的最小生成树。 3v 7215 467 8910 11 12 v 1v 2v 3 v 4v 5v 6v 87 解:过程如下: 1v 5v 821 v 1v 5v 8321 v 1v 4v 5v 8 3v 7215 v 1v 4v 5v 83v 7215 6 v 1v 4v 5v 8v 38 3v 7215 6 v 1v 4v 5v 8v 3v 68 3v 7215 6 v 1v 4v 5v 8v 3v 68v 29 2、算法证明定理 1 由克鲁斯克尔算法得到的任何生成树一定是最小生成树。证明:设 G是一个 n阶连通赋权图,用 T* =G[ { e1,e2, …,en-1 }] 表示由克鲁斯克尔算法得到的一棵生成树,我们证明:它是最小生成树。 9 设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*中的边。由克鲁斯克尔算法知道: ( ) ( ) k w e w e ?所以: 1 ( ) ( ) w T w T ?这说明 T1 是最小树,但这与 f(T) 的选取假设矛盾!所以: T = T *. 10 例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) 不能继续执行时停止。解:该方法不能得到一条最小生成路。