离散数学16 PPT课件.ppt

第16章树
聊城大学重点课程离散数学
本章说明
树是图论中重要内容之一。
本章所谈回路均指初级回路(圈)或简单回路,不含复杂回路(有重复边出现的回路)。
无向树及其性质
生成树
根树及其应用
本章小结
习题
作业
本章说明
无向树及其性质

无向树——连通无回路的无向图,简称树,用T表示。
平凡树——平凡图。
森林——若无向图G至少有两个连通分支(每个都是树)。
树叶——无向图中悬挂顶点。
分支点——度数大于或等于2的顶点。
举例 如图为九个顶点的树。
设G=<V,E>是n阶m条边的无向图,则下面各命题是等价的:
(1)G是树。
(2)G中任意两个顶点之间存在唯一的路径。
(3)G中无回路且m=n1。
(4)G是连通的且m=n1。
(5)G是连通的且G中任何边均为桥。
(6)G中没有回路,但在任何两个不同的顶点之间加一条新边,在所得图中得到唯一的一个含新边的圈。
无向树的等价定义
(1)(2)
如果G是树,则G中任意两个顶点之间存在唯一的路径。
存在性。
(在n阶图G中,若从顶点vi到vj(vivj)存在通路,则vi到vj 一定存在长度小于等于n-1的初级通路(路径))可知,
u,v∈V,u与v之间存在路径。
唯一性(反证法)。
若路径不是唯一的,设Г1与Г2都是u到v的路径,
易知必存在由Г1和Г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=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,则G是连通的且m=n -1。
如果G是连通的且m=n1,则G是连通的且G中任何边均为桥。
只需证明G中每条边均为桥。
e∈E,均有|E(G-e)|=n-1-1=n-2,
由习题十四题49(若G是n阶m条边的无向连通图,则m≥n-1)可知,G-e已不是连通图,
所以,e为桥。
(4)(5)