离散数学第16章

1、1,第十六章 树,主要内容 无向树及其性质 生成树 根树及其应用,2,16.1 无向树及其性质,定义16.1 (1) 无向树连通无回路的无向图 (2) 平凡树平凡图 (3) 森林至少由两个连通分支且每个都是树组成 (4) 树叶1度顶点 (5) 分支点度数2的顶点,3,无向树的等价定义,定理16.1 设G=是n阶m条边的无向图，则下面各命题 是等价的： (1) G 是树 (2) G 中任意两个顶点之间存在惟一的路径. (3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1. (5) G 是连通的且 G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，

2、在所得图中得到惟一的一个含新边的圈.,4,(3)(4). 只需证明G连通. 用反证法. 否则G有s（s2）个连通 分支都是小树. 于是有mi=ni1, ， 这与m=n1矛盾.,证明思路,(2)(3). 若G中有回路，则回路上任意两点之间的路径不 惟一. 对n用归纳法证明m=n1. n=1正确. 设nk时对，证n=k+1时也对：取G中边e， Ge有且仅有两个连通分支G1,G2(为什么?) . nik，由归纳 假设得mi=ni1, i=1,2. 于是，m=m1+m2+1=n1+n22+1=n1.,(1)(2). 关键一步是, 若路径不惟一必有回路.,5,(4)(5). 只需证明G 中每条边都是桥.

3、 为此只需证明命题 “G 是 n 阶 m 条边的无向连通图，则 mn1”. 命题的证明: 对n归纳. eE, Ge只有n2条边，由命题可知Ge不连通，故e为桥.,证明思路,(5)(6). 由(5)易知G为树，由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈.,(6)(1). 只需证明G连通，这是显然的.,6,无向树的特点,在结点给定的无向图中， 树是边数最多的无回路图 树是边数最少的连通图 由此可知，在无向图G = (n, m)中， 若mn-1，则G是不连通的 若mn-1，则G必含回路,7,由上式解出x 2.,定理16.2 设T是n阶非平凡的无向树，则T

4、中至少有两片树叶.,无向树的性质,证 设 T 有 x 片树叶，由握手定理及定理16.1可知，,8,例题,例1 已知无向树T中有1个3度顶点，2个2度顶点，其余顶点 全是树叶，试求树叶数，并画出满足要求的非同构的无向树.,解 解本题用树的性质m=n1，握手定理. 设有x片树叶，于是 n = 1+2+x = 3+x, 2m = 2(n1) = 2(2+x) = 13+22+x 解出x = 3，故T有3片树叶.,T 的度数列应为 1, 1, 1, 2, 2, 3， 易知3度顶点与1个2度顶点相邻与和2个2度顶点均相邻是非同构的，因而有2棵非同构的无向树T1, T2，如图所示.,9,例2 已知无向树T

5、有5片树叶，2度与3度顶点各1个，其余顶 点的度数均为4，求T的阶数n，并画出满足要求的所有非同 构的无向树.,例题,解 设T的阶数为n, 则边数为n1，4度顶点的个数为n7. 由握手定理得 2m = 2(n1) = 51+21+31+4(n7) 解出n = 8，4度顶点为1个.,10,T的度数列为1, 1, 1, 1, 1, 2, 3, 4，共有3棵非同构的无向树，如图所示.,例题,11,不一定连通，也不一定不含回路，如图所示,定义16.2 设G为无向图 (1) G的树T 是G 的子图并且是树 (2) G的生成树T 是G 的生成子图并且是树 (3) 生成树T的树枝T 中的边 (4) 生成树T

6、的弦不在T 中的边 (5) 生成树T的余树 全体弦组成的集合的导出子图,16.2 生成树,12,推论2 的边数为mn+1.,推论3 为G的生成树T的余树，C为G中任意一个圈，则C与 一定有公共边. 证 否则，C中的边全在T中，这与T为树矛盾.,定理16.3 无向图G具有生成树当且仅当G连通.,生成树的存在条件,推论1 G为n阶m条边的无向连通图，则mn1.,证 必要性显然. 充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）,13,基本回路、基本回路系统、圈秩,定理16.4 设T为G的生成树，e为T的任意一条弦，则Te中 含一个只有一条弦其余边均为T的树枝的圈. 不同的弦对应的 圈也不

7、同. 证 设e=(u,v)，在T中u到v有惟一路径，则e为所求的圈.,定义16.3 设T是n阶m条边的无向连通图G的一棵生成树，设 e1, e2, , emn+1为T 的弦. 设Cr为T 添加弦er 产生的只含弦 er、其余边均为树枝的圈. 称Cr为G的对应树T 的弦er的基本 回路或基本圈，r=1, 2, , mn+1. 并称C1, C2, ,Cmn+1为 G对应T 的基本回路系统，称mn+1为G的圈秩，记作 (G).,求基本回路的算法：设弦e=(u,v)，先求T中u到v的路径uv，再并上弦e，即得对应e的基本回路.,14,基本割集的存在,定理16.5 设T是连通图G的一棵生成树，e为T的树

8、枝，则G 中存在只含树枝e，其余边都是弦的割集，且不同的树枝对 应的割集也不同. 证 由定理16.1可知，e是T的桥，因而Te有两个连通分支T1 和T2，令 Se=e | eE(G)且 e 的两个端点分别属于V(T1)和V(T2)， 由构造显然可知Se为G的割集，eSe且Se中除e外都是弦， 所以Se为所求. 显然不同的树枝对应的割集不同.,15,定义16.4 设T是n阶连通图G的一棵生成树，e1, e2, , en1 为T 的树枝，Si是G的只含树枝ei的割集，则称Si为G的对应 于生成树T由树枝ei生成的基本割集，i=1, 2, , n1. 并称 S1,S2, , Sn1为G 对应T 的基

9、本割集系统，称n1为G的割 集秩，记作(G).,基本割集、基本割集系统、割集秩,求基本割集的算法 设e为生成树T 的树枝，Te为两棵小树T1与T2，令 Se =e | eE(G)且e的两个端点分别属于T1与T2 则Se为e 对应的基本割集.,16,解 弦e, f, g对应的基本回路分别为 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基=Ce, Cf, Cg. (G)=3 树枝a, b, c, d对应的基本割集分别为 Sa=a, f, g, Sb=b, e, f, g, Sc=c, e, f g, Sd=d, g, S基=Sa, Sb, Sc, Sd. (G)=4,

10、例3 下图实线边所示为生成树，求基本回路系统与基本割集系统,实例,17,破圈法与避圈法求生成树,算法1 求连通图G = 的生成树的破圈法： 每次删除回路中的一条边，其删除的边的总数为m-n+1。 算法2 求连通图G = 的生成树的避圈法： 每次选取G中一条与已选取的边不构成回路的边，选取的边的总数为n-1。 由于删除回路上的边和选择不构成任何回路的边有多种选法，所以产生的生成树不是惟一的。,18,例题,分别用破圈法和避圈法求下图的生成树。,1,2,3,4,5,6,分析 用破圈法时，由于n = 6，m = 9，所以m-n+1 = 4，故要删除的边数为4，因此只需4步即可。 用避圈法时，由于n =

11、 6，所以n-1 = 5，故要选取5条边，因此需5步即可。,破圈法,19,避圈法,由于生成树的形式不惟一，故上述两棵生成树都是所求的。 破圈法和避圈法的计算量较大，主要是需要找出回路或验证不存在回路。,1,2,3,4,5,6,20,广度优先搜索算法,求连通图G = 的生成树的广度优先搜索算法： （1）任选sV，将v标记为0，令L = s，V = V-s，k = 0； （2）如果V = ，则转(4)，否则令k = k+1； （3）依次对L中所有标记为k-1的结点v，如果它与V中的结点w相邻接，则将w标记为k，指定v为w的前驱，令L = Lw，V = V-w，转(2)； （4）EG = (v, w

12、)|wL-s，v为w的前驱，结束。,21,例题,利用广度优先搜索算法求下图的生成树。,0(-),1(a),1(a),2(c),2(b),3(e),3(e),3(e),4(d),4(h),b,a,c,d,g,j,i,f,e,h,0(-),1(a),1(a),2(c),2(b),3(e),3(f),3(e),4(h),4(h),b,a,c,d,g,j,i,f,e,h,22,最小生成树,定义16.5 T是G=的生成树 (1) W(T)T各边权之和 (2) 最小生成树G的所有生成树中权最小的,Kruskal算法：设G=，将G中非环边按权从小 到大排序：e1, e2, , em. (1) 取e1在T中

13、(2) 查e2，若e2与e1不构成回路，取e2也在T 中，否则弃e2. (3) 再查e3, 直到得到生成树为止.,23,例4 求图的一棵最小生成树.,最小生成树W(T)=38.,实例,试试破圈法求最小生成树,24,Prim算法,1，在G中任意选取一个结点v1，置VT = v1, ET = ，k = 1； 2，在V-VT中选取与某个viVT邻接的结点vj，使得边(vi, vj)的权最小，置VT = VTvj, ET = ET(vi, vj)，k = k+1； 3，重复步骤2，直到k = |V|。 说明：步骤2中，若满足条件的最小权边不止一条，则可从中任选一条，这样就会产生不同的最小生成树。 要点

14、：从任意结点开始，每次增加一条最小权边构成一棵新树。,25,例题,用Prim算法求图中赋权图的最小生成树。,解 n = 7，按算法要执行n-1 = 6次，,w(T) = 25。,Prim算法每一步得到的图一定是树，故不需要验证是否有回路（因为，每一步总是从余下的顶点集合中选择下一个顶点及关联边），因此它的计算工作量较Kruskal算法要小。,26,无向树的要点,树是不含回路的连通图。注意把握树的性质，特别是树中叶结点的数目及边数与结点数的关系：m = n-1； 生成树是无向连通图的生成子图。注意把握所有连通图都有生成树，知道生成树的树枝与弦及其数目，会使用避圈法、破圈法求生成树； 最小生成树是

15、赋权连通图的权值之和最小的生成树。会使用Kruskal算法和Prim算法求最小生成树。,27,16.3 根树及其应用,定义16.6 T是有向树（基图为无向树） (1) T 为根树T 中一个顶点入度为0，其余的入度均为1. (2) 树根入度为0的顶点 (3) 树叶入度为1，出度为0的顶点 (4) 内点入度为1，出度不为0的顶点 (5) 分支点树根与内点的总称 (6) 顶点v的层数从树根到v的通路长度 (7) 树高T 中层数最大顶点的层数 (8) 平凡根树平凡图,28,根树实例,根树的画法树根放上方，省去所有有向边上的箭头,29,家族树与根子树,定义16.7 T 为非平凡根树 (1) 祖先与后代

16、(2) 父亲与儿子 (3) 兄弟 定义16.8 设v为根树T中任意一顶点，称v及其后代的导出子 图为以v为根的根子树.,30,根树的分类,(1) T 为有序根树同层上顶点标定次序的根树 (2) 分类 r 叉树每个分支点至多有r 个儿子 r 叉有序树 r 叉正则树每个分支点恰有r 个儿子 r 叉正则有序树 r 叉完全正则树树叶层数相同的r叉正则树 r 叉完全正则有序树,31,例题,判断下图所示的几棵根树分别是什么树？,2叉正则树,3叉树,3叉正则树,3叉有序正则树,练习：画一棵树高为3 的二叉完全正则树。,32,r叉正则树中分支点与叶结点数目之间的关系,定理 在r叉正则树中，若叶数为t，分支点数

17、为i，则下式成立： (r-1)i = t-1 证明 由假设知，该树有i+t个结点。该树的边数为i+t-1。由握手定理知，所有结点的出度之和等于边数。而根据r叉正则树的定义知，所有分支点的出度为ri。因此有 ri = i+t-1，即 (r-1)i = t-1 推论 二叉正则树中，分支点的个数等于树叶个数减1.,例5 假设有一台计算机，它有一条加法指令，可计算3个数之和。如果要求9个数 之和，问至少要执行几次加法指令。,解：用3个结点表示3个数，把9个数看成树叶， 将表示3数之和的结点作为它们的父结点。本问题可理解为求一个正则三叉树的内点个数问题。由 (3-1)i=9-1，得i=4；要执行4次加法

18、指令。,34,定义16.9 设2叉树T 有t片树叶v1, v2, , vt，权分别为w1, w2, , wt，称 为T 的权，其中l(vi)是vi 的层数. 在所有的有t片树叶带权w1, w2, , wt 的2叉树中，权最小的2叉树称为最优二叉树.,最优二叉树,求最优树的算法 Huffman算法 给定实数w1, w2, , wt，且w1w2wt. (1) 连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2. (2) 在w1+w2, w3, , wt 中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权. (3) 重复(2)，直到形成 t1个分支点，t片树叶为

19、止.,35,例 6 求带权为1, 1, 2, 3, 4, 5的最优树. 利用Huffman算法，最优树的生成过程如下：,W(T)=38,36,二叉树的应用之通讯编码,二进制比特(bit)流的传输: 等长码： 例如: 0,1,2,7, 编码为：000,001,010,111 则：000111010101译为0725 不等长编码： 若0,1,2,7出现频率不一样,则出现频率高的用短码字 例如： 频率递减: 0,1,2,3,4,5,6,7 编码：0,1,00,01,10,11,000,001. 若收到000111, 不能唯一解码: 651, 235, 075,等. 原因: 码字互为前缀, 如00是0

20、01的前缀,37,前缀码,定义16.10 设1, 2, , n-1, n是长度为 n 的符号串 (1) 前缀1, 12, , 12n1 (2) 前缀码1, 2, , m中任何两个元素互不为前缀 (3) 二元前缀码i (i=1, 2, , m) 中只出现两个符号，如0与1.,如何产生二元前缀码？ 定理16.6 一棵2叉树树叶产生一个二元前缀码. 推论 一棵2叉正则树产生惟一的前缀码（按左子树标0，右子树标1）,38,下图所示二叉树产生的前缀码为 00, 10, 11, 011, 0100, 0101 ,39,最佳前缀码,最佳前缀码: 给定信号出现频率, 平均码字长度最短的前缀码 平均码字长度:

21、码字长度乘以频率,求和 例: 0,1,2,3, 40%, 30%, 20%,10% 编码1: 00,010,011,1 240%+330%+320%+110%=2.4 编码2: 1,00,010,011 140%+230%+320%+310%=1.9 编码3：00,01,10,11 等长码，平均码字长度为 2 如何得到最佳前缀码呢？,40,用Huffman算法产生最佳前缀码,例7 在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5% 求传输它们的最佳前缀码，并求传输10n（n2）个按上述比 例出现的八进制数字需要多少个

22、二进制数字？,41,解 用100个八进制数字中各数字出现的个数，即以100乘各频率为权，并将各权由小到大排列，得w1=5, w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25. 用此权产生的最优树如图所示.,求最佳前缀码,01-0 11-1 001-2 100-3 101-4 0001-5 00000-6 00001-7,W(T)=285， 传10n(n2)个 用二进制数字需 2.8510n个，,42,二叉树的遍历,行遍或周游根树T列出根树的所有顶点，每个顶点恰好出现一次. 对2叉树的遍历，根据是先访问跟顶点，还是先访问子树有3种不同的遍历方式： 中序

23、遍历 遍历左子树、访问根顶点、遍历右子树 先序遍历 访问根顶点、遍历左子树、遍历右子树 后序遍历 遍历左子树、遍历右子树、访问根顶点 显然，这些遍历算法都是递归算法,中序遍历算法描述,43,function inorder (root) begin if root is not null then begin p=left child of root inorder (p) print label of root p=right child of root inorder (p) end end,二叉树的遍历举例,44,如右图所示，按照中序、先序和后序遍历算法，顶点的访问顺序分别为： b a

24、(f d g) c e a b (c (d f g) e) b (f g d) e c) a,课堂练习,45,二叉树顶点的先序顺序为 ABCDEFGHIJKLM， 中序顺序为 CEDFBAHJIKGML， 画出这颗二叉树。,46,表达式树,存放规则 最高层次运算放在树根 后依次将运算符放在根子树的根上 数放在树叶上 规定：被除数、被减数放在左子树树叶上,中缀符号法： (b+(c+d)a)(ef)(g+h)(ij) 在中缀算式中，运算符具有优先顺序（先乘除，后加减）；否则，需要加括弧改变优先顺序。,47,波兰符号法与逆波兰符号法,波兰符号法 也称前缀符号法，按先序遍历访问存放算式的2叉树，规定每

