1、1第十六章 树主要内容l 无向树及其性质l 生成树l 根树及其应用216.1 无向树及其性质定义 16.1 (1) 无向树 连通无回路的无向图(2) 平凡树 平凡图(3) 森林 至少由两个连通分支且每个都是树组成(4) 树叶 1 度顶点(5) 分支点 度数 2的顶点3无向树的等价定义定理 16.1 设 G=是 n阶 m条边的无向图，则下面各命题是等价的：(1) G 是树(2) G 中任意两个顶点之间存在惟一的路径 .(3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1.(5) G 是连通的且 G 中任何边均为桥 .(6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在
2、所得图中得到惟一的一个含新边的圈 . 4(3)(4). 只需证明 G连通 . 用反证法 . 否则 G有 s（ s2）个连通分支都是小树 . 于是有 mi=ni1, ，这与 m=n1矛盾 . 证明思路(2)(3). 若 G中有回路，则回路上任意两点之间的路径不惟一 . 对 n用归纳法证明 m=n1. n=1正确 . 设 nk时对，证 n=k+1时也对：取 G中边 e，Ge有且仅有两个连通分支 G1,G2(为什么 ?) . nik，由归纳假设得 mi=ni1, i=1,2. 于是， m=m1+m2+1=n1+n22+1=n1.(1)(2). 关键一步是 , 若路径不惟一必有回路 . 5(4)(5)
3、. 只需证明 G 中每条边都是桥 . 为此只需证明命题“G 是 n 阶 m 条边的无向连通图，则 mn1”. 命题的证明 : 对 n归纳 . eE, Ge只有 n2条边，由命题可知 Ge不连通，故 e为桥 . 证明思路(5)(6). 由 (5)易知 G为树，由 (1)(2)知， u,vV（ uv）, u到 v有惟一路径，加新边 (u,v)得惟一的一个圈 . (6)(1). 只需证明 G连通，这是显然的 . 6无向树的特点在结点给定的无向图中，树是边数最多的无回路图树是边数最少的连通图由此可知，在无向图 G = (n, m)中，若 m n-1，则 G是不连通的若 m n-1，则 G必含回路7由上
4、式解出 x 2. 定理 16.2 设 T是 n阶非平凡的无向树，则 T 中至少有两片树叶 . 无向树的性质证 设 T 有 x 片树叶，由握手定理及定理 16.1可知，8例题例 1 已知无向树 T中有 1个 3度顶点， 2个 2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树 . 解 解本题用树的性质 m=n1，握手定理 . 设有 x片树叶，于是 n = 1+2+x = 3+x,2m = 2(n1) = 2(2+x) = 13+22+x解出 x = 3，故 T有 3片树叶 .T 的度数列应为 1, 1, 1, 2, 2, 3，易知 3度顶点与 1个 2度顶点相邻与和 2个 2度顶点均相邻是非同构的，因而有 2棵非同构的无向树 T1, T2，如图所示 . 9例 2 已知无向树 T有 5片树叶， 2度与 3度顶点各 1个，其余顶点的度数均为 4，求 T的阶数 n，并画出满足要求的所有非同构的无向树 . 例题解 设 T的阶数为 n, 则边数为 n1， 4度顶点的个数为 n7. 由握手定理得2m = 2(n1) = 51+21+31+4(n7)解出 n = 8， 4度顶点为 1个 . 10T的度数列为 1, 1, 1, 1, 1, 2, 3, 4，共有 3棵非同构的无向树，如图所示 .例题
