《离散数学(第十六章)》由会员分享，可在线阅读，更多相关《离散数学(第十六章)（44页珍藏版）》请在金锄头文库上搜索。
1、1,16.1 无向树及其性质,定义16.1 (1) 无向树连通无回路的无向图 (2) 平凡树平凡图 (3) 森林至少由两个连通分支（每个都是树）组成 (4) 树叶1度顶点 (5) 分支点度数2的顶点,2,树的举例,判断图G1、G2、G3是否为树？,是,不是,有回路,不是,不连通,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,由上式解出x 2.,定理16.2 设T是n阶非平凡的无向树，则T 中至少有两片树叶.,无向树的性质,证 设 T 有 x 片树叶，由握手定理及定理16.1可知，,7,例题,例1 已知无向树T中有1个3度顶点，2个2度顶点，其余顶点 全是树
4、叶，试求树叶数，并画出满足要求的非同构的无向树.,解 解本题用树的性质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，如图所示.,8,例2 已知无向树T有5片树叶，2度与3度顶点各1个，其余顶 点的度数均为4，求T的阶数n，并画出满足要求的所有非同 构的无向树.,例题,解 设T的阶数为n, 则边数为n1，4度顶点的个数为
5、n7. 由握手定理得 2m = 2(n1) = 51+21+31+4(n7) 解出n = 8，4度顶点为1个.,9,T的度数列为1, 1, 1, 1, 1, 2, 3, 4，共有3棵非同构的无向树，如图所示.,例题,10,不一定连通，也不一定不含回路，如图所示,定义16.2 设G为无向图 (1) G的生成树T 是G 的生成子图并且是树 (2) 生成树T的树枝T 中的边 (3) 生成树T的弦不在T 中的边 (4) 生成树T的余树 全体弦组成的集合的导出子图,16.2 生成树,11,生成树举例,求图G的生成树,图T1和T2均为G的生成树。,12,定理16.3 无向图G具有生成树当且仅当G连通.,生
6、成树存在条件,证 必要性显然. 充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）,13,最小生成树,定义16.5 T是G=的生成树 (1) W(T)T各边权之和 (2) 最小生成树G的所有生成树中权最小的,求最小生成树的一个算法 避圈法（Kruskal）设G=，将G中非环边按权从小 到大排序：e1, e2, , em. (1) 取e1在T中 (2) 查e2，若e2与e1不构成回路，取e2也在T 中，否则弃e2. (3) 再查e3, 直到得到生成树为止.,14,避圈法求最小生成树举例,用避圈法求图G的最小生成树,15,解答,(1)选择权值为1的边(c,d);,1,(2)选择权值为2的边
7、(b,f);,2,(3)选择权值为3的边(b,c);,3,(4)选择权值为4的边(a,b);,4,(5)权值为5的边(a,f),形成回路,避开,权值为6的边(a,c),形成回路,避开;,权值为7的边(d,f),形成回路,避开;,(6)选择权值为8的边(f,e);,8,加权长度1234818,最小生成树,16,求最小生成树举例,求图G的最小生成树,(1)选择权值为3的边(v1,v5);,3,(2)选择权值为4的边(v1,v4);,4,(3)选择权值为4的边(v4,v5);,形成回路,避开,(4)选择权值为5的边(v2,v5);,5,(5)选择权值为6的边(v3,v5);,6,加权长度为3+4+5
8、+618,最小生成树,17,解答(2),(1)选择权值为3的边(v1,v5);,3,(2)选择权值为4的边(v4,v5);,4,(3)选择权值为4的边(v1,v4);,形成回路,避开,(4)选择权值为5的边(v2,v5);,5,(5)选择权值为6的边(v3,v5);,6,加权长度为3+4+5+618,最小生成树不唯一，最小生成树的加权长度相同,18,16.3 根树及其应用,定义16.6 T是有向树（基图为无向树） (1) T 为根树T 中一个顶点入度为0，其余的入度均为1. (2) 树根入度为0的顶点 (3) 树叶入度为1，出度为0的顶点 (4) 内点入度为1，出度不为0的顶点 (5) 分支点
9、树根与内点的总称 (6) 顶点v的层数从树根到v的通路长度 (7) 树高T 中层数最大顶点的层数 (8) 平凡根树平凡图,19,根树实例,根树的画法树根放上方，省去所有有向边上的箭头,根树举例,树叶:,树根,树的高度：3,v4,v5,v6,v7,v8,v10,v11,v12,分枝结点：,v0,v1,v2,v3,v9,根结点是分枝结点,21,家族树与根子树,定义16.7 T 为非平凡根树 (1) 祖先与后代 (2) 父亲与儿子 (3) 兄弟 定义16.8 设v为根树T中任意一顶点，称v及其后代的导出子 图为以v为根的根子树.,有序树举例,不考虑同一层上结点的次序，是同一棵树 两棵不同的有序树。,
10、大,小,(1) T 为有序根树同层上顶点标定次序的根树,23,根树的分类,(2) 分类 r 叉树每个分支点至多有r 个儿子 r 叉有序树r 树是有序的 r 叉正则树每个分支点恰有r 个儿子 r 叉正则有序树 r 叉完全正则树树叶层数相同的r叉正则树 r 叉完全正则有序树,24,定义16.9 设2叉树T 有t片树叶v1, v2, , vt，权分别为w1, w2, , wt，称 为T 的权，其中l(vi)是vi 的层数. 在所有有t片树叶，带权w1, w2, , wt 的2叉树中，权最小的2叉树称为最优2叉树.,最优二叉树,求最优树的算法 Huffman算法 给定实数w1, w2, , wt，且w
11、1w2wt. (1) 连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2. (2) 在w1+w2, w3, , wt 中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权. (3) 重复(2)，直到形成 t1个分支点，t片树叶为止.,25,例 5 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由图9给出，W(T)=38,求最优二叉树举例,设有一组权2，3，5，7，11，13，17，19，20，求相应的最优树。,解答,2 3 5 7 11 13 17 19 20,5,5 7 11 13 17 19 20,解答（续）,5 5 7 11 13 17
12、19 20,10,7 11 13 17 19 20,解答（续）,17 11 13 17 19 20,24,17 17 19 20,解答（续）,17 24 17 19 20,34,24 19 20,解答（续）,24 34 19 20,39,24 34,解答（续）,24 34 39,58,39,解答（续）,58 39,97,W(T)=6(2+3)+5*5 +4*7+3(11+13+17) +2(19+20) =264,34,最佳前缀码,定义16.10 设1, 2, , n-1, n是长度为 n 的符号串 (1) 前缀1, 12, , 12n1 (2) 前缀码1, 2, , m中任何两个元素互不为前
13、缀 (3) 二元前缀码i (i=1, 2, , m) 中只出现两个符号，如0与1.,如何产生二元前缀码？ 定理16.6 一棵2叉树产生一个二元前缀码. 推论 一棵正则2叉树产生惟一的前缀码（按左子树标0，右子树标1）,35,图所示二叉树产生的前缀码为 00, 10, 11, 011, 0100, 0101 ,36,用Huffman算法产生最佳前缀码,例6 在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5% 求传输它们的最佳前缀码，并求传输10n（n2）个按上述比 例出现的八进制数字需要多少个二进制数字？若用等长的 （
14、长为3）的码字传输需要多少个二进制数字？,37,解 用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个， 用等长码需 310n个数字.,38,波兰符号法与逆波兰符号法,行遍或周游根树T对T的每个顶点访问且仅访问一次. 对2叉有序正则树的
15、周游方式： 中序行遍法次序为：左子树、根、右子树 前序行遍法次序为：根、左子树、右子树 后序行遍法次序为：左子树、右子树、根,对图所示根树按中序、前序、 后序行遍法访问结果分别为： b a (f d g) c e， a b (c (d f g) e)， b (f g d) e c) a,39,用2叉有序正则树存放算式,存放规则 最高层次运算放在树根 后依次将运算符放在根子树的根上 数放在树叶上 规定：被除数、被减数放在左子树树叶上,算式 (b+(c+d)a)(ef)(g+h)(ij) 存放在图所示2叉树上.,40,波兰符号法,波兰符号法 按前序行遍法访问存放算式的2叉有序正则树，其结果不加 括号，规定每个运算符号与其后面紧邻两个数进行运算，运 算结果正确. 称此算法为波兰符号法或前缀符号法. 对上图的 访问结果为 b + c d a e f + g h i j 逆波兰符号法 按后序行遍法访问，规定每个运算符与前面紧邻两数运算， 称为逆波兰符号法或后缀符号法. 对上图的访问结果为 b c d + + a e f
