图论课件最小生成树

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