离散数学PPT课件5树与生成树(ppt文档).ppt

单击以编辑,母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,5,树与生成树,树是一种特殊的图,它是图论中重要的概念之一,它有,着广泛的应用,.,在计算机科学中有如判定树、语法树、分,类树、搜索树、目录树等等,.,一,.,树,(Tree),1.,树的定义,:,一个连通无回路的,无向图,T,称之为树,.,如,(a),2.,叶结点,:,度数为,1,的结点,称为叶结点,.,3.,分支结点,(,内结点,):,度数大于,1,的结点,.,4.,森林,:,一个无向图的每个连通分支都是树,.,如,(b),(,a),(b),5.,与树定义等价的几个命题,定理,8-9.1,给定图,T,以下关于树的定义是等价的,.,无回路的连通图,.,无回路且,e=v-1,其中,e,是,T,的边数,v,是,T,的结点数.,连通的且,e=v-1.,无回路但添加一条新边则得到一条仅有的回路,.,连通的,但删去任一条边,T,便不连通,.,每对结点之间有一条且仅有一条路,.,证明,:,:,已知,T,是连通无回路图,通过不断地增加,T,中,的结点数,归纳证明.,当,v=2,时,T,如右图所示,e=1,显然,e=v-1.,以后对,T,在保证连通又无回路的前提下每增加一个结点,也增加一条边,.,设最后,T,有,v,个结点,e,条边,所以,e=v-1.,:,已知,T,是无回路的,且,e=v-1.(,推出,T,是连通的,),假设,T,不是连通的,设,T,有,k,个连通分支,T,1,T,2,.,T,k,(k,2,),因为它的每个连通分支都是连通无回路的,所以都是树,设,T,i,有结点数,v,i,边数,e,i,所以边数,e,i,=v,i,-1,设,T,有,v,个结点,e,条边.所以,v=,v,1,+v,2,+v,3,+v,k,e=,e,1,+e,2,+e,3,+e,k,=(v,1,-1)+(v,2,-1)+(v,3,-1)+(v,k,-1),=(,v,1,+v,2,+v,3,+v,k,)-k=v-k,但是已知,e=v-1,所以,k=1,所以,T,是连通图.,:,已知,T,是连通的且,e=v-1(,推出,T无回路,且加一新,边,得到仅有一条回路,)假设,T,有回路,C,1,从,C,1,中删去一条边,以后,T,仍然连通性,如果还有回路,C,2,再从,C,2,中删去一条边,如此下去.假设共删去,k,条边,就无回路了,得到树,T,设,T,有,边,e,e=v-1,e-k=v-1,又已知,e=v-1,k=0,即,T,无回路,再证明,:,加一新边,得到仅有一条回路,假设加一条新边(,u,v),如果,u,与,v,是邻接点,那么新边与原来,(,u,v),边构成平行边,自成一个回路.如果,u,与,v,不邻接,由于,T,是连通的,u,间,v,必有一条路径,P,加上新边(,u,v),后,就与,P,构成回路,且此回路必是唯一的.因为如果回路不唯一,则,删去(,u,v),边后,还有回路,与上面证出的,T,无回路矛盾.,:,已知,T,无回路,且加一条边得到仅有的一条回路,.,(,推出,T,是连通的,且删去一条边后,T,就不连通了,),假设,T,不是连通的,则存在两个结点,v,i,与,v,j,之间无路,于是,加上边,(v,i,v,j,),不会产生回路,这与已知矛盾,.,故,T,树连通的,.,因,T,是连通无回路的,故删去任何一条边后,T,就不连通了,.,:,已知,T,是连通的,且删去一条边后,T,就不连通了,.,(,推出每对结点之间有且仅有一条路,),由,T,是连通图,则任何两个结点间都有一条路,.,如果有两个结点间有多于一条的路,那么,T,必有回路,则删去回路中的,一条边后,T,仍然是连通的,.,与已知矛盾,.,:,已知,T,每对结点间有且仅有一条路,(,推出,T,连通无,回路,),因为,T,每对结点之间有一条路,所以,T,是连通的,.,若,T,有回路,则回路上任何两个结点间有两条路,与已知矛盾,.,二,.,生成树,在图论的应用中,找出一个连通图的所有不同的生成树,以,及找出最小生成树是很有意义的,.,1.,定义,:,如果图,G,的生成子图是树,则称此树为,G,的生成树,.,2.,弦,:,图,G,中,不在其生成树里的边,称作,弦,.,所有弦的集合,称为该生成,树的补,.,定理,8-9.2,连通图至少有一棵生成树,.,证明,:,如果,G,中无回路,则,G,本身就是树,.,如果,G,中有回路,可以通过反复删去回路,中的边,使之既无回路,又连通,.,就得到生成树,.,思考题,:,设,G,是有,n,个结点,m,条边的连通图,问要删去多少,条边,才得到一棵生成树?,寻找生成树的方法,：深度优先；广度优先,.,v,1,v,5,v,4,v,2,v,3,三,.,赋权图的最小生成树,1.,定义,:,一棵生成树中的所有边的权之和称为该,生成树的,权,.,具有最小权的生成树,称为,最小生成树,.,最小生成树很有实际应用价值,.,例如结点是城市名,边的权,表示两个城市间的距离,从一个城市出发走遍各个城市,如何选择最优的旅行路线,.,又如城市间的通信网络问题,如,何布线,使得总的线路长度最短,.,例如,:,右图所示,2.,求最小生成树算法,-Kruskal,算法:,(,避圈法,),v,1,v,5,v,4,v,2,v,3,v,8,v,6,v,7,1,2,2,1,3,7,7,2,4,8,6,6,5,3,4,4,3,Kruskal,算法:设,G,是有,n,个结点,m,条边(,mn-1),的连通图.,|S|=n-1,说明是树,最后,S=,a,1,a,2,a,3,a,n,S=i=0 j=1,将所有边按照权升序排序,:,e,1,e,2,e,3,e,m,|S|=n-1,取,e,j,使得,S e,j,有回路,?,j=j+1,i=i+1,a,i,=e,j,S=Sa,i,j=j+1,输出,S,停,Y,N,Y,N,边按升序排序,:,边,(,v,i,v,j,),记成,e,ij,边,权,边,权,e,28,e,34,e,23,e,38,e,17,e,24,e,45,e,57,e,16,e,78,e,56,e,35,e,46,e,67,e,58,e,12,e,18,1 1 2 2 2 3 3 3 4,4 4 5 6 6 7 7 8,v,1,v,5,v,4,v,2,v,3,v,8,v,6,v,7,1,2,2,1,3,7,7,2,4,8,6,6,5,3,4,4,3,v,1,v,5,v,4,v,2,v,3,v,8,v,6,v,7,1,2,1,2,4,3,3,本节要掌握,树的,6,个定义,会画生成树和最小生成树,.,作业,p171(4)(8),