文档介绍：第十六章树
无向树及其性质
一、无向树的定义
连通无回路的无向图称为
无向树,或简称树,常用T表示树。平凡
图称为平凡树。若无向图G至少有两个连
通分支,每个连通都是树,则称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的连通性及定理
, u,v∈V,u与v之间存
在路径,若路径不是唯一的,设Г1与Г2
都是u到v的路径,易知必存在由Г1和Г2
上的边构成的回路,这与G中无回路矛盾。
(2)(3).首先证明G中无回路。若
G中存在关联某顶点v的环,则v到v存在长
为0和1的两条路经,这与已知矛盾。若G中
存在长度大于或等于2的圈,则圈上任何两个
顶点之间都存在两条不同的路径,这也引出
矛盾。下面用归纳法证明m=n-1.
n=1时,G为平凡图,结论显然成立。
设n≤k(k≥1)时结论成立,当n=k+1时,
设e=(u,v)为G中的一条边,由于G中无回
路,所以G-e为两个连通分支G1,,
mi分别为Gi中的顶点数和边数,则ni≤k ,
i=1,2,由归纳假设可知mi=ni-1,于是m=
m1+m2+1=n1+n2+1-2=n-1.
(3)(4).只要证明G是连通的。否
则设G有s(s≥2)个连通分支G1,G2,…,Gs,
Gi中均无回路,因而Gi全为树,由
(1)(2)(3)
可知,mi=ni-,m= =n-s,
由于s≥2,这与m=n-1矛盾。
(4)(5).只要证明G中每条边均为
桥, e∈E,均有E(G-e)=n-1-1=n-2,由习
题十四题49可知,G-e已不是连通图,故e
为桥。
(5) (6).由于G中每条边均为桥,
因而G中无圈,又由于G连通,所以G为树,由(1) (2)可知,u,v∈V且u≠v,则u与v之间存在唯一的路径Г,则Г∪(u,v)((u,v)为加的新边)为G中的圈,显然圈是唯一的。
(6) (1).只要证明G是连通的。 u,v∈V且u≠v,则新边(u,v)∪G产生唯一的圈,显然有C—(u,v)为G中u 到v的通路,故u~v,由u,v的任意性可知,G是连通的。
设T是n阶非平凡的无向树,
则T中至少有两片树叶。
证设T有a片树叶,由握手定理及定
,
2m=2(n-1)=∑d(vi)≥a+2(n-a)
由上式解出a≥2.
以上两个定理给出了无向树的主要
性质,利用这些性质和握手定理,可以
画出阶数n比较小的所有非同构的无向树。
画出6阶所有非同构的无向树。
解设Ti是6阶无向树。,Ti的边数mi=5,由握手定理可知,
Ti(vj)=10,且δ(Ti)≥1,△(Ti)≤5.
于是Ti的度数列必为以下情况之一。
(1)1,1,1,1,1,5.