1、1第十章 树的介绍主要内容l 无向树及其性质l 生成树l 根树及其应用10.1 无向树及其性质定 义 10.1 连 通无回路的无向 图 称 为 无向 树 , 简 称 树 . 每个连通分支都是 树 的无向 图 称 为 森林 . 平凡 图 称 为 平凡 树 . 在无向 树 中 , 悬 挂 顶 点称 为 树 叶 , 度数大于或等于 2的 顶 点称 为分支点 例f星形树3无向树的性质定理 10.1 设 G=是 n阶 m条边的无向图，则下面各命题是等价的：(1) G 是树(2) G 中任意两个顶点之间存在惟一的路径 .(3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1.(5) G 是连
2、通的且 G 中任何边均为桥 .(6) G 中没有回路，但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈 . 4(3)(4). 只需证明 G连通 . 用反证法 . 否则 G有 s(s2)个连通分支 , 它们都是树 . 于是 , 有 mi=ni1,这与 m=n1矛盾 . 证明(2)(3). 若 G中有回路，则回路上任意两点之间的路径不惟一 . 对 n用归纳法证明 m=n1. 当 n=1时成立 . 设 nk时成立，证 n=k+1时也成立：任取一条边 e， Ge有且仅有两个连通分支 G1,G2 . nik，由归纳假设得 mi=ni1, i=1,2. 于是，m=m1+m2+1=n1+
3、n22+1=n1.证 (1)(2). 若路径不惟一 , 必有回路 . 5(4)(5). 只需证明 G 中每条边都是桥 . 下述命题显然成立 : G是 n 阶 m 条边的无向连通图，则 mn1. eE, Ge只有 n2条边，由命题可知 Ge不连通，故 e为桥 . 证明(5)(6). 由 (5)易知 G为树 . 由 (1)(2)知， u,vV（ uv）, u到 v有惟一路径，加新边 (u,v)得惟一的一个圈 . (6)(1). 只需证明 G连通，这是显然的 . 解得 x 2. 定理 10.2 设 T是 n阶非平凡的无向树，则 T 中至少有两片树叶 . 无向树的性质证 设 T 有 x 片树叶，由握手
4、定理及定理 10.1可知，例 1 已知无向树 T中有 1个 3度顶点， 2个 2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树 . 解 设有 x片树叶， n = 3+x.2m = 2(n1) = 2(2+x) = 13+22+x解出 x = 3，故 T有 3片树叶 .7例 2 已知无向树 T有 5片树叶， 2度与 3度顶点各 1个，其余顶点的度数均为 4，求 T的阶数 n，并画出满足要求的所有非同构的无向树 . 例题解 设 T的阶数为 n, 则边数为 n1， 4度顶点的个数为 n7. 由握手定理 , 2m = 2(n1) = 51+21+31+4(n7),解出 n = 8
5、， 4度顶点为 1个 . 810.2 生成树定 义 10.2 如果无向 图 G的生成子 图 T是 树 ， 则 称 T是 G的 生成 树 . 设 T是 G的生成 树 ， G的在 T中的 边 称 为 T的 树 枝 ，不在 T中的 边为 T的 弦 . 称 T的所有弦的 导 出子 图为 T的 余 树 ，记 作 . 例9定理 10.3 无向 图 G有生成 树 当且 仅 当 G连 通 .生成树存在条件推论 G为 n阶 m条边的无向连通图，则 mn1. 证 必要性 显 然 . 证 充分性若 G中无回路， 则 G为 自己的生成 树 若 G中含圈，任取一圈，随意地 删 除圈上的一条边 ; 若仍有圈 , 再任取一
6、个圈并 删 去 这 个圈上的一条 边 ，重复 进 行 , 直到最后无圈 为 止 . 最后得到的 图 无圈（当然无回路）、 连 通且是 G的生成子 图 ，因而是 G的生成 树 这个产生生成树的方法称为 破圈法 10最小生成树定 义 10.3 设 无向 连 通 带权图 G=， T是 G的一棵生成树 ， T的各 边权 之和称 为 T的 权 ， 记 作 W(T) G的所有生成树中 权 最小的生成 树 称 为 G的 最小生成 树 .避圈法 （ Kruskal）输入 : 连通图 G=输出 : G的最小生成树 T 1. 将 G中非环边按权从小到大排列 : W(e1)W(e2) W(em).2. 令 Te1, i2.3. 若 ei与 T中的边不构成回路 , 则令 TTei.4. 若 |T|n-1, 则令 ii+1, 转 3.
