离散数学-树.ppt

1
第7章树
无向树及生成树
根树及其应用
2
无向树及生成树
无向树与森林
生成树与余树
基本回路与基本回路系统
基本割集与基本割集系统
最小生成树与避圈法
3
无向树
无向树: 无回路的连通无向图
平凡树: 平凡图
森林: 每个连通分支都是树的非连通的无向图
树叶: 树中度数为1的顶点
分支点: 树中度数2的顶点
右图为一棵12阶树.
注:本章中所讨论的回路均
指简单回路或初级回路
树的应用
英国数学家凯莱(Arthur Cayley)于19世纪中叶研究
H2n+2的同分异构体时提出树的概
念. 当n=1,2,3时, 都只有一棵非同构的树; 当n=4时,
有2棵不同构的树.
4
甲烷
乙烷
丙烷
丁烷
异丁烷
5
无向树的性质
定理设G=<V,E>是n阶m条边的无向图, 则下面各命
题是等价的:
(1) G是树(连通无回路);
(2) G中任意两个顶点之间存在惟一的路径;
(3) G中无回路且m=n1;
(4) G是连通的且m=n1;
(5) G是连通的且G中任何边均为桥;
(6) G中没有回路, 但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈.
6
无向树的性质(续)
定理设T 是 n 阶非平凡的无向树,则T中至少有两片树叶.
证设T有x片树叶, 由握手定理及前面的定理,
2(n-1)x+2(n-x)
解得 x2.
7
例题
例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶点全
是树叶. 试求树叶数, 并画出满足要求的非同构的无向树.
解用树的性质m=n1和握手定理.
设有x片树叶,于是
n=1+2+x=3+x,
2m=2(2+x)=13+22+x
解得x=3,故T有3片树叶.
T的度数列为1, 1, 1, 2, 2, 3
有2棵非同构的无向树.
8
例题
例2 已知无向树T有5片树叶, 2度与3度顶点各1个, 其余顶点
的度数均为4. 求T的阶数n, 并画出满足要求的所有非同构的
无向树.
解设T的阶数为n, 则边数为n1, 4度顶点的个数为n7.
由握手定理得
2m=2(n1)=51+21+31+4(n7)
解得n=8, 4度顶点为1个.
T的度数列为1,1,1,1,1,2,3,4
有3棵非同构的无向树
9
生成树
设G为无向连通图
G的生成树: G的生成子图并且是树
生成树T的树枝: G在T中的边
生成树T的弦: G不在T中的边
生成树T的余树: 所有弦的集合的导出子图
注意: 不一定连通, 也不一定不含回路.
黑边构成生成树
红边构成余树
10
生成树的存在性
定理任何无向连通图都有生成树.
证用破圈法. 若图中无圈, 则图本身就是自己的生成树.
否则删去圈上的任一条边, 这不破坏连通性, 重复进行
直到无圈为止,剩下的图是一棵生成树.
推论设n阶无向连通图有m条边, 则mn1.