离散数学+图论树.ppt

第七章 图论 第八章 图论-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 树的概念和基本性质 在图论中： 8.2.1 树的概念和基本性质 3、多个树称为森林； 4、孤立顶点叫做平凡树 。 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 几类常用树 根树 8.2.2 几类常用树 根树通常画成倒长的； 一个 结点的子结点画在它的 下一层，边的方向省略； “同辈兄弟”画在同一层。 8.2.2 几类常用树 [树的高度] 设有根树 T=(V, A)，v0为树根。u ? V的深度是从v0 开始到达u的有向路的长度，T的高度是从v0到T的叶子的最长路的长度。 根结点深度为0，称为第0层； 深度同为i 的结点构成树的第i 层； 具有最大深度的结点的深度称为树的深度（高度）。 8.2.2 几类常用树 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表示在天平上作比较。 8.2.2 几类常用树 容易看出，上例中方法并不唯一。 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 层从右向左连续缺若干结点，这就是完全二叉树。 。 8.2.2 几类常用树 高度为k的完全二叉树，其k-1层以上结点构成一棵高度为k-1 的完美二叉树。 完全二叉树的叶结点或者在同一层或者 在相邻的两层。 8.2.2 几类常用树 三 、 最优二叉树 [定义]设T是有t片叶子的二叉树，其中t片叶子分别带有非负实权 ，则称T为加权二叉树。称W(T)＝ 为二叉树T的权，其中hi为带权wi的树叶vi的层数。在所有的带权 的二叉树中，带权最小的二叉树称为最优二叉树(哈夫曼树 ) 8.2.2 几类常用树 【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为： 　　(a) W(T)=7*2+5*2+2*2+4*2=36 　　(b) W(T)= =7*3+5*3+2*1+4*2=46