总结－图 基础知识 基本方法 2017年3月6日 西南石油大学.

基础知识 概念：定义、分类、邻接点与邻接边 性质：结点度数、握手定理、同构、完全图、补图、子图、生成子图、导出子图 连通性：无向连通图与连通分支、强连通图与强连通分支 通路：通路与回路、简单(基本)通路与简单(基本)回路、通路与回路长度、欧拉通路与回路、哈密顿通路与回路 2017年3月6日 西南石油大学.

基本方法 表示：邻接阵、邻接表 性质：握手定理 同构：不变量比较、顶点映射构造 连通：邻接矩阵的乘方 2017年3月6日 西南石油大学.

第 7 章 树(I) 树及其应用

第 7 章 树 树是图论中的一个非常重要的概念 在计算机科学中有着非常广泛的应用 本章介绍其基础概念、常见应用、遍历操作 例：现代计算机操作系统均采用树形结构来组织文件和文件夹 本章介绍其基础概念、常见应用、遍历操作 2017年3月6日 西南石油大学.

7.1 概述 伯努利数学世家 2017年3月6日 西南石油大学.

7.1 概述 [定义1] 树(tree) 约定，本章所出现的 Ex.1 无简单回路的连通无向图 图：都是简单图 回路：都是简单回路或基本回路 无环、无平行边，树是简单图 约定，本章所出现的 图：都是简单图 回路：都是简单回路或基本回路 Ex.1 2017年3月6日 西南石油大学.

7.1 概述 练习：下图中哪些是树？为什么？ (a) (b) (c) (d) √ × √ × 2017年3月6日 西南石油大学.

7.1 概述 [定义] 森林(forest) 无简单回路的无向图 森林的连通分支 树 Fig.7-3 2017年3月6日 西南石油大学.

7.1 概述 [定理1] 无向图是树 iff. 每对结点间存在唯一简单通路 无向图是树每对结点有唯一简单通路 树是连通的结点间有简单通路 树无简单回路结点间的简单通路唯一(否则有回路) 图的每对结点有唯一简单通路树 每对结点都有通路图连通 每对结点有唯一通路图无简单回路(否则不唯一) 2017年3月6日 西南石油大学.

7.1 概述 [定义] 如果有向图 G=(V, E) 对应的无向图是树，则称 G 为有向树(directed tree) Fig.7-4 2017年3月6日 西南石油大学.

√ √ × × √ 7.1 概述 练习：下图中哪些是有向树？为什么？ (a) (b) (c) (e) (d) 2017年3月6日 西南石油大学.

7.1 概述 Fig.7-4 [定义2] 如果有向树中有一个结点作为根，每条边的方向都离开根，则称为根树(rooted tree) 根： (唯一的)入度＝0 的结点，其它结点入度＝ 1 叶子：出度＝0 的结点 内点：入度＝1、出度＞0的结点 表示根树时，可忽略边的方向！ 2017年3月6日 西南石油大学.

7.1 概述 练习：给出一下根树的根、叶子、内点 根树可忽略边的方向！ v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 2017年3月6日 西南石油大学.

7.1 概述 练习：画出有 4 个结点的不同构的根树 2017年3月6日 西南石油大学.

7.1 概述 根树的术语：设根树 T=(V, E) 若 (u, v)∈E，则 u 是 v 的父母(parent)，v 是 u 的子女(child) u 到 v 存在有向边 若(u, v1)∈E，(u, v2)∈E，则 v1 与 v2 互为兄弟(sibling) 兄弟顶点有共同父母 若 u 到 v 有通路存在，则称 u 是 v 的祖先(ancestor)，v 是 u 的后裔(descendant) Ex.2 2017年3月6日 西南石油大学.

7.1 概述 Ex.2 设根树 T=(V，E)，a 是 T 的内点，Va 是 a 及其后裔的集合，Ea 是 a 到各后裔通路上边的集合，则 Ta=(Va，Ea) 称为 T 的以 a 为根的子树(subtree) 以 a 为根的子树：包含根顶点 a a 的子树：以 a 的子女为根的子树 2017年3月6日 西南石油大学.

