屈婉玲全套配套课件离散数学及其应用 第十章.ppt

《屈婉玲全套配套课件离散数学及其应用 第十章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第十章树主要内容无向树及其性质生成树根树及其应用10.1无向树及其性质定义10.1连通无回路的无向图称为无向树,简称树.每个连通分支都是树的无向图称为森林.平凡图称为平凡树.在无向树中,悬挂顶点称为树叶,度数大于或等于2的顶点称为分支点．例fff星形树3无向树的性质定理10.1设G=是n阶m条边的无向图，则下面各命题是等价的：(1)G是树(2)G中任意两个顶点之间存在惟一的路径.(3)G中无回路且m=n1.(4)G是连通的且m=n1.(5)G是连通的且G中任何边均为桥.(6)G中没有回路，但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.4(3)

2、(4).只需证明G连通.用反证法.否则G有s(s2)个连通分支,它们都是树.于是,有mi=ni1,这与m=n1矛盾.证明(2)(3).若G中有回路，则回路上任意两点之间的路径不惟一.对n用归纳法证明m=n1.当n=1时成立.设nk时成立，证n=k+1时也成立：任取一条边e，Ge有且仅有两个连通分支G1,G2.nik，由归纳假设得mi=ni1,i=1,2.于是，m=m1+m2+1=n1+n22+1=n1.证(1)(2).若路径不惟一,必有回路.5(4)(5).只需证明G中每条边都是桥.下述命题显然成立:G是n阶m条边的无向连通图，则mn1.eE,Ge

3、只有n2条边，由命题可知Ge不连通，故e为桥.证明(5)(6).由(5)易知G为树.由(1)(2)知，u,vV（uv）,u到v有惟一路径，加新边(u,v)得惟一的一个圈.(6)(1).只需证明G连通，这是显然的.解得x2.定理10.2设T是n阶非平凡的无向树，则T中至少有两片树叶.无向树的性质证设T有x片树叶，由握手定理及定理10.1可知，例1已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树.解设有x片树叶，n=3+x.2m=2(n1)=2(2+x)=13+22+x解出x=3，故T有3片树叶.7例2已知

4、无向树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个.810.2生成树定义10.2如果无向图G的生成子图T是树，则称T是G的生成树.设T是G的生成树，G的在T中的边称为T的树枝，不在T中的边为T的弦.称T的所有弦的导出子图为T的余树，记作.例9定理10.3无向图G有生成树当且仅当G连通.生成树存在条件推论G为n阶m条边的无向连通图，则mn1.证必要性显然.证充分性

5、．若G中无回路，则G为自己的生成树．若G中含圈，任取一圈，随意地删除圈上的一条边;若仍有圈,再任取一个圈并删去这个圈上的一条边，重复进行,直到最后无圈为止.最后得到的图无圈（当然无回路）、连通且是G的生成子图，因而是G的生成树．这个产生生成树的方法称为破圈法．10最小生成树定义10.3设无向连通带权图G=，T是G的一棵生成树，T的各边权之和称为T的权，记作W(T)．G的所有生成树中权最小的生成树称为G的最小生成树.避圈法（Kruskal）输入:连通图G=输出:G的最小生成树T1.将G中非环边按权从小到大排列:W(e1)W(e2)…W(em).2.令T

6、{e1},i2.3.若ei与T中的边不构成回路,则令TT{ei}.4.若

7、T

8、

9、5设T为一棵非平凡的根树,vi,vjV(T),若vi可达vj，则称vi为vj的祖先,vj为vi的后代;若vi邻接到vj,则称vi为vj的父亲,vj为vi的儿子.若vj,vk的父亲相同,则称vj与vk是兄弟．将根树T中层数相同的顶点都标定次序,称T为有序树．根树的分类：(1)若T的每个分支点至多有r个儿子，则称T为r叉树.(2)若T的每个分支点都恰好有r个儿子,则称T为r叉正则树.(3)若T是r叉正则树,且所有树叶的层数相同,则称T为r叉完全正则树.有序