第16章树下载_PPT模板_38

is_463355

暂无简介

第16章树null 离散数学 Discrete Mathematics第十六章树第十六章树主要内容无向树及其性质生成树根树及其应用 16.1 无向树及其性质16.1 无向树及其性质定义16.1 (1) 无向树——连通无回路的无向图 (2) 平凡树——平凡图 (3) 森林——至少由两个连通分支（每个都是树）组成 (4) 树叶——1度顶点 (5) 分支点——度数2的顶点无向树的等价定义无向树的等价定义定理16.1 ...

null 离散数学 Discrete Mathematics第十六章树第十六章树主要内容无向树及其性质生成树根树及其应用 16.1 无向树及其性质16.1 无向树及其性质定义16.1 (1) 无向树——连通无回路的无向图 (2) 平凡树——平凡图 (3) 森林——至少由两个连通分支（每个都是树）组成 (4) 树叶——1度顶点 (5) 分支点——度数2的顶点无向树的等价定义无向树的等价定义定理16.1 设G=是n阶m条边的无向图，则下面各命题是等价的： (1) G 是树 (2) G 中任意两个顶点之间存在惟一的路径. (3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1. (5) G 是连通的且 G 中任何边均为桥. (6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈. 证明思路证明思路(2)(3). 若G中有回路，则回路上任意两点之间的路径不惟一. 对n用归纳法证明m=n1. n=1正确. 设nk时对，证n=k+1时也对：取G中边e， Ge有且仅有两个连通分支G1,G2(为什么?) . nik，由归纳假设得mi=ni1, i=1,2. 于是，m=m1+m2+1=n1+n22+1=n1.(3)(4). 只需证明G连通. 用反证法. 否则G有s（s2）个连通分支都是小树. 于是有mi=ni1, ，这与m=n1矛盾. (1)(2). 关键一步是, 若路径不惟一必有回路. 证明思路证明思路(4)(5). 只需证明G 中每条边都是桥. 为此只需证明命题 “G 是 n 阶 m 条边的无向连通图，则 mn1”. 命题的证明: 对n归纳. eE, Ge只有n2条边，由命题可知Ge不连通，故e为桥. (5)(6). 由(5)易知G为树，由(1)(2)知，u,vV（uv）, u到v有惟一路径，加新边(u,v)得惟一的一个圈. (6)(1). 只需证明G连通，这是显然的. 无向树的性质由上式解出x  2. 定理16.2 设T是n阶非平凡的无向树，则T 中至少有两片树叶. 无向树的性质证设 T 有 x 片树叶，由握手定理及定理16.1可知，例题例题例1 已知无向树T中有1个3度顶点，2个2度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树. 解解本题用树的性质m=n1，握手定理. 设有x片树叶，于是 n = 1+2+x = 3+x, 2m = 2(n1) = 2(2+x) = 13+22+x 解出x = 3，故T有3片树叶.T 的度数列应为 1, 1, 1, 2, 2, 3，易知3度顶点与1个2度顶点相邻与和2个2度顶点均相邻是非同构的，因而有2棵非同构的无向树T1, T2，如图所示. 例题例题例2 已知无向树T有5片树叶，2度与3度顶点各1个，其余顶点的度数均为4，求T的阶数n，并画出满足要求的所有非同构的无向树. 解设T的阶数为n, 则边数为n1，4度顶点的个数为n7. 由握手定理得 2m = 2(n1) = 51+21+31+4(n7) 解出n = 8，4度顶点为1个. 例题T的度数列为1, 1, 1, 1, 1, 2, 3, 4，共有3棵非同构的无向树，如图所示.例题16.2 生成树16.2 生成树null定理16.3 无向图G具有生成树当且仅当G连通.生成树存在条件推论1 G为n阶m条边的无向连通图，则mn1. 证必要性显然. 充分性用破圈法（注意：在圈上删除任何一条边，不破坏连通性）基本回路系统基本回路系统定理16.4 设T为G的生成树，e为T的任意一条弦，则Te中含一个只有一条弦其余边均为T的树枝的圈. 不同的弦对应的圈也不同. 证设e=(u,v)，在T中u到v有惟一路径，则e为所求的圈. 定义16.3 设T是n阶m条边的无向连通图G的一棵生成树，设 e1, e2, …, emn+1为T 的弦. 设Cr为T 添加弦er 产生的只含弦 er、其余边均为树枝的圈. 称Cr为G的对应树T 的弦er的基本回路或基本圈，r=1, 2, …, mn+1. 并称{C1, C2, …,Cmn+1}为 G对应T 的基本回路系统，称mn+1为G的圈秩，记作 (G). 求基本回路的算法：设弦e=(u,v)，先求T中u到v的路径uv，再并上弦e，即得对应e的基本回路. 基本割集的存在基本割集的存在定理16.5 设T是连通图G的一棵生成树，e为T的树枝，则G 中存在只含树枝e，其余边都是弦的割集，且不同的树枝对应的割集也不同. 证由定理16.1可知，e是T的桥，因而Te有两个连通分支T1 和T2，令 Se={e | eE(G)且 e 的两个端点分别属于V(T1)和V(T2)}，由构造显然可知Se为G的割集，eSe且Se中除e外都是弦，所以Se为所求. 显然不同的树枝对应的割集不同. 基本割集与基本割集系统基本割集与基本割集系统定义16.4 设T是n阶连通图G的一棵生成树，e1, e2, …, en1 为T 的树枝，Si是G的只含树枝ei的割集，则称Si为G的对应于生成树T由树枝ei生成的基本割集，i=1, 2, …, n1. 并称 {S1,S2, …, Sn1}为G 对应T 的基本割集系统，称n1为G的割集秩，记作(G). 求基本割集的算法设e为生成树T 的树枝，Te为两棵小树T1与T2，令 Se ={e | eE(G)且e的两个端点分别属于T1与T2} 则Se为e 对应的基本割集. 实例解弦e, f, g对应的基本回路分别为 Ce=e b c, Cf=f a b c, Cg=g a b c d, C基={Ce, Cf, Cg}. 树枝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}. 例3 图5实线边所示为生成树，求基本回路系统与基本割集系统实例最小生成树最小生成树定义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,…, 直到得到生成树为止. 实例例4 求图的一棵最小生成树.所求最小生成树如图所示，W(T)=38.实例16.3 根树及其应用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) 平凡根树——平凡图根树实例根树实例根树的画法——树根放上方，省去所有有向边上的箭头家族树与根子树家族树与根子树定义16.7 T 为非平凡根树 (1) 祖先与后代 (2) 父亲与儿子 (3) 兄弟定义16.8 设v为根树T中任意一顶点，称v及其后代的导出子图为以v为根的根子树.根树的分类根树的分类(1) T 为有序根树——同层上顶点标定次序的根树 (2) 分类 ① r 叉树——每个分支点至多有r 个儿子 ② r 叉有序树——r 树是有序的 ③ r 叉正则树——每个分支点恰有r 个儿子 ④ r 叉正则有序树 ⑤ r 叉完全正则树——树叶层数相同的r叉正则树 ⑥ r 叉完全正则有序树最优二叉树最优二叉树求最优树的算法—— Huffman算法给定实数w1, w2, …, wt，且w1w2…wt. (1) 连接权为w1, w2的两片树叶，得一个分支点，其权为w1+w2. (2) 在w1+w2, w3, …, wt 中选出两个最小的权，连接它们对应的顶点(不一定是树叶)，得新分支点及所带的权. (3) 重复(2)，直到形成 t1个分支点，t片树叶为止. null例 5 求带权为1, 1, 2, 3, 4, 5的最优树. 解题过程由图9给出，W(T)=38最佳前缀码最佳前缀码定义16.10 设1, 2, …, n-1, n是长度为 n 的符号串 (1) 前缀——1, 12, …, 12…n1 (2) 前缀码——{1, 2, …, m}中任何两个元素互不为前缀 (3) 二元前缀码——i (i=1, 2, …, m) 中只出现两个符号，如0与1. 如何产生二元前缀码？定理16.6 一棵2叉树产生一个二元前缀码. 推论一棵正则2叉树产生惟一的前缀码（按左子树标0，右子树标1）null图所示二叉树产生的前缀码为 { 00, 10, 11, 011, 0100, 0101 }用Huffman算法产生最佳前缀码用Huffman算法产生最佳前缀码例6 在通信中，八进制数字出现的频率如下： 0：25% 1：20% 2：15% 3：10% 4：10% 5：10% 6：5% 7：5% 求传输它们的最佳前缀码，并求传输10n（n2）个按上述比例出现的八进制数字需要多少个二进制数字？若用等长的（长为3）的码字传输需要多少个二进制数字？求最佳前缀码解用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-----7W(T)=285，传10n(n2)个用二进制数字需 2.8510n个，用等长码需 310n个数字. 波兰符号法与逆波兰符号法波兰符号法与逆波兰符号法行遍或周游根树T——对T的每个顶点访问且仅访问一次. 对2叉有序正则树的周游方式： ① 中序行遍法——次序为：左子树、根、右子树 ② 前序行遍法——次序为：根、左子树、右子树 ③ 后序行遍法——次序为：左子树、右子树、根对图所示根树按中序、前序、后序行遍法访问结果分别为： b a (f d g) c e， a b (c (d f g) e)， b ((f g d) e c) a用2叉有序正则树存放算式用2叉有序正则树存放算式存放规则最高层次运算放在树根后依次将运算符放在根子树的根上数放在树叶上规定：被除数、被减数放在左子树树叶上算式 ((b+(c+d))a)((ef)(g+h)(ij)) 存放在图所示2叉树上. 波兰符号法波兰符号法波兰符号法按前序行遍法访问存放算式的2叉有序正则树，其结果不加括号，规定每个运算符号与其后面紧邻两个数进行运算，运算结果正确. 称此算法为波兰符号法或前缀符号法. 对上图的访问结果为    b + c d a   e f  + g h  i j 逆波兰符号法按后序行遍法访问，规定每个运算符与前面紧邻两数运算，称为逆波兰符号法或后缀符号法. 对上图的访问结果为 b c d + + a  e f  g h + i j     第十六章习题课第十六章习题课主要内容无向树及其性质生成树、最小生成树、基本回路系统、基本割集系统根树及其分类、最优树、最佳前缀码、波兰符号法、逆波兰符号法基本要求深刻理解无向树的定义及性质熟练地求解无向树准确地求出给定带权连通图的最小生成树深刻理解基本回路、基本割集的概念，并会计算理解根树及其分类等概念会画n阶（n较小）非同构的无向树及根树（1n6）熟练掌握求最优树及最佳前缀码的方法掌握波兰符号法与逆波兰符号法null（2）（3）从而解出练习11. 无向树 T 有ni个i 度顶点，i=2, 3, …,k，其余顶点全是树叶，求T 的树叶数. 解用树的性质：边数 m=n1（n为阶数），及握手定理. (1) null2．设n阶非平凡的无向树T中，(T)  k，k  1. 证明T至少有k片树叶. 证反证法. 否则，T至多有s片树叶，s < k，下面利用握手定理及树的性质m = n1推出矛盾. 由于(T)  k，故存在v0，d(v0)  k. 于是，由此解出s  k，这与s < k矛盾. 证本题的方法有多种，请用分支点都是割点来证明. 练习2null得 n25n+4  0，解出 1  n  4, 矛盾于n  5. 练习3null练习3null4．画出基图为图所示无向树的所有非同构的根树练习4以a, b, c 或d为根的根树同构，选a为根，则根树如图(1); 以 e 与 g 为根的根树同构，取 g为根，则根树如图(2)；以 f 为根，如图(3) 所示. null5．设T 是正则2叉树，T 有t 片树叶，证明T的阶数 n=2t1. 方法一. 利用正则2叉树的定义及树的性质直接证明. (1) n = t+i (i为分支点数) (2) n = m+1 （m为T的边数） (3) m = 2i （正则2叉树定义）由(2)、(3)得，代入（1）得n = 2t1. 练习5方法二. 利用握手定理及树的性质证. T的树根为2度顶点，所有内点为3度顶点，当然叶为1度顶点，有 (1) 2m = 2+3(i1)+t (2) n = m+1 = i+t 由(1) 和(2) 可解出n = 2t1.

本文档为【第16章树】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

第16章树

热门搜索

历史搜索

第16章 树

热门搜索

历史搜索

第16章树