第8章 节 +图论-8（树） 离散数学-图论课件.ppt

8.3.1 平面图的定义 [可平面性] 一个图 G=(V,E) ，若能将其画在平面上，且任意两条边的交点只能是G的顶点，则称G可嵌入平面，或称G是可平面的。可平面图在平面上的一个嵌入称为一个平面图。 树是一类重要的平面图。 应用举例：印刷电路版、集成电路设计。 (a) (b) (c) (a)是可平面图，(b),(c) 是(a)的平面嵌入，是平面图。 * 返回 结束 第八章 图论-2 8.1 Euler图与Hamilton图 8.2 树 8.2.1 树的概念和基本性质 8.2.2 几类常用树 根树 有序树 最优二叉树 8.2.3 生成树 8.3 平面图 8.2 树 树的术语起源于植物学和家谱学。早在1857年，英国数学Arthur Cayley(1821—1895)就发现了树，当时他正在试图列举形为CnH2n+2的化合物的同分异构体。树具有广泛的应用，特别在计算机科学与管理科学中。如用树构造存储和传输数据的有效编码，用树构造最便宜的电话线连接分布式计算机网络，用树模拟一系列决策完成的过程等。 8.2.1 树的概念和基本性质 在图论中： 1、连通的无环图称为树。 2、除根之外， 度＝1的顶点称为叶子，度＞1的顶点称为分支点或者内点。 叶子 分支点 根 8.2.1 树的概念和基本性质 3、多个树称为森林； 4、孤立顶点叫做平凡树 。 1 2 3 4 5 6 7 8 9 10 15 12 13 11 14 平凡树 8.2.1 树的概念和基本性质 [定理] T=(V, E) 是结点数 n=|V| ?1 的树，则下述命题等价： （1） T是无回路的连通图； （2）T是连通的，且有n?1条边； （3）T有n?1条边，且T中无回路； （4）T的任意两点间有且只有唯一的通路； （5）T中无回路，但若在T的任一对不相邻的顶点之间增加一条边，则构成T中的唯一回路。 8.2.2 几类常用树 [树的高度] 设有根树 T=(V, A)，v0为树根。u ? V的深度是从v0 开始到达u的有向路的长度，T的高度是从v0到T的叶子的最长路的长度。 根结点深度为0，称为第0层； 深度同为i 的结点构成树的第i 层； 具有最大深度的结点的深度称为树的深度（高度）。 8.2.2 几类常用树 Tree Node Level and Path Length 8.2.2 几类常用树 有序树 [定义] 对有向树 T=(V, A)，若 u ,v?V且 u,v ? A，则称 u为v的父亲，v为u的儿子。若从u到v存在有向道路，则称u是v的祖先，v是u的后代（子孙） [有序树] 将各树的每个结点的所有儿子按次序排列，称这样的根树为有序树。 有序树的每个结点的出度小于或等于m时，称为m叉有序树。 有序树的每个结点的出度只为 0或 m 时，称为m叉正则有序树。 8.2.2 几类常用树 例 设有4个银币，已知其中3个一定是真的，真假的区别在于银币的重量，现用一天平设法找出假币。 解：用a、b、c、d分别表示银币，a:b表示在天平上作比较。 a:b ＜ ＞ ＝ a:c c重 c轻 ＜ ＞ ＝ a:d d重 全真 d轻 ＜ ＞ ＝ a:c a轻 b重 ＜ ＝ a:c b轻 a重 ＞ ＝ 8.2.2 几类常用树 容易看出，上例中方法并不唯一。 a,b:c,d ＜ ＞ ＝ a:c ＜ ＞ ＝ d:c c轻 a重 ＞ ＝ a:c ＝ ＜ 全真 d:c b重 d轻 ＜ ＞ ＝ a轻 c重 ＜ ＝ a:b ＝ a:b b轻 d重 ＜ 8.2.2 几类常用树 三 、 最优二叉树 [二叉树] 除树叶外，每个结点的最多有两个子结点，分别称为左子结点和右子结点的根树称为二叉树 二叉树的另外一个定义：二叉树或者是空树，或者有一个根结点和两个分别称为左右子树的二叉树构成。 [二叉树的性质] 第i 层的结点数最多为2i； 深度为k的二叉树最多有2k+1-1个结点； 记二叉树出度为2的结点数目为n2，叶子数目为n0，则有： n0=n2+1 多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中该结点的左儿子；以结点的右兄弟为对应二叉树中该结点的右儿子。 8.2.2 几类常用树 [满二叉树] 二叉树的每个结点的出度或者是0或者是2 。满二叉树也称正则二叉树 [完美二叉树] 满二叉树且所有结点在同一层。 对完美二叉树 的结点按从上到下，同层结点从左到右的原则编号，得到结点从1~2k+1-1 的编号序列。得到上述结点编号的二叉树称为编号二叉树。 [完全二叉树]若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。 。