7.1 概述 [定义3] 每个内点最多有 m 个子女的根树称为 m 元树(m-ary tree) Ex.3 [定义3] 每个内点最多有 m 个子女的根树称为 m 元树(m-ary tree) [定义] 每个内点恰有 m 个子女的根树称为 m 元正则树(full m-ary tree) m=2 的正则 m 元树称为二叉树(binary tree) 2017年3月6日 西南石油大学.

7.1 概述 [定义] 若在根树中规定了子女顺序，则称为有序树(ordered tree) 每个内点最多有 m 个子女的有序树称为 m 元有序树 每个内点恰有 m 个子女的有序树称为 m 元正则有序树 2017年3月6日 西南石油大学.

7.1 概述 根树 vs. 有序树 同构的有根树，非同构的有序树 2017年3月6日 西南石油大学.

7.1 概述 有序二叉树 Ex.4 左子女(left child)：内点的左边子女 右子女(right child)：内点的右边子女 左子树(left subtree)：左子女为根的子树 右子树(right subtree)：右子女为根的子树 Ex.4 2017年3月6日 西南石油大学.

7.1 概述 练习：判断下图所示根树的类型 3 元树 3 元有序正则树 3 元正则树 (a) (b) 1 2 (c) 3 2017年3月6日 西南石油大学.

7.1.1 树模型 Ex.5 化合物结构 Ex.6 职务层次 Ex.7 文件目录 表示层次结构或分类结构 树模型的描述能力： 2017年3月6日 西南石油大学.

- + Ex. 表达式计算顺序  * 从下向上，从左到右 a b c d e f g h i j 计算顺序： 2017年3月6日 西南石油大学.

7.1.2 树的性质 树是可平面图 去掉树的任一边，就构成森林 树上任意添加一条边，将产生唯一回路 树是固定结点数下边数最少的连通图 树是固定结点数下边数最多的无回路图 2017年3月6日 西南石油大学.

7.1.2 树的性质 [定理2] 有 n 个结点的树有 n-1 条边 [定理] 设树 T 有 n 个结点、m 条边，则 n=m+1 [归纳假设] 设 n≤k 时成立 [归纳递推] 当 n＝k 时 移去一条边，形成 2 棵树 T1 和 T2(顶点个数都≤k) 由归纳假设有 n1=m1＋1，n2=m2＋1 又 m1＋m2 = m－1 故 n = n1＋n2= m1＋1＋m2＋1 = (m1＋m2＋1)＋1= m＋1 2017年3月6日 西南石油大学.

7.1.2 树的性质 若无向图 G 有 n 个结点、m 条边，则 m=n - 1 若 m＜n-1，则 G 是不连通的 2017年3月6日 西南石油大学.

7.1.2 树的性质 [定理3] 设有 i 个内点的正则 m 元树结点数为 n，则关系 n＝m×i＋1 成立 2017年3月6日 西南石油大学.

7.1.2 树的性质 [定理4] 设正则 m 元树叶子数为 l Ex.9 若顶点数=n，则 若内点数=i，则 若树叶数=l，则 内点数 i=(n-1)/m，树叶数 l=[(m-1)n+1]/m 若内点数=i，则 顶点数 n=mi+1，树叶数 l=(m-1)i+1 若树叶数=l，则 顶点数 n=(ml-1)(m-1)，内点数 i=(l-1)/(m-1) Ex.9 2017年3月6日 西南石油大学.

7.1.2 树的性质 练习：证明 3 结点以上的树 T 最少有两片叶子 设：T 的结点数＝n，边数＝m ∵树是连通图，∴T 中结点度数≥1 设 T 中有 k 个 1 度结点，其余结点度数≥2 由握手定理有： 又 m＝n－1，则 2(n－1)≥2n－k，求解得 k≥2 2017年3月6日 西南石油大学.

