第09章 树.ppt

第九章 树 基本要求: 掌握树的定义, 生成树, 最小生成树和m叉树的概念。 了解二叉有哪些信誉好的足球投注网站树、决策树的概念, 前缀码, 树的遍历算法。 重点: 树的定义, 生成树, m叉树的概念, 树的顶点与分枝的关系及其证明, 最小生成树。 难点: 树的顶点与分枝的关系及其证明。 第九章 树 树是图论中重要的概念之一, 它在计算机科学中应用非常广泛, 这里将介绍树的一些基本性质和应用。 9.1 无向树及生成树 9.2 根树及其应用 9.3 题例分析 9.1 无向树及生成树 一、无向树的概念 定义9.1 一个连通且无回路的无向图称为无向树, 简称 树, 常用T 表示。 平凡图称为平凡树。 设T=V,E为一棵树, v?V, 若d(v)=1, 则称 v为 T 的树叶; 若d(v)≥2, 则称 v为 T 的分支点。 每个连通分支是树的无向图称为森林。 例: 如图为 9 个顶点的树。 二、无向树的性质 定理9.1 设 G＝V, E, |V|=n, |E|=m, 则下面各命题是等价的。 (1) G是连通而无回路的图是树; (2) G 中每对顶点之间存在唯一的通路; (3) G 是连通的且 m＝n?1; (4) G 中无回路且 m＝n?1; (5) G 中无回路, 但在G中任意两个不相邻的顶点之间增加一边, 就形成唯一的一条初级回路; (6) G 是连通的且G中每条边都是割边(桥)。 二、无向树的性质 定理9.2 设 T=V,E是 n 阶非平凡的无向树, 则 T 中至少有 2片树叶。 证: 因 T 是连通, 则 ?v?T, deg(v)≥1。 设 T 有 k 片树叶, 则有(n?k)个顶点的度均大于等于2, 则由握手定理可知 2m =∑d(vi) , ( i=1, 2, …, n ) ≥ k ? 2(n?k) = 2n?k。 又 ∵ T 是树, 有 m = n?1 ∴ 2(n?1)≥2n?k, 故 k≥2。 # 例 画出 6 阶所有非同构的无向树。 解: 设 Ti 是 6 阶无向树。 由定理9.1可知, Ti 的边数 mi＝6-1＝ 5, 由握手定理知, ∑dTi(vj)＝10, 且?(Ti)≥1, △(Ti)≤5。 于是Ti 的度数列必为以下情况之一。 例: 6 阶所有非同构的无向树如下图所示。 人们常称只有一个分支点, 且分支点的度数为 n-1的 n (n≥3) 阶无向树为星形图, 称唯一的分支点为星心。 例:7 阶无向图有 3片树叶和 1个3度结点, 其余 3个结点的度数均无 1和3。试画出满足要求的所有非同构的无向树。 解: 设 Ti 为满足要求的无向树, 则边数 mi＝6, 于是 ∑d(vj)＝12＝1?3+3+d(v4)+d(v5)+d(v6)。 由 d(vj)≠1∧d(vj)≠3, 且 d(vj)≥1∧d(vj)≤6, j＝4,5,6。 可知 d(vj)＝2, j＝4,5,6。于是 Ti 的度数列为: 1, 1, 1, 2, 2, 2, 3 由度数列可知, Ti 中有一个3 度顶点vi , vi 的邻域N(vi)中有 3个顶点, 这 3个顶点的度数列只能为以下三种情况之一: 1, 1, 2 1, 2, 2 2, 2, 2 设它们对应的树分别为 T1,T2,T3。此度数列只能产生这三棵非同构的 7 阶无向树。 例: 画出满足要求的所有非同构的无向树 例: 已知无向树 T 中, 有1个3度结点, 2个2度结点, 其余结点全是树叶。试求树叶数, 并画出满足要求的非同构的无向树。 解: 设有 x片树叶, 则顶点总数为 n ＝ 1 + 2 + x ＝ 3 + x 由握手定理和树的性质(m＝n?1)知, 2m ＝ 2(n?1) ＝ 2×( 2 + x ) ＝ 1×3 + 2×2 + x 解出 x＝3, 故T 有 3片树叶。 故 T 的度序列为: 1, 1, 1, 2, 2, 3。 ∵ 3度顶点的邻域有: 1, 1, 2和1, 2, 2 ∴ T 有两棵非同构的树。 例: 已知无向树 T有 5片树叶, 2度与 3度顶点各 1个, 其余顶点的度数均为 4。求 T 的阶数 n, 并画出满足要求的所有非同构的无向树。 解: 设 T 的阶数为n, 则边数为n?1, 4 度顶点的个数为: n?5?1?1= n ? 7 由握手定理得 2 m = 2(n?1) = 1 ? 5 + 2 ?1 + 3?1 + 4 ?(n?7) ∴ n = 8, 即 4 度结点为 1 个。 故 T 的度数列为: