《离散数学-树》PPT课件.ppt

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

1、第16章树离散数学本章说明树是图论中重要内容之一。本章所谈回路均指初级回路（圈）或简单回路，不含复杂回路（有重复边出现的回路）。16.1无向树及其性质定义16.1无向树——连通无回路的无向图，简称树，用T表示。平凡树——平凡图。森林——若无向图G至少有两个连通分支（每个都是树）。树叶——无向图中悬挂顶点。分支点——度数大于或等于2的顶点。举例如图为九个顶点的树。定理16.1设G＝是n阶m条边的无向图，则下面各命题是等价的：（1）G是树。（2）G中任意两个顶点之间存在唯一的路径。（3）G中无回路且m＝n1。

2、（4）G是连通的且m＝n1。（5）G是连通的且G中任何边均为桥。（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。无向树的等价定义(1)(2)如果G是树，则G中任意两个顶点之间存在唯一的路径。存在性。由G的连通性及定理14.5的推论（在n阶图G中，若从顶点vi到vj(vivj)存在通路，则vi到vj一定存在长度小于等于n-1的初级通路(路径)）可知，u,v∈V，u与v之间存在路径。唯一性（反证法）。若路径不是唯一的，设Г1与Г2都是u到v的路径，易知必存在由Г1和Г

3、2上的边构成的回路，这与G中无回路矛盾。(2)(3)如果G中任意两个顶点之间存在唯一的路径，则G中无回路且m＝n-1。首先证明G中无回路。若G中存在关联某顶点v的环，则v到v存在长为0和1的两条路经(注意初级回路是路径的特殊情况)，这与已知矛盾。若G中存在长度大于或等于2的圈，则圈上任何两个顶点之间都存在两条不同的路径，这也与已知矛盾。(2)(3)如果G中任意两个顶点之间存在唯一的路径，则G中无回路且m＝n-1。其次证明m＝n-1。（归纳法）n＝1时，G为平凡图，结论显然成立。设n≤k(k≥1)时结论成立，当n=

4、k+1时，设e＝(u,v)为G中的一条边，由于G中无回路，所以G-e为两个连通分支G1、G2。设ni、mi分别为Gi中的顶点数和边数，则ni≤k，i＝1,2，由归纳假设可知mi＝ni-1，于是m＝m1+m2+1＝n1-1+n2-1+1＝n1+n2-1＝n-1。只需证明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，

5、则G是连通的且m＝n-1。如果G是连通的且m＝n1，则G是连通的且G中任何边均为桥。只需证明G中每条边均为桥。e∈E，均有

6、E(G-e)

7、＝n-1-1＝n-2，由习题十四题49（若G是n阶m条边的无向连通图，则m≥n-1）可知，G-e已不是连通图，所以，e为桥。(4)(5)如果G是连通的且G中任何边均为桥，则G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。因为G中每条边均为桥，删掉任何边，将使G变成不连通图，所以，G中没有回路，也即G中无圈。又由于G连通，所以G为树，由(

8、1)(2)可知，u,v∈V，且u≠v，则u与v之间存在唯一的路径Г，则Г∪(u,v)（(u,v)为加的新边）为G中的圈，显然圈是唯一的。(5)(6)如果G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈，则G是树。只需证明G是连通的。u,v∈V，且u≠v，则新边(u,v)∪G产生唯一的圈C，显然有C-(u,v)为G中u到v的通路，故u～v，由u,v的任意性可知，G是连通的。(6)(1)定理16.2设T是n阶非平凡的无向树，则T中至少有两片树叶。设T有x片树叶，由握手定理及

9、定理16.1可知，证明由上式解出x≥2。无向树的性质例16.1例16.1画出6阶所有非同构的无向树。解答设Ti是6阶无向树。由定理16.1可知，Ti的边数mi＝5，由握手定理可知，∑dTi(vj)＝10，且δ(Ti)≥1，△(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度顶点相邻，在另一棵树中不相邻，其他情况均能画出一棵非同构的树。例1

10、6.1人们常称只有一个分支点，且分支点的度数为n-1的n(n≥3)阶无向树为星形图，称唯一的分支点为星心。例16.2例16.27阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3。试画出满足要求的所有非同构的无向树。解答设Ti为满足要求的无向树，则边数mi＝6，于是∑d(vj)＝12＝e+3+d(v4)+d(v5)+d(v6)。由于