《离散数学图论树》PPT课件.pptx

第16章树 第十六章树一 无向树1 定义 连通无回路 初级回路或简单回路 的无向图称为无向树 或简称树常用T表示树 平凡图称为平凡树 若无向图G至少有两个连通分支 则称G为森林 在无向树中 悬挂顶点称为树叶 度数大于或等于2的顶点称为分支结点 2 树的等价定义设G 是n阶m条边的无向图 则下面各命题是等价的 1 G是连通无回路 树 可通过循环证明 2 G中任意两个顶点之间存在惟一的路径 连通则存在路径 若不唯一 不同路径则构成回路 3 G中无回路且m n 1 有长大于等于2的回路都与唯一路径矛盾 对结点进行归纳 n 1平凡图m 0 n 1 设n k成立 n k 1时两个结点有唯一的路 去掉则为两个连通分支 各自满足假设 m m1 m2 1 n1 1 n2 1 1 n1 n2 1 n 1 4 G是连通的且m n 1 若不连通 对各个 s 2 连通分支是树且有mi ni 1m n ss 2矛盾 5 G中没有回路 但在任何两个不同的顶点之间加一条新边 在所得图中得到惟一的一个含新边的初级回路 6 G是连通的 但删去任何一条边后 所得图不连通 G连通 若存在二个结点无通路 则在二个结点添加边后不会出现回路3 树的性质对于给定的无向图 树是边数最小的连通图 mn 1则有回路 结点的度 d vi 2m 2 n 1 定理 设T是n阶非平凡的无向树 则T中至少有片树叶设 有x片树叶 其余结点度数至少为2x 2 n x 2 n 1 例 无向树T中度为4 3 2的结点各一个 其余为树叶 树叶 4 3 2 k 2 3 k 1 4 阶数n比较小的所有非同构的无向树 例1 画出6阶所有非同构的无向树 m n 1 5从树的节点之和来分析 结点之和为10分配给6个结点111115111124111133111223112222例2 7阶无向树中有3片树叶和1个3度顶点 其余3个顶点的度数均无1和3 试画出满足要求的所有非同构的无向树 解答 从树的节点之和来分析 7阶无向树的边数m 于是 d vi 12 3 3 d v5 d v6 d v7 1112223加入2 2 2如何组成结点的度数序列使之不同构主要分析 度为3的结点v与其三个邻接点的关系邻接关系不同就能得到不同构的树三个邻接点度数 112122222 16 2生成树 一些连通图不是树 但它的子图是树 重要的是生成树 1 定义 设T是无向图G的子图并且为树 则称T为G的树 若T是G的树且为生成子图 则称T是G的生成树 设T是G的生成树 e E G 若e E T 则称e为T的树枝 否则称e为T的弦 并称导出子图G E G E T 为T的余树 记作 注 不一定连通 也不一定不含回路 无规律 2 生成树的性质1 定理 无向图G具有生成树当且仅当G是连通图 破圈法 不断去掉回路 2 设G为n阶m条边的无向连通图 则m E G E T n 1 3 设G是n阶m条边的无向连通图 T为G的生成树 则T的余树 中含m n 1条边 即T有m n 1条弦 4 任何无向连通图G 都存在生成树无向连通图G的生成树是不唯一的 实边图为该图的一棵生成树T 余树 为虚边所示 它不连通 同时也含回路 3 生成树的应用要建6个工厂 修建连接的通路 见图 为使5处都有路相通 至少要建几条路 如何铺设 由于n 6所以建5条路即可4 无向图G的生成树的确定 二种方法 1 破圈法 每次去掉回路中的一条边 去掉总数为m n 1条弦2 避圈法 由一个结点开始选一条边 逐渐添加与边关联的结点 只要不构成回路即可 直到所有结点被添加 挑选n 1条边 3 带权图的最小生成树 1 定义5设无向连通带权图G T是G的一棵生成树 T的各边权之和称为T的权 记作W T G的所有生成树中权最小的生成树称为G的最小生成树 2 最小生成树的求法 这里介绍避圈法Kruskal算法 设n阶无向连通带权圈G 有m条边 不妨设G中没有环 否则 可以将所有的环先删去 将m条边按权从小到大顺序排列 设为e1 e2 em 取e1在T中 然后依次检查e2 e3 em 若ej j 2 与已在T中的边不能构成回路 则取ej在T中 否则弃去ej 算法停止时得到的T为G的最小生成树 避圈法Kruskal算法 n 1次 1 1 2 3 4 破圈法 1 作业 P319习题十六1 2 3 4 5 13 16 3根树及其应用有向树 设D是有向图 若D的基图是无向树 则称D为有向树 有向树中 根树最重要 故只讨论根树 一 根树1 定义 设T是n n 2 阶有向树 若T中有一个顶点的入度为0 其余顶点的入度均为1 则称T为根树 入度为0的顶点称为树根 相当于文件系统的盘符 入度为1出度为0的顶点称为树叶 具体文件 入度为1出度不为0的顶点称为内点 文件夹 内点和树根统称为分支结点 是否为根树 a b c no no yes 从树根到T的任意顶点v的通路 路径 长度称为v的层数 v5的层数为层 层数最大顶点的层数称为树高 将平凡树也称为根树 右图中树高为 在根树中 由于各有向边的方向是一致的 所以画根树时可以省去各边上的所有箭头 并将树根画在最上方 2 根树中顶点的关系定义 设T为一棵非平凡的根树 vi vj V T 若vi可达vj 则称vi为vj的祖先 vj为vi的后代 若vi邻接到vj 即 E T 称vi为vj的父亲 而vj为vi的儿子若vj vk的父亲相同 则称vj与vk是兄弟 v1为v5的祖先 v5为v1的后代 v2为v5的父亲 而v5为v2的儿子 v4与v5是兄弟 3 有序树设T为根树 若将T中层数相同的顶点都标定次序 则称T为有序树根据根树T中每个分支点儿子数以及是否有序 可以将根树分成下列各类 1 若T的每个分支点至多有r个儿子 则称T为r叉树 又若r叉树是有序的 则称它为r叉有序树 2 若T的每个分支点都恰好有r个儿子 则称T为r叉正则树 又若T是有序的 则称它为r叉正则有序树 3 若T是r叉正则树 且每个树叶的层数均为树高 则称T为r叉完全正则树 又若T是有序的 则称它为r叉完全正则有序树 二叉有序树 二叉完全正则有序树 四叉树 a b c 4 r叉树的子树定义 设T为一棵根树 v V T 称v及其后代的导出子图Tv为T的以v为根的根子树 如 二叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树 左子树 右子树 二 根树的应用1 最优二叉树定义 设二叉树T有t片树叶v1 v2 vt 权分别为w1 w2 wt 称W T wi vi 为T的权 其中 vi 是vi的层数 也可以是从根到该叶子的通路长度 在所有有t片树叶 带权w1 w2 wt的二叉树中 总权值W T 最小的二叉树称为最优二叉树三棵带权二叉树W T1 2 2 2 3 3 5 3 3 2 38W T2 4 3 5 3 3 2 2 2 47W T3 3 3 3 5 2 2 2 2 36 2 Huffman算法 在给定权值下 如何构造最优二叉树 给定实数 权值 w1 w2 wt 按从小到大排序为w1 w2 wt 1 连接权为w1 w2的两片树叶 得一个分支点 其权为w1 w2 2 在w1 w2 w3 w4 wt中选出两个权最小的 连接它们对应的顶点 不一定是树叶 得新分支点及所带的权 3 重复 2 直到形成t 1个分支点 t片树叶为止 例 求2 2 3 3 5的最优二叉树 例 求2 2 3 3 5的最优二叉树 2 3 3 4 5 1 2 2 3 3 5 3 4 5 6 4 6 9 最优二叉树总的原则是 权值较大的叶子距根较近 权值较小的可以距根较远例 给定一组权值3 5 6 9 11 14 16 18构造相应的最优二叉树 3 前缀编码在通信中 常用二进制编码表示符号 1 等长编码与不等长编码 不等长编码可以使总电文总长度较短2 不等长编码中编码的问题 如何识别 3 前缀编码定义 设a1a2 an 1an为长为n的符号串 称其子串a1 a1a2 a1a2 an 1分别为该符号串的长度为1 2 n 1的前缀 设A b1 b2 bm 为一个符号串集合 若对于任意的bi bj A i j bi与bj互不为前缀 则称A为前缀码 若符号串bi i 1 2 m 中只出现0 1两个符号 则称A为二元前缀码 1 10 101 0101 1010 0100 01001 不是前缀码 1 00 011 0101 01001 01000 为前缀码 1 01 111 1100 0111 不是前缀码 1 10 01 101 0101a b c d e 2 利用二叉树产生二元前缀码规定二叉树的左子树的边为0 右子树的边为1则将从根到叶子结点的通路中边的序列即为叶子的二元前缀编码 a 00b 010c 011d 10e 111 通信中 每个字符出现的频率不同 如何使得传输效率最高 等长的编码一定不是最好的 考虑利用二元前缀码 3 最优二元前缀码给定所需编码的字符的频率 构造字符的二元前缀编码 使其总电文长度为最短 称为最优二元前缀码 先利用哈夫曼算法 生成最优二叉树 再得到最优二元前缀码 例 传输100个八进制的数字 其出现的频率分别为 0 25 1 20 2 15 3 10 4 10 5 10 6 5 7 5 用最优二元前缀码传输需要多少二进制数字 用等长码传输需要多少二进制数字 先得到最优二元前缀码利用哈夫曼算法 生成最优二叉树 以频率为权值 5 5 10 10 10 15 20 256 7 3 4 5 2 1 0 5 5 10 10 10 15 20 256 7 3 4 5 2 1 0编码 6 0000 7 0001 3 001 4 010 5 011 2 100 1 101 0 11 总权值 100个字符的bit数 W T 5 5 4 10 10 10 15 20 3 25 2 285等长码 0 000 1 001 2 010 3 011 4 100 5 101 6 110 7 111 总权值 W2 3 100 300 4 二叉树的周游 遍历 二叉树的周游 对于一棵二叉树的每一个结点都访问一次且仅一次的操作1 做一条绕行整个二叉树的行走路线 不能穿过树枝 2 按行走路线经过结点的位置 左边 下边 右边 得到周游的方法有三种 中序遍历 路线经过结点下边时访问结点 访问的次序 左子树 根 右子树前序遍历 路线经过结点左边时访问结点 访问的次序 根 左子树 右子树后序遍历 路线经过结点右边时访问结点 访问的次序 左子树 右子树 根 中序遍历 次序 左 根 右 前序遍历 次序 根 左 右 后序遍历 次序 左 右 根 中序遍历 cbedgfaIkhj前序遍历 abcdefghikj后序遍历 cegfdbkijha 例 给定二叉树 写出三种访问结点的序列 例 给定二叉树周游的二种周游序列 画出该二叉树 5 二叉排序树将一组需要排序的序列建立二叉排序树建立 不断添加结点为其子树 比根结点小的为左子树比根结点大的为右子树利用周游得出排序结果 中序遍历 例 二叉排序树20 3 4 9 25 36 7 12 18 先建成二叉排序树 以第一个数为根 比根小在左 比根大在右 建成二叉排序树后 中