7.1.2 树的性质 练习：假设有一台计算机，它有一条加法指令，可计算 3 个数的和。如果要求 9 个数 x1, x2, x3, x4, x5, x6, x7, x8, x9 之和，问至少要执行几次加法指令？ 2017年3月6日 西南石油大学.

7.1.2 树的性质 分析：1 次算 3 个数之和，共 9 个数 i=(l-1)/(m-1) x1 x2 x3 x4 x5 x6 x7 x9 (a) (b) x1 x2 x3 x4 x5 x6 x7 x8 x9 i=(l-1)/(m-1) 2017年3月6日 西南石油大学.

7.1.2 树的性质 [定义] 结点 v 的通路长或层(level)是指从根到 v 边的条数，记为l(a) Ex.10 [定义] 结点 v 的通路长或层(level)是指从根到 v 边的条数，记为l(a) [定义] 根树的高度(height) 是根到最远结点 v 的通路长度，即 h=max(l(v))，v∈V 2017年3月6日 西南石油大学.

× 7.1.2 树的性质 [定义] 若高度为 h 的 m 元树的所有顶点都在 h 层或 h-1 层，则称为平衡树 Ex.11 2017年3月6日 西南石油大学.

7.1.2 树的性质 [定理5] 高度 h 的 m 元树最多有 mh 个叶子 证明：数学归纳法 [基础] h=1，根的子女都是叶子 2017年3月6日 西南石油大学.

7.1.2 树的性质 [推论] 设高度 h 的 m 元树有 l 个叶子，则 h≥ 若树是正则且平衡的，则 h= 2017年3月6日 西南石油大学.

7.1.2 树的性质 [定义] 若树高为 h 的 m 元树有 mh 个叶子，则称为 m 元完全树(complete m-ary tree) 完全树是正则树 2017年3月6日 西南石油大学.

作业四(计科2013) P252 18. P260 21. P266 23. P274 10. 16. 2017年3月6日 西南石油大学.

7.2 树的应用 二叉搜索(二分搜索) 决策树 前缀码 博弈树 2017年3月6日 西南石油大学.

7.2.2 二叉搜索树 在表中通过搜索的方法查找项目 表中项目排成一个有序的二叉树 Ex.1 左小右大 2017年3月6日 西南石油大学.

7.2.2 二叉搜索树 二叉搜索树：有序的二叉树 最优二叉搜索树：平衡二叉树 以不同顶点为根，构造的树结构不同 树结构不同，搜索时的比较次数不同 平衡的二叉搜索树比较次数最少 最优二叉搜索树：平衡二叉树 2017年3月6日 西南石油大学.

7.2.3 决策树 表示决策过程的根树 内点：决策，子树：后果，叶：结果 2017年3月6日 西南石油大学.

7.2.3 决策树 Ex. 有 5 枚外观一样的硬币，其中 1 枚伪币重量不同，请问如何使用一架天平来找出那枚伪币？ 用天平来称两枚硬币A、B，只有 A＜B、A = B、A＞B 三种可能的情形，因此可构造 3 元决策树 2017年3月6日 西南石油大学.

7.2.3 决策树 硬币A、B，有A＜B、A = B、A＞B 三种可能情形 C:D A:B ?:E E重 E轻 ＜ ＞ C:E D轻 C重 ＝ D重 C轻 A:? B重 A轻 B轻 A重 2017年3月6日 西南石油大学.

7.2.3 决策树 Ex. 假设伪币轻 Ex.2 更快的判别方法：“二分法” E AB:CD ＜ A:B ＝ ＞ C:D D A B C 2017年3月6日 西南石油大学.

7.2.3 决策树 练习：有 5 枚外观相同的硬币(其中 2 枚伪币较重)，请画出用天平来找出 2 枚伪币的决策树？ 顶点标记＝x/y：硬币 x 在左、y 在右 叶标记＝xHyH：硬币x、y 是伪币(较重) 2017年3月6日 西南石油大学.

