资源描述：
《《无向树和生成树》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章1.无向树和生成树2.根树树连通而不含回路的无向图称为无向树,简称树,常用T表示树.连通分支数大于等于2,且每个连通分支均是树的非连通无向图称为森林.平凡图称为平凡树.树叶设T＝为一棵无向树,v∈V,若d(v)＝1,则称v为T的树叶.若d(v)≥2,则称v为T的分支点.设G＝,则下面各命题是等价的:(1)G连通而不含回路;(2)G的每对顶点之间具有唯一的一条路径;(3)G是连通的且n＝m+1;(4)G中无回路且n＝m+1;定理1(5)G中无回路,但在G中任两个不相邻的顶点之间增加一条边,就形成唯一的一条初级回路;(6)G
2、是连通的且G中每条边都是桥;(7)G是连通的,但删除任何一条边后,就不连通了.其中n为G中顶点数,m为边数.定理2设T＝是n阶非平凡的树,则T中至少有2片树叶.证明因为T是非平凡树,所以T中每个顶点的度数都大于等于1,设有k片树叶,则有(n-k)个顶点度数大于等于2,由握手定理可知由定理1可知m＝n-1,将此结果代入上式经过整理得k≥2,这说明T至少有2片树叶.生成树设G＝是无向连通图,T是G的生成子图,并且T是树,则称T是G的生成树.G在T中的边称为T的树枝,G不在T中的边称为T的弦.T的所有弦的集合的导出子图称为T的余树.
3、(2)为(1)的一棵生成树T,(3)为T的余树,注意余树不一定是树.定理任何连通图G至少存在一棵生成树.推论1设n阶无向连通图G有m条边,则m≥n-1.推论2设n阶无向连通图G有m条边,T是G的生成树,T'是T的余树,则T'中有m-n+1条边.图2基本回路在图2中,实边所示的子图是图G的一棵生成树T,d,e,f为T的树枝,a,b,c为T的弦.在T上加弦a,产生G的一个初级回路aed.在T上加弦b,产生G的一个初级回路bdf.在T上加弦c,产生G的一个初级回路cef.这3个回路中每一个回路都只含一条弦,其余的边都是树枝,这样的回路称为基本回路.基本
4、回路系统定义设T是n阶连通图G=的一棵生成树,G有n条边.设e1,e2···,em-n+1为T的弦,设Cr是T加弦er产生的G的回路,r=1,2,…m-n+1.称Cr为对应于弦er的基本回路,称{C1,C2,···,Cm-n+1}为对应生成树T的基本回路系统.基本割集系统定义设T是n阶连通图G=的一棵生成树,称T的n-1个树枝对应的G的n-1个割集(每个割集只含一个树枝,其余的边都是弦)S1,S2,···,Sn-1为对应生成树T的G的基本割集,称{S1,S2,···,Sn-1}为对应生成树T的基本割集系统.对一个n阶连通图G来
5、说,对应不同的生成树的基本割集可能不一样,但基本割集的个数必为n-1个,这也是G的固有特性.例1图G中,实线边所构成的子图是G的一棵生成树T,求T对应的基本回路和基本回路系统,基本割集和基本割集系统.解:G中顶点数n=6,边数m=9,基本回路个数为m-n+1=4,即T有4条弦f,g,h,i.对应的基本回路:Cf=facd;Cg=gba;Ch=hdcb;Ci=ied.基本回路系统为{Cf,Cg,Ch,Ci}T有5个树枝a,b,c,d,e,因而有5个基本割集:Sa={a,g,f};Sb={b,g,h};Sc={c,f,h};Sd={d,i,h};Se
6、={e,f,i};基本割集系统为{Sa,Sb,Sc,Sd,Se}.定义设无向连通带权图G=,T是G的一棵生成树.T各边带权之和称为T的权,记作W(T).G的所有生成树中带权最小的生成树称为最小生成树.Kruskal算法设n阶无向连通带权图G=中有m条边e1,e2···,em,它们带的权分别为a1,a2,…am,不妨设a1≤a2≤…≤am.(1)取e1在T中(e1非环,若e2为环,则弃e1);(2)若e2不与e1构成回路,取e2在T中,否则弃e2,再查e3,继续这一过程,直到形成生成树T为止.用以上算法生成的T是最小生成
7、树.实边所示的生成树均由避圈法得到的最小生成树.图(1)中,W(T)=15,图(2)中,W(T)=23.
