《无向树及生成树》PPT课件

《《无向树及生成树》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章树9.1无向树及生成树9.2根树及其应用19.1无向树及生成树无向树、森林树枝、弦、余树生成树基本回路与基本回路系统基本割集与基本割集系统最小生成树2无向树无向树(树):连通而无回路的无向图，用T表示.平凡树:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点:树中度数2的顶点右图为一棵12阶树.声明:本章中所讨论的回路均指简单回路或初级回路3无向树的性质定理9.1设G=是n阶m条边的无向图，则下面各命题是等价的：（1）G是树(连通无回路);（2）G中任意两个顶点之间存在惟一的路径;（3）G中无回路且m=n1;（4）G是连通

2、的且m=n1;（5）G是连通的且G中任何边均为桥;（6）G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.4无向树的性质(续)定理9.2设T是n阶非平凡的无向树，则T中至少有两片树叶.证设T有x片树叶，由握手定理及定理9.1可知，由上式解出x2.5例题例1已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.试求树叶数,并画出满足要求的非同构的无向树.解用树的性质m=n1和握手定理.设有x片树叶，于是n=1+2+x=3+x,2m=2(n1)=2(2+x)=13+22+x解出x=3，故T有3片树叶.T的度数列为1,

3、1,1,2,2,3有2棵非同构的无向树,如图所示6例题例2已知无向树T有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.求T的阶数n,并画出满足要求的所有非同构的无向树.解设T的阶数为n,则边数为n1,4度顶点的个数为n7.由握手定理得2m=2(n1)=51+21+31+4(n7)解出n=8,4度顶点为1个.T的度数列为1,1,1,1,1,2,3,4有3棵非同构的无向树7生成树设G为无向连通图G的生成树:G的生成子图并且是树生成树T的树枝:G在T中的边生成树T的弦:G不在T中的边生成树T的余树:所有弦的集合的导出子图注意：不一定连通,也不一定不含回路

4、.右图黑边构成生成树红边构成余树8生成树的存在性定理任何无向连通图都有生成树.证用破圈法.若图中无圈,则图本身就是自己的生成树.否则删去圈上的任一条边,这不破坏连通性,重复进行直到无圈为止,剩下的图是一棵生成树.推论1设n阶无向连通图有m条边,则mn1.推论2设n阶无向连通图有m条边,则它的生成树的余树有mn+1条边.推论3设为G的生成树T的余树，C为G中任意一个圈，则C与一定有公共边.9基本回路与基本回路系统定义设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,…,emn+1为T的弦.设Cr为T添加弦er产生的G中惟一的圈(由er和树枝组成)

5、,称Cr为对应弦er的基本回路或基本圈,r=1,2,…,mn+1.称{C1,C2,…,Cmn+1}为对应T的基本回路系统.求基本回路的算法:设弦e=(u,v),先求T中u到v的路径uv,再并上弦e,即得对应e的基本回路.10基本割集与基本割集系统定义设T是n阶连通图G的一棵生成树,e1,e2,…,en1为T的树枝，Si是G的只含树枝ei,其他边都是弦的割集,称Si为对应生成树T由树枝ei生成的基本割集,i=1,2,…,n1.称{S1,S2,…,Sn1}为对应T的基本割集系统.求基本割集的算法:设e为生成树T的树枝,Te由两棵子树T1与T2组

6、成,令Se={e

7、eE(G)且e的两个端点分别属于T1与T2}则Se为e对应的基本割集.11实例例图中红边为一棵生成树,求对应它的基本回路系统与基本割集系统解弦e,f,g对应的基本回路分别为Ce=ebc,Cf=fabc,Cg=gabcd,C基={Ce,Cf,Cg}.树枝a,b,c,d对应的基本割集分别为Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,fg},Sd={d,g},S基={Sa,Sb,Sc,Sd}.12无向图与最小生成树对无向图或有向图的每一条边e附加一个实数w(e),称作边e的权.图连同附加在边上的权称作带权图,记作G=

8、.设G是G的子图,G所有边的权的和称作G的权,记作W(G).最小生成树:带权图权最小的生成树求最小生成树的算法——避圈法(Kruskal)设G=,将非环边按权从小到大排序：e1,e2,…,em.(1)取e1在T中(2)检查e2,若e2与e1不构成回路,则将e2加入T中,否则弃去e2.(3)检查e3,…,重复进行直至得到生成树为止.13实例例求图的一棵最小生成树W(T)=38149.2根树及其应用有向树根树、树根、树叶、内点、分支点家族树、根子树、有序树r元树（r元有序树）r元正则树（r元有序正则树）r元完全正则树（r