离散数学树解读课件.ppt

《离散数学树解读课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章树7.1无向树及生成树7.2根树及其应用17.1无向树及生成树无向树与森林生成树与余树基本回路与基本回路系统基本割集与基本割集系统最小生成树与避圈法2无向树无向树:无回路的连通无向图平凡树:平凡图森林:每个连通分支都是树的非连通的无向图树叶:树中度数为1的顶点分支点:树中度数2的顶点右图为一棵12阶树.注:本章中所讨论的回路均指简单回路或初级回路3树的应用英国数学家凯莱(ArthurCayley)于19世纪中叶研究饱和碳氢化合物CnH2n+2的同分异构体时提出树的概念.当n=1,2,3时,都只有一棵非同构的树;当n=4时,有

2、2棵不同构的树.甲烷乙烷丙烷丁烷异丁烷4无向树的性质定理设G=是n阶m条边的无向图,则下面各命题是等价的：(1)G是树(连通无回路);(2)G中任意两个顶点之间存在惟一的路径;(3)G中无回路且m=n1;(4)G是连通的且m=n1;(5)G是连通的且G中任何边均为桥;(6)G中没有回路,但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.5无向树的性质(续)定理设T是n阶非平凡的无向树，则T中至少有两片树叶.证设T有x片树叶,由握手定理及前面的定理，2(n-1)x+2(n-x)解得x2.6例题例1

3、已知无向树T中,有1个3度顶点,2个2度顶点,其余顶点全是树叶.试求树叶数,并画出满足要求的非同构的无向树.解用树的性质m=n1和握手定理.设有x片树叶，于是n=1+2+x=3+x,2m=2(2+x)=13+22+x解得x=3，故T有3片树叶.T的度数列为1,1,1,2,2,3有2棵非同构的无向树.7例题例2已知无向树T有5片树叶,2度与3度顶点各1个,其余顶点的度数均为4.求T的阶数n,并画出满足要求的所有非同构的无向树.解设T的阶数为n,则边数为n1,4度顶点的个数为n7.由握手定理得2m=2(n1)=51+2

4、1+31+4(n7)解得n=8,4度顶点为1个.T的度数列为1,1,1,1,1,2,3,4有3棵非同构的无向树8生成树设G为无向连通图G的生成树:G的生成子图并且是树生成树T的树枝:G在T中的边生成树T的弦:G不在T中的边生成树T的余树:所有弦的集合的导出子图注意：不一定连通,也不一定不含回路.黑边构成生成树红边构成余树9生成树的存在性定理任何无向连通图都有生成树.证用破圈法.若图中无圈,则图本身就是自己的生成树.否则删去圈上的任一条边,这不破坏连通性,重复进行直到无圈为止,剩下的图是一棵生成树.推论设n阶无向连通图有m条边,则

5、mn1.10基本回路与基本回路系统定义设T是连通图G的一棵生成树,对每一条弦e,存在惟一的由弦e和T的树枝构成的初级回路Ce,称Ce为对应于弦e的基本回路.称所有基本回路的集合为对应生成树T的基本回路系统.求基本回路的算法:设弦e=(u,v),先求T中u到v的路径uv,再加上弦e.例如Ce=ebc,Cf=fabc,Cg=gabcd,C基={Ce,Cf,Cg}.11基本割集与基本割集系统定义设T是连通图G的一棵生成树,对T的每一条树枝a,存在惟一的由树枝a,其余的边都是弦的割集Sa,称Sa为对应树枝a的基本割集，称所有基本割集的

6、集合为对应生成树T的基本割集系统.求基本割集的算法:设a为生成树T的树枝,Ta由两棵子树T1与T2组成,则Sa={e

7、eE(G)且e的两个端点分别属于T1与T2}.例如Sa={a,f,g},Sb={b,e,f,g},Sc={c,e,fg},Sd={d,g},S基={Sa,Sb,Sc,Sd}.12回路合并合并回路C1和C2(C1C2):C1C2是C1和C2上的边的对称差构成的(一条或几条)回路.13基本回路的性质连通图中的任一条回路都可以表成对应它所含弦的基本回路的合并.例如,abcf=Cfaef=CeCfaedg=C

8、eCgbcdgfe=CeCfCg14基本割集的性质连通图中的任一割集都可以表成对应它所含树枝的基本割集的对称差.例如{g,d}=Sd{a,b,e}=SaSb{a,e,c}=SaSc{b,e,f,d}=SbSd15无向图与最小生成树对无向图或有向图的每一条边e附加一个实数w(e),称作边e的权.图连同附加在边上的权称作带权图,记作G=.设T是G的生成树,T所有边的权的和称作T的权,记作W(T).最小生成树:带权图权最小的生成树避圈法(Kruskal)——求最小生成树的算法设G是n阶无向连通带权图G.(1)按权

9、从小到大排列边(环除外),设W(e1)≤W(e2)≤…≤W(em).(2)令T,i1,k0.(3)若ei与T中的边不构成回路，则令TT{ei},kk+1.(4)若k