欢迎来到天天文库
浏览记录
ID:50766212
大小:915.00 KB
页数:41页
时间:2020-03-14
《离散数学树PPT课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第16章树离散数学本章说明树是图论中重要内容之一。本章所谈回路均指初级回路(圈)或简单回路,不含复杂回路(有重复边出现的回路)。216.1无向树及其性质定义16.1无向树——连通无回路的无向图,简称树,用T表示。平凡树——平凡图。森林——若无向图G至少有两个连通分支(每个都是树)。树叶——无向图中悬挂顶点。分支点——度数大于或等于2的顶点。举例如图为九个顶点的树。3定理16.1设G=是n阶m条边的无向图,则下面各命题是等价的:(1)G是树。(2)G中任意两个顶点之间存在唯一的路径。(3)G中无回路且m=n1。(4)G是连通的且m=n1。(5)G
2、是连通的且G中任何边均为桥。(6)G中没有回路,但在任何两个不同的顶点之间加一条新边,在所得图中得到唯一的一个含新边的圈。无向树的等价定义4(1)(2)如果G是树,则G中任意两个顶点之间存在唯一的路径。存在性。由G的连通性及定理14.5的推论(在n阶图G中,若从顶点vi到vj(vivj)存在通路,则vi到vj一定存在长度小于等于n-1的初级通路(路径))可知,u,v∈V,u与v之间存在路径。唯一性(反证法)。若路径不是唯一的,设Г1与Г2都是u到v的路径,易知必存在由Г1和Г2上的边构成的回路,这与G中无回路矛盾。5(2)(3)如果G中任意两个顶点之
3、间存在唯一的路径,则G中无回路且m=n-1。首先证明G中无回路。若G中存在关联某顶点v的环,则v到v存在长为0和1的两条路经(注意初级回路是路径的特殊情况),这与已知矛盾。若G中存在长度大于或等于2的圈,则圈上任何两个顶点之间都存在两条不同的路径,这也与已知矛盾。6(2)(3)如果G中任意两个顶点之间存在唯一的路径,则G中无回路且m=n-1。其次证明m=n-1。(归纳法)n=1时,G为平凡图,结论显然成立。设n≤k(k≥1)时结论成立,当n=k+1时,设e=(u,v)为G中的一条边,由于G中无回路,所以G-e为两个连通分支G1、G2。设ni、mi分别为Gi
4、中的顶点数和边数,则ni≤k,i=1,2,由归纳假设可知mi=ni-1,于是m=m1+m2+1=n1-1+n2-1+1=n1+n2-1=n-1。7只需证明G是连通的。(采用反证法)假设G是不连通的,由s(s≥2)个连通分支G1,G2,…,Gs组成,并且Gi中均无回路,因而Gi全为树。由(1)(2)(3)可知,mi=ni-1。于是,由于s≥2,与m=n-1矛盾。(3)(4)如果G中无回路且m=n-1,则G是连通的且m=n-1。8如果G是连通的且m=n1,则G是连通的且G中任何边均为桥。只需证明G中每条边均为桥。e∈E,均有
5、E(G-e)
6、=n-1-1
7、=n-2,由习题十四题49(若G是n阶m条边的无向连通图,则m≥n-1)可知,G-e已不是连通图,所以,e为桥。(4)(5)9如果G是连通的且G中任何边均为桥,则G中没有回路,但在任何两个不同的顶点之间加一条新边,在所得图中得到唯一的一个含新边的圈。因为G中每条边均为桥,删掉任何边,将使G变成不连通图,所以,G中没有回路,也即G中无圈。又由于G连通,所以G为树,由(1)(2)可知,u,v∈V,且u≠v,则u与v之间存在唯一的路径Г,则Г∪(u,v)((u,v)为加的新边)为G中的圈,显然圈是唯一的。(5)(6)10如果G中没有回路,但在任何两个不同的
8、顶点之间加一条新边,在所得图中得到唯一的一个含新边的圈,则G是树。只需证明G是连通的。u,v∈V,且u≠v,则新边(u,v)∪G产生唯一的圈C,显然有C-(u,v)为G中u到v的通路,故u~v,由u,v的任意性可知,G是连通的。(6)(1)11定理16.2设T是n阶非平凡的无向树,则T中至少有两片树叶。设T有x片树叶,由握手定理及定理16.1可知,证明由上式解出x≥2。无向树的性质12例16.1例16.1画出6阶所有非同构的无向树。解答设Ti是6阶无向树。由定理16.1可知,Ti的边数mi=5,由握手定理可知,∑dTi(vj)=10,且δ(Ti)≥1,△
9、(Ti)≤5。于是Ti的度数列必为以下情况之一。(1)1,1,1,1,1,5(2)1,1,1,1,2,4(3)1,1,1,1,3,3(4)1,1,1,2,2,3(5)1,1,2,2,2,2(4)对应两棵非同构的树,在一棵树中两个2度顶点相邻,在另一棵树中不相邻,其他情况均能画出一棵非同构的树。13例16.1人们常称只有一个分支点,且分支点的度数为n-1的n(n≥3)阶无向树为星形图,称唯一的分支点为星心。14例16.2例16.27阶无向图有3片树叶和1个3度顶点,其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。解答设Ti为满足要求的无向树,
10、则边数mi=6,于是∑d(vj)=12=e+3+d(
此文档下载收益归作者所有