《图论最小生成树.pptx》由会员分享,可在线阅读,更多相关《图论最小生成树.pptx(35页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、1本次课主要内容最小生成树(一)、克鲁斯克尔算法(二)、管梅谷的破圈法(三)、Prim算法(四)、计算机中的树简介第1页/共35页2最小连接问题:交通网络中,常常关注能把所有站点连接起来的生成树,使得该生成树各边权值之和为最小。例如:假设要在某地建造5个工厂,拟修筑道路连接这5处。经勘探,其道路可按下图的无向边铺设。现在每条边的长度已经测出并标记在图的对应边上,如果我们要求铺设的道路总长度最短,这样既能节省费用,又能缩短工期,如何铺设?v1v2v3v4v512243455第2页/共35页3v1v2v3v4v51223不难发现:最小代价的连接方式为:最小连接问题的一般提法为:在连通边赋权图G中求
2、一棵总权值最小的生成树。该生成树称为最小生成树或最小代价树。(一)、克鲁斯克尔算法第3页/共35页4克鲁斯克尔(Kruskal):1928年生,一家3弟兄都是数学家,1954年在普林斯顿大学获博士学位,导师是Erds,他大部分研究工作是数学和语言学,主要在贝尔实验室工作。1956年发表包含克鲁斯克尔算法论文,使他名声大振。1、算法思想从G中的最小边开始,进行避圈式扩张。2、算法(1)、选择边e1,使得其权值最小;(2)、若已经选定边e1,e2,ek,则从E-e1,e2,ek 中选择边ek+1,使得:(a)、Ge1,e2,ek+1为无圈图(b)、ek+1的权值w(ek+1)尽可能小。第4页/共3
3、5页5(3)、当(2)不能进行时,停止。例1 用克鲁斯克尔算法求下图的最小生成树。3v721546789101112v1v2v3v4v5v6v8第5页/共35页6解:过程如下:1v5v821v1v5v8321v1v4v5v83v7215v1v4v5v83v72156v1v4v5v8v3第6页/共35页73v72156v1v4v5v8v3v683v72156v1v4v5v8v3v68v292、算法证明定理1 由克鲁斯克尔算法得到的任何生成树一定是最小生成树。证明:设G是一个n阶连通赋权图,用T*=Ge1,e2,en-1表示由克鲁斯克尔算法得到的一棵生成树,我们证明:它是最小生成树。第7页/共35
4、页8 设T是G的一棵最小生成树。若T*T由克鲁斯克尔算法容易知道:TT*。于是令f(T)=k 表示T*中的边ei不在T中的最小i值。即可令T=Ge1,e2,ek-1,ek,en 考虑:Tek,则由树的性质,它必然为G中圈。作 T1=T ek-e,容易知道:T1还为G的一棵生成树。设e是圈T ek中在T中,但不在T*中的边。由克鲁斯克尔算法知道:所以:这说明T1是最小树,但这与f(T)的选取假设矛盾!所以:T=T*.第8页/共35页9 例2 在一个边赋权G中,下面算法是否可以产生有最小权值的生成路?为什么?算法:(1)选一条边e1,使得w(e1)尽可能小;(2)若边e1,e2,ei已经选定,则用
5、下述方法从Ee1,.,ei中选取边ei+1:(a)G e1,e2,ei,ei+1为不相交路之并;(b)w(ei+1)是满足(a)的尽可能小的权。(3)当(2)不能继续执行时停止。解:该方法不能得到一条最小生成路。第9页/共35页10 例如,在下图G中我们用算法求生成路:3122343667910 用算法求出的生成路为:122693第10页/共35页11直接在图中选出的一条生成路为:123366 后者的权值小于前者。(二)、管梅谷的破圈法 在克鲁斯克尔算法基础上,我国著名数学家管梅谷教授于1975年提出了最小生成树的破圈法。第11页/共35页12 管梅谷()。我国著名数学家,曾任山东师范大学校长
6、。中国运筹学会第一、二届常务理事,第六届全国政协委员。从事运筹学及其应用的研究,对最短投递路线问题的研究取得成果,冠名为中国邮路问题,该问题被列入经典图论教材 和著作。管梅谷教授1957年至1990年在山东师范大学工作。1984年至1990年担任山东师范大学校长,1990年至1995年任复旦大学运筹学系主任。1995年至今任澳大利亚皇家墨尔本理工大学交通研究中心高级研究员,国际项目办公室高级顾问及复旦大学管理学院兼职教授。自1986年以来,管教授致力于城市交通规划的研究,在我国最早引进加拿大的交通规划EMME软件,取得一系列重要研究成果。第12页/共35页13 破圈法求最小生成树的求解过程是:
7、从赋权图G的任意圈开始,去掉该圈中权值最大的一条边,称为破圈。不断破圈,直到G中没有圈为止,最后剩下的G的子图为G的最小生成树。证明可以参看数学的认识与实践4,(1975),38-41。3122343667910 例3 用破圈法求下图G的最小生成树。第13页/共35页14312234366710 解:过程如下:3122346671031223667103122667103122667312266第14页/共35页15(三)、Prim算法 Prim算法是由Prim在1957年提出的一个著名算法。作者因此而出名。Prim(1921-)1949年在普林斯顿大学获博士学位,是Sandia公司副总裁。P
8、rim算法:对于连通赋权图G的任意一个顶点u,选择与点u关联的且权值最小的边作为最小生成树的第一条边e1;在接下来的边e2,e3,en-1,在于一条已经选取的边只有一个公共端点的的所有边中,选取权值最小的边。用反证法可以证明该算法。即证明:由Prim算法得到的生成树是最小生成树。(证明略)第15页/共35页16 例4 用Prim算法求下图的最小生成树。554432176v1v2v3v4v5 解:过程如下:1v1v231v1v2v3第16页/共35页17431v1v2v3v44321v1v2v3v4v5 最小生成树权值为:w(T)=10.例5 连通图G的树图是指这样的图,它的顶点是G的生成树T1
9、,T2,T,Ti与Tj相连,当且仅当它们恰有n-2条公共边。证明任何连通图的树图是连通图。证明:只需证明,对任意Ti与Tj,在树图中存在连接它们的路即可!第17页/共35页18 对任意Ti与Tj,设e1,e2,ek(k n-2)是它们的公共边。由树的性质:使得:。该圈中:作:则Ti与Ti+1有n-2条边相同,于是,它们邻接。此时,Ti+1与Tj有k+1条边相同。如此这样作下去,可以得到连接Ti与Tj的一条路为:所以,连通图G的树图是连通的。第18页/共35页19(四)、计算机中的树简介 在计算机科学中,常常遇到所谓的根树。定义2:一棵树T,如果每条边都有一个方向,称这种树为有向树。对于T的顶点
10、v来说,以点v为终点的边数称为点v的入度,以点v为起点的边数称为点v的出度。入度与出度之和称为点v的度。u7u5u4u3u2u1u6有向树T 注:指出上图中顶点的入度、出度和度。第19页/共35页20定义3:一棵非平凡的有向树T,如果恰有一个顶点的入度为0,而其余所有顶点的入度为1,这样的的有向树称为根树。其中入度为0的点称为树根,出度为0的点称为树叶,入度为1,出度大于1的点称为内点。又将内点和树根统称为分支点。倒置根树T根树T 注:根树常画成倒置形式,方向由上指向下。第20页/共35页21定义4:对于根树T,顶点v到树根的距离称为点v的层数;所有顶点中的层数的最大者称为根树T的树高。上图中
11、,根树高为3;倒置根树T2176435891011 树根1:0层;点2,3,4:第1层;余类推。第21页/共35页22计算机中数据结构常采用根树结构。族谱图是根树。定义5:对于根树T,若规定了每层顶点的访问次序,这样的根树称为有序树。注:一般次序为从左至右。有时也用边的次序代替顶点次序。定义6:对于根树T,由点v及其v的后代导出的子图,称为根树的子根树。倒置根树T2176435891011根树T的对应点2的子根树25910第22页/共35页23定义7:对于根树T,若每个分支点至多m个儿子,称该根树为m元根树;若每个分支点恰有m个儿子,称它为完全m元树。3元根树T2176435891011完全3
12、元根树T2176435891011对于完全m元树T,有如下性质:定理2 在完全m元树T中,若树叶数为t,分支点数为i,则:第23页/共35页24证明:一方面,由树的性质得:另一方面,由握手定理得:由(1)与(2)消去m(T)得:例6 一台计算机,它有一条加法指令,可以计算3个数的和。如果要求9个数的和,问至少执行多少次加法指令?解:用3个顶点表示3个数,用一个父结点表示3个数的和。问题转化为求一棵有9个叶点的完全3元树的分支点数。第24页/共35页25即:m=3,t=9,求i=?由定理2得:i=4,至少要执行4次。两种可能情况是:x6x5x4x3x2x1x7x8x9x1x2x3x4x5x6x7
13、x8x9 在m元树中,应用最广泛的是二元树,原因是它在计算机中容易处理。第25页/共35页26对于一棵有序树,常要转化为二元树。方法是:(1)从根开始,保留每个父亲同其最左边儿子的连线,撤销与别的儿子的连线;(2)兄弟间用从左至右的有向边连接;(3)按如下方法确定二元树中结点的左右儿子:直接位于给定结点下面的儿子,作为左儿子,对于同一水平线上 与给定结点右邻的结点,作为右儿子,依此类推。例7 将下根树转化为二元树。v1v2v3v4v5v6v7v8v9根树Tv10v11第26页/共35页27 解:v1v2v3v4v5v6v7v8v9v10v11v1v2v3v4v5v6v7v8v9v10v11第2
14、7页/共35页28 二元树的遍历问题 找到一种方法,能系统访问根结点,使得每个结点恰好访问一次。有三种常用方法:(1)先根次序遍历:1)访问根;2)按先根次序遍历根的左子树;3)按先根次序遍历根的右子树;即:先左后右!例如:v1v2v3v4v5v6v7v8v9v10v12v11第28页/共35页29先根次序遍历次序为:v1v2v4v6v7v3v5v8v9v10v11v12.(2)中根次序遍历:2)访问根;1)按中根次序遍历根的左子树;3)按中根次序遍历根的右子树;v1v2v3v4v5v6v7v8v9v10v12v11中根次序遍历次序为:v6v4v7v2v1v8v5v11v10v12v9v3.第
15、29页/共35页30(3)后根次序遍历:3)访问根;1)按后根次序遍历根的左子树;2)按后根次序遍历根的右子树;v1v2v3v4v5v6v7v8v9v10v12v11后根次序遍历次序为:v6v7v4v2v8v11v12v10v9v5v3v1.第30页/共35页31 最优二元树 定义8 设T是一棵二元树,若对所有t片树叶赋权值wi(1it),且权值为wi的树叶层数为L(wi),称:为该赋权二元树的权。而在所有赋权为wi的二元树中W(T)最小的二元树称为最优二元树。哈夫曼算法:(1)初始:令S=w1,w2,wt;(2)从S中取出两个权值最小者wi与wj,画结点vi,带权wi,画结点vj,带权wj,画vi与vj的父亲v,连接vi与v,连接vj与v,令v带权wi+wj;第31页/共35页32(3)令S=(S-wiwj)wi+wj;(4)判断S是否只含一个元素,若是,停止,否则转2).例8 求带权为:7、8、9、12、16的最优树。解:由哈夫曼算法:7815(1)7815(2)91221912217815(3)1631912217815(4)163152第32页/共35页33 作业 P43 习题2:16,17,18第33页/共35页34Thank You!第34页/共35页35感谢您的观看。第35页/共35页
限制150内