1、电子科技大学离散数学课程组 国家精品课程 双语示范课程离 散 数 学*电子科技大学计算机科学与工程学院电子科技大学离散数学课程组 国家精品课程 双语示范课程82-2*第 10章 树 树 是图论中的一个非常重要的概念，而在计算机科学中有着非常广泛的应用，例如 现代计算机操作系统 均采用树形结构来组织文件和文件夹，本章介绍树的 基本知识和应用 。在本章中，所谈到的图都假定是 简单图 ；所谈到的回路均指 简单回路 或 基本回路 。并且同一个图形表示的回路 (简单的或基本的 )，可能有不同的 交替序列 表示方法，但我们规定它们表示的是同一条回路。电子科技大学离散数学课程组 国家精品课程 双语示范课程8
2、2-3*10.0 内容提要 1. 与树相关的概念： 树、森林、根树、根、叶、分支点、生成树、最小生成树、 k元树、 k元完全树、子树、有序树、祖先与后代、父亲与儿子、最优树等；2. 树的基本性质： m = n-1等；3. 树的算法：求生成树与最小生成树的算法、求最优树的算法、二元树遍历的算法、根树与二元树相互转化的算法等；4. 树的应用。电子科技大学离散数学课程组 国家精品课程 双语示范课程82-4*10.1 本章学习要求重点掌握 一般掌握 了解11 与树相关基本概念2 树的性质3 树的基本算法 31 树的同构2 树的应用2树的算法 电子科技大学离散数学课程组 国家精品课程 双语示范课程82-
3、5*10.2 树 10.2.1 树的定义与性质例 10.2.1 2006年德国世界杯 8强的比赛结果图，最后胜利的队捧得大力神杯。德 国阿根廷意大利乌克兰英格兰葡萄牙巴 西法 国德 国意大利葡萄牙法 国意大利法 国意大利电子科技大学离散数学课程组 国家精品课程 双语示范课程82-6*定义 10.2.1n 连通而不含回路的无向图称为 无向树 (Undirected Tree)，简称 树 (Tree)，常用 T表示树。n 树中度数为 1的结点称为 叶 (Leaf)；度数大于 1的结点称为 分支点 (Branch Point)或 内部结点(Interior Point)。n 每个连通分支都是树的无向
4、图称为 森林 (Forest)。n 平凡图称为 平凡树 (Trivial Tree)。 树中 没有 环 和 平行边 ，因此一定是 简单图 在任何非平凡树中，都 无度数为 0的结点。电子科技大学离散数学课程组 国家精品课程 双语示范课程82-7*例 10.2.2判断下图中的图哪些是树？为什么？ (a) (b) (c) (d)分析 判断无向图是否是树，根据定义 10.2.1，首先看它是否连通，然后看它是否有回路。解 图 (a)、 (b)都是连通，并且不含回路，因此是树；图 (c)不连通，因此不是树，但由于它不含回路，因此是森林；图 (d)虽然连通，但存在回路，因此不是树。电子科技大学离散数学课程组
5、 国家精品课程 双语示范课程82-8*树的性质 定理 10.2.1 设无向图 G = ， |V| = n， |E| = m，下列各命题是等价的： G连通而不含回路 (即 G是树 )； G中 无回路 ，且 m = n-1； G是 连通的 ，且 m = n-1； G中 无回路 ，但在 G中 任二结点之间增加一条新边，就得到惟一的一条基本回路 ； G是 连通的 ，但 删除 G中任一条边后，便不连通 ；(n2) G中 每一对结点之间有惟一一条基本通路 。 (n2)电子科技大学离散数学课程组 国家精品课程 双语示范课程82-9*分析直接证明这 6个命题两两等价工作量太大，一般采用循环论证的方法，即证明(
6、1) (2) (3) (4) (5) (6) (1)然后利用传递性，得到结论。电子科技大学离散数学课程组 国家精品课程 双语示范课程82-10*证明 (1) (2)：对 n作归纳。 n = 1时， m = 0，显然有 m = n-1。假设 n = k时命题成立，现证 n = k+1时也成立。由于 G连通而无回路，所以 G中至少有一个度数为 1的结点 v0，在 G中删去 v0及其关联的边，便得到 k个结点的连通而无回路的图，由归纳假设知它有 k-1条边。再将结点 v0及其关联的边加回得到原图 G，所以 G中含有 k+1个结点和 k条边，符合公式 m = n-1。所以， G中无回路，且 m = n-1。 G连通而不含回路 (即 G是树 ) G中 无回路 ，且 m = n-1；