7.2.3 决策树 练习：称出 5 枚硬币中 2 枚较重伪币 2017年3月6日 西南石油大学.

7.2.4 前缀码(prefix code) 计算机用 0、1 序列来表示和存储信息，通讯编码类似 a－z 编码为 00000－11111 eat 00100 00000 11001 2017年3月6日 西南石油大学.

7.2.4 前缀码(prefix code) 能否用不同位数的二进制串来编码信息，尽量缩短通讯时序列的长度？ e－0，a－1，t－01 0101 tea 0101? 需要避免二义性！ eaea tt 2017年3月6日 西南石油大学.

7.2.4 前缀码(prefix code) 用不同位数的二进制串来编码，同时避免二义性 e－0，a－10，t－11 任一编码都不是其它编码的前缀！ eat 01011 0 10 11eat 2017年3月6日 西南石油大学.

7.2.4 前缀码(prefix code) 一个二进制位串集合，如果这些二进制序位串互不为前缀，则称此集合为前缀码(prefix code) 表示为：二元有序加权正则树 内点左边的权＝0，右边的权＝1 叶：一个编码 每个叶有一条从根到叶的路径 路径上的权排成序＝叶的编码 Fig. 9-20 2017年3月6日 西南石油大学.

7.2.4 前缀码(prefix code) 前缀码：二元有序加权正则树 只有内点才可能是叶的前缀，而内点不对应一个码，故这样一棵树所有叶对应的码构成前缀码 最长码长是树高 h 2017年3月6日 西南石油大学.

7.2.4 前缀码(prefix code) 前缀码：字母使用频率越高，编码越短 Huffman 算法：数据压缩编码基本算法 单词编码总长度最小 Huffman 算法：数据压缩编码基本算法 自底向上构造前缀码 2017年3月6日 西南石油大学.

7.2.4 前缀码(prefix code) Huffman 算法：自底向上构造前缀码 Ex. 4 初始：所有字母看成单顶点的二叉树 根的权值＝顶点频率 从所有二叉树中，选取根权值最小的 2 棵，构造新二叉树 根权值＝子树的根权值之和 重复上述过程，直到形成编码树 Ex. 4 2017年3月6日 西南石油大学.

7.2.5 博弈树 博弈：选手交替动作，直至结束 博弈树：研究博弈比赛策略 围棋、象棋、五子棋、跳棋 顶点：方框/圆圈选手1/2 标记值：当前状态，权值：选手得分 1选手 1 获胜，-1选手 2 获胜 边：合法动作 2017年3月6日 西南石油大学.

7.2.5 博弈树 博弈树：表示比赛的全部结局 Ex. 5 根：开局 2017年3月6日 西南石油大学.

7.2.5 博弈树 博弈树：表示比赛的全部结局 Ex. 5 内点：中间局面 标记：状态值 1： 选手 1 获胜 -1：选手 2 获胜 +1 －1 内点：中间局面 标记：状态值 1： 选手 1 获胜 -1：选手 2 获胜 权值：得分 叶：终局 2017年3月6日 西南石油大学.

7.2.5 博弈树 博弈树：研究比赛的获胜策略 内点权值：取子女权值中的最优 Ex. 7 +1 -1 -1 最大最小策略 选手 1：最大(max) 选手 2：最小(min) Ex. 7 +1 +1 －1 -1 -1 2017年3月6日 西南石油大学.

7.2.5 博弈树 获胜策略：根的权值 Ex. 7 选手 1 可获胜 2017年3月6日 西南石油大学.

7.2.5 博弈树 练习：有 7 根火柴，甲、乙两人依次从中取走 1 根或 2 根，但不能不取，规定取走最后一根的就是胜利者。请利用博弈树确定游戏获取策略？ 2017年3月6日 西南石油大学.

7.2.5 博弈树 练习：7 根火柴，两人轮流取 1或 2 根 6 7 5 4 1 -1 2 3 (a) 1：甲可获胜(按正确步骤) 2017年3月6日 西南石油大学.