离散数学-树.pptx

1
主要内容
无向树及其性质
生成树
根树及其应用
第十六章树
2
无向树及其性质

(1) 无向树——连通无回路的无向图
(2) 平凡树——平凡图
(3) 森林——至少由两个连通分支(每个都是树)组成
(4) 树叶——1度顶点
(5) 分支点——度数2的顶点
3
无向树的等价定义
设G=<V,E>是n阶m条边的无向图,则下面各命题
是等价的:
(1) G 是树
(2) G 中任意两个顶点之间存在惟一的路径.
(3) G 中无回路且 m=n1.
(4) G 是连通的且 m=n1.
(5) G 是连通的且 G 中任何边均为桥.
(6) G 中没有回路,但在任何两个不同的顶点之间加一条新边,在所得图中得到惟一的一个含新边的圈.
4
(3)(4). 只需证明G连通. 用反证法. 否则G有s(s2)个连通分支都是小树. 于是有mi=ni1, ,
这与m=n1矛盾.
证明思路
(2)(3). 若G中有回路,则回路上任意两点之间的路径不
惟一. 对n用归纳法证明m=n1.
n=1正确. 设nk时对,证n=k+1时也对:取G中边e,
Ge有且仅有两个连通分支G1,G2(为什么?) . nik,由归纳
假设得mi=ni1, i=1,2. 于是,m=m1+m2+1=n1+n22+1=n1.
(1)(2). 关键一步是, 若路径不惟一必有回路.
5
(4)(5). 只需证明G 中每条边都是桥. 为此只需证明命题
“G 是 n 阶 m 条边的无向连通图,则 mn1”.
命题的证明: 对n归纳.
eE, Ge只有n2条边,由命题可知Ge不连通,故e为桥.
证明思路
(5)(6). 由(5)易知G为树,由(1)(2)知,u,vV(uv),
u到v有惟一路径,加新边(u,v)得惟一的一个圈.
(6)(1). 只需证明G连通,这是显然的.
6
由上式解出x  2.
设T是n阶非平凡的无向树,则T 中至少有两片树叶.
无向树的性质
证设 T 有 x 片树叶,,
7
实例
例1 已知无向树T中, 有1个3度顶点, 2个2度顶点, 其余顶
点全是树叶. 试求树叶数, 并画出满足要求的非同构的无
向树.
解设有x片树叶,
2(2+x)=13+22+x
解得x=3,故T有3片树叶.
T的度数列为1, 1, 1, 2, 2, 3
8
实例
例2 画出所有6阶非同构的无向树
解 5条边, 总度数等于10
可能的度数列:
(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
(1)
(2)
(3)
(4a)
(4b)
(5)
9
不一定连通,也不一定不含回路,如图所示
设G为无向图
(1) G的树——T 是G 的子图并且是树
(2) G的生成树——T 是G 的生成子图并且是树
(3) 生成树T的树枝——T 中的边
(4) 生成树T的弦——不在T 中的边
(5) 生成树T的余树——全体弦组成的集合的导出子图
生成树
10
生成树的存在性
任何无向连通图都有生成树.
证用破圈法. 若图中无圈, 则图本身就是自己的生成树.
否则删去圈上的任一条边, 不破坏连通性, 重复进行直到
无圈为止, 得到图的一棵生成树.
推论1 设n阶无向连通图有m条边, 则mn1.
推论2 设n阶无向连通图有m条边, 则它的生成树的余树
有mn+1条边.