文档介绍：第十章树与有序树
树的基本概念
连通图的生成树和带权连通图的最小生成树
有序树
前缀码和最优二分树
例
Peter
Godfried
Betty
Albert
Mary
Marivin
Doris
Judy
Hal
Denise
Gregory
树的定义
一个无向图若连通且不含圈,则称它为一棵树,记为 T=(V,E)。
设T是一棵树, T中度数为1的顶点称为树叶,度数大于1的顶点称为分枝点。
例是否为树?
例1 画出所有5个顶点的树
定理1 设 T=(V,E)是一棵树,则有|E|=|V|-1。
分析:对顶点数|V|进行归纳法证明。
当|V|=1和|V|=2时,定理显然是成立的。
归纳假设当|V|≤k时,定理成立。
考察|V|=k+1时的情况。
因为树无圈,所以从T中去掉任何一条边,都会使T变成具有两个连通分支的不连通图。这两个连通分支也必然是树,譬如说是T1=(V1,E1)和T2=(V2,E2)。
显然,|V1| ≤k, |V2| ≤k。根据归纳假设,有|E1|=|V1|-1, |E2|=|V2|-1。而|V|=|V1|+|V2|, |E|=|E1|+|E2|+1, 所以|E|=|V|-1, 即定理得证。
定理1的证明
证明:用对顶点集V的元素个数归纳法来证。
当|V|=1时,T是一个仅有一个顶点且没有边的图。显然,|E|=0, 命题成立。
归纳假设若|V|≤k时,命题成立。考察|V|=k+1时的情况。设{u’,v’} ∊E ,我们擦去边e, 得T的一个子图。令
V1={v∊V│子图中存在u’到v的通路},
V2={v∊V│子图中存在v’到v的通路}。
例
定理1的证明(续)
新图分为两个连通的子图. 因为对于任意的v∊V,原图是连通的,所以在原图中存在 v到u’的通路,也存在v到v’的通路,且都是初等通路。若这两条通路都经过边e,则原图中一定有圈,故V=V1∪V2 。如果存在v ∊ V1∩V2,则原图中存在 v到u’、v到v’的两条不经过边e的初等通路,加上边e后, 原图中一定有圈,故V1∩V2 =Ø。
新图分为两棵不相交的树. 原图无圈,子图也不会有圈,即为两棵不相交的树(顶点的交集为空集)。
设T1=(V1,E1),T2=(V2,E2),由归纳假定有
|V1|-1=|E1|,|V2|-1=|E2|。
又|V|=|V1|+|V2|,|E|=|E1|+|E2|+1。所以有定理得证。
定理1的推论
任何一棵至少含有两个顶点的树至少有两片树叶。
证明:设 T=(V,E)是一棵树,若T中最多只有一片树叶,则有
∑d(v) ≥1+2(|V|-1)=2|E|+1,
这与结论∑ d(v) =2|E| 矛盾!
矛盾说明 T 不止一片树叶。
v∊V
v∊V
例设T为树,最大度△≥k,这里k≥1, 证明T至少有k片树叶。
证明:假设T有s片树叶,s<k。
记T的顶点数为n,则
T有1个△度顶点,有s片树叶,
还有(n-s-1)个不少于2度的顶点。
由握手定理可知:
2(n-1) ≥2(n-s-1)+k+s
可以解出 s≥k,这与假设s<k矛盾。
例2
已知一棵树有5个4度顶点,3个3度顶点,3个2度顶点,问有几个一度顶点?
解:设有 x个1度顶点,则依题意有方程: 5•4+3•3+3•2+1•x
= ∑ d(v) =2|E| =2(|V|-1)
=2(5+3+3+ x-1)
∴ x=15