25、个运算符号与其后面紧邻两个数进行运算。 对上图的 访问结果为 b + c d a e f + g h i j 逆波兰符号法 也称后缀符号法，按后序遍历访问，规定每个运算符与前面紧邻两数运算. 对上图的访问结果为 b c d + + a e f g h + i j 波兰符号法和逆波兰符号法，都可以省略括号。 后缀符号法在计算机科学中具有重要应用，目前许多编译器首先把数学表达式置换成后缀符号算式，然后，再将后缀表达式变成机器代码。,如何求后缀表达式的值,48,比如，24 4 3 * - 16 4 / + 24 4 3 * - 16 4 / + 4*3=12 24 12 - 16 4 / + 24-

26、12=12 12 16 4 / + 16/4=4 12 4 + 12+4=16 16,课堂练习,49,1，画出中缀表达式 x+(y-z)*w所对应的表达式树。 2，求后缀表达式 24 4 + 3 * 7 / 26 4 - + 的值。 3，将中缀表达式 (a+b)*(c+d)-e变成后缀表达式。,50,本章主要知识点,树的概念： 树、森林、根树、根、叶、分支点、生成树、最小生成树等。 树的基本性质：m = n-1等。 与根树相关的概念：有向树、根树、根、叶、内点、分支点、层数、高、有序树、祖先与后代、父亲与儿子、r叉树、 r叉完全树、 r叉有序树、 r叉有序完全树、子树、根树的遍历、最优树。 树

27、的算法： 破圈法、避圈法、Kruskal算法、Prim算法、哈夫曼算法、二叉树的先(中、后)根次序遍历算法 树的应用,51,习题类型,基本概念题：树的基本概念、分类； 判断题：判定是否是树、生成树等； 计算题：叶和分支点的数目、利用现有算法计算相应的问题等； 证明题：主要观测点在于树性质的证明,52,解题分析和方法,利用树的性质：m=n-1，将其与握手定理配合使用，在有关无向树、有向树的很多证明和计算中都很重要； 构造性证明方法的使用，只有找到了就一定存在； 利用各种问题的现有算法，可机械地计算求解； 反证法非常有用，特别是在证明惟一性和不存在的时候。,53,作业16,习题十六：3，24（1），25，37，42,54,（2）,（3）,从而解出,练习1,1. 无向树 T 有ni个i 度顶点，i=2, 3,