图论课件 - 04-2015

第九章

树

树是图论中的一个非常重要的概念，而 在计算机科学中有着非常广泛的应用，例如 现代计算机操作系统均采用树形结构来组织 文件和文件夹，本章介绍树的基本知识和应 用。

定义1

无向树：连通而不含回路的无向图称为无向树， 简称树，常用T表示树。 叶：树中度数为1的结点； 分支点或内部结点：度数大于1的结点； 森林：每个连通分支都是树的无向图。

§9.1 树

注：树中没有环和平行边，因此一定是简单图

例1

判断下图中的图哪些是树？为什么？

(a) (b) (c) (d) 分析 判断无向图是否是树，根据定义1，首先看它 是否连通，然后看它是否有回路。

定理1 设无向图G = ，|V| = n，|E| = m，下 列各命题是等价的： ① G连通而不含回路(即G是树)； ② G中无回路，且m=n-1； ③ G是连通的，且m=n-1；

④ G中无回路，但在G中任二结点之间增加一条 新边，就得到惟一的一条基本回路； ⑤ G是连通的，但删除G中任一条边后，便不连 通；(n≥2) ⑥ G中每对结点间有惟一一条基本通路。(n≥2)

例2：无向树G有5片树叶，3个2度分支点，其

余分支点均为3度，问G有多少个结点？

解：由握手定理 2m=∑d(vi) 及定理1 n= m+1 设G有n个顶点,则有下列关系式

5 ×1+3 ×2+(n-5-3) ×3=2 ×(n-1) 解得：n=11

本文来源：https://www.bwwdw.com/article/jskh.html