离散数学树ppt课件.ppt

第16章树 离散数学 本章说明 树是图论中重要内容之一 本章所谈回路均指初级回路 圈 或简单回路 不含复杂回路 有重复边出现的回路 2 16 1无向树及其性质 定义16 1无向树 连通无回路的无向图 简称树 用T表示 平凡树 平凡图 森林 若无向图G至少有两个连通分支 每个都是树 树叶 无向图中悬挂顶点 分支点 度数大于或等于2的顶点 举例如图为九个顶点的树 3 定理16 1设G 是n阶m条边的无向图 则下面各命题是等价的 1 G是树 2 G中任意两个顶点之间存在唯一的路径 3 G中无回路且m n 1 4 G是连通的且m n 1 5 G是连通的且G中任何边均为桥 6 G中没有回路 但在任何两个不同的顶点之间加一条新边 在所得图中得到唯一的一个含新边的圈 无向树的等价定义 4 1 2 如果G是树 则G中任意两个顶点之间存在唯一的路径 存在性 由G的连通性及定理14 5的推论 在n阶图G中 若从顶点vi到vj vi vj 存在通路 则vi到vj一定存在长度小于等于n 1的初级通路 路径 可知 u v V u与v之间存在路径 唯一性 反证法 若路径不是唯一的 设 1与 2都是u到v的路径 易知必存在由 1和 2上的边构成的回路 这与G中无回路矛盾 5 2 3 如果G中任意两个顶点之间存在唯一的路径 则G中无回路且m n 1 首先证明G中无回路 若G中存在关联某顶点v的环 则v到v存在长为0和1的两条路经 注意初级回路是路径的特殊情况 这与已知矛盾 若G中存在长度大于或等于2的圈 则圈上任何两个顶点之间都存在两条不同的路径 这也与已知矛盾 6 2 3 如果G中任意两个顶点之间存在唯一的路径 则G中无回路且m n 1 其次证明m n 1 归纳法 n 1时 G为平凡图 结论显然成立 设n k k 1 时结论成立 当n k 1时 设e u v 为G中的一条边 由于G中无回路 所以G e为两个连通分支G1 G2 设ni mi分别为Gi中的顶点数和边数 则ni k i 1 2 由归纳假设可知mi ni 1 于是m m1 m2 1 n1 1 n2 1 1 n1 n2 1 n 1 7 只需证明G是连通的 采用反证法 假设G是不连通的 由s s 2 个连通分支G1 G2 Gs组成 并且Gi中均无回路 因而Gi全为树 由 1 2 3 可知 mi ni 1 于是 由于s 2 与m n 1矛盾 3 4 如果G中无回路且m n 1 则G是连通的且m n 1 8 如果G是连通的且m n 1 则G是连通的且G中任何边均为桥 只需证明G中每条边均为桥 e E 均有 E G e n 1 1 n 2 由习题十四题49 若G是n阶m条边的无向连通图 则m n 1 可知 G e已不是连通图 所以 e为桥 4 5 9 如果G是连通的且G中任何边均为桥 则G中没有回路 但在任何两个不同的顶点之间加一条新边 在所得图中得到唯一的一个含新边的圈 因为G中每条边均为桥 删掉任何边 将使G变成不连通图 所以 G中没有回路 也即G中无圈 又由于G连通 所以G为树 由 1 2 可知 u v V 且u v 则u与v之间存在唯一的路径 则 u v u v 为加的新边 为G中的圈 显然圈是唯一的 5 6 10 如果G中没有回路 但在任何两个不同的顶点之间加一条新边 在所得图中得到唯一的一个含新边的圈 则G是树 只需证明G是连通的 u v V 且u v 则新边 u v G产生唯一的圈C 显然有C u v 为G中u到v的通路 故u v 由u v的任意性可知 G是连通的 6 1 11 定理16 2设T是n阶非平凡的无向树 则T中至少有两片树叶 设T有x片树叶 由握手定理及定理16 1可知 证明 由上式解出x 2 无向树的性质 12 例16 1 例16 1画出6阶所有非同构的无向树 解答设Ti是6阶无向树 由定理16 1可知 Ti的边数mi 5 由握手定理可知 dTi vj 10 且 Ti 1 Ti 5 于是Ti的度数列必为以下情况之一 1 1 1 1 1 1 5 2 1 1 1 1 2 4 3 1 1 1 1 3 3 4 1 1 1 2 2 3 5 1 1 2 2 2 2 4 对应两棵非同构的树 在一棵树中两个2度顶点相邻 在另一棵树中不相邻 其他情况均能画出一棵非同构的树 13 例16 1 人们常称只有一个分支点 且分支点的度数为n 1的n n 3 阶无向树为星形图 称唯一的分支点为星心 14 例16 2 例16 27阶无向图有3片树叶和1个3度顶点 其余3个顶点的度数均无1和3 试画出满足要求的所有非同构的无向树 解答设Ti为满足要求的无向树 则边数mi 6 于是 d vj 12 e 3 d v4 d v5 d v6 由于d vj 1 d vj 3 而且d vj 1且d vj 6 j 4 5 6 可知d vj 2 j 4 5 6 于是Ti的度数列为1 1 1 2 2 2 3由度数列可知 Ti中有一个3度顶点vi vi的邻域N vi 中有3个顶点 这3个顶点的度数列只能为以下三种情况之一 1 1 21 2 22 2 2设它们对应的树分别为T1 T2 T3 此度数列只能产生这三棵非同构的7阶无向树 15 例16 2 16 例题 例题已知无向树T中 有1个3度顶点 2个2度顶点 其余顶点全是树叶 试求树叶数 并画出满足要求的非同构的无向树 解答设有x片树叶 于是结点总数为n 1 2 x 3 x由握手定理和树的性质m n 1可知 2m 2 n 1 2 2 x 1 3 2 2 x解出x 3 故T有3片树叶 故T的度数应为1 1 1 2 2 3 17 例题已知无向树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 例题 18 小节结束 例题 19 16 2生成树 定义16 2设G为无向图 1 T为G的树 T是G的子图并且是树 2 T为G的生成树 T是G的生成子图并且是树 3 e为T的树枝 设T是G的生成树 e E G 若e E T 4 e为T的弦 设T是G的生成树 e E G 若e E T 5 生成树T的余树 导出子图G E G E T 记作 20 注意 不一定连通 也不一定不含回路 说明 21 定理16 3无向图G具有生成树当且仅当G连通 证明必要性 显然 充分性 破圈法 若G中无回路 G为自己的生成树 若G中含圈 任取一圈 随意地删除圈上的一条边 若再有圈再删除圈上的一条边 直到最后无圈为止 易知所得图无圈 当然无回路 连通且为G的生成子图 所以为G的生成树 生成树的存在条件 22 最小生成树 定义16 5设T是无向连通带权图G 的一棵生成树 T的各边权之和称为T的权 记作W T G的所有生成树中权最小的生成树称为G的最小生成树 求最小生成树的算法 避圈法 Kruskal 1 设n阶无向连通带权图G 有m条边 不妨设G中没有环 否则 可以将所有的环先删去 将m条边按权从小到大排序 e1 e2 em 2 取e1在T中 3 依次检查e2 em 若ej j 2 与已在T中的边不构成回路 取ej也在T中 否则弃去ej 4 算法停止时得到的T为G的最小生成树为止 23 例16 3 例16 3求下图所示两个图中的最小生成树 W T1 6 W T2 12 24 例题 例如求所示图的一棵最小生成树 解答 最小生成树W T 38 小节结束 25 16 3根树及其应用 设D是有向图 若D的基图是无向树 则称D为有向树 在所有的有向树中 根树最重要 所以我们只讨论根树 二叉树的应用 26 根树的定义 定义16 6T是n n 2 阶有向树 1 T为根树 T中有一个顶点入度为0 其余顶点的入度均为1 2 树根 入度为0的顶点 3 树叶 入度为1 出度为0的顶点 4 内点 入度为1 出度不为0的顶点 5 分支点 树根与内点的总称 6 顶点v的层数 从树根到v的通路长度 7 树高 T中层数最大顶点的层数 8 根树 平凡树 27 根树的画法 树根放上方 省去所有有向边上的箭头 树叶 8片内点 6个分支点 7个高度 5 28 家族树 常将根树看成家族树 家族中成员之间的关系如下定义 定义16 7设T为一棵非平凡的根树 vi vj V T 若vi可达vj 则称vi为vj的祖先 vj为vi的后代 若vi邻接到vj 即 E T 则称vi为vj的父亲 而vj为vi的儿子 若vj vk的父亲相同 则称vj与vk是兄弟 定义16 8设v为根树T中任意一顶点 称v及其后代的导出子图为以v为根的根子树 29 根树的分类 1 设T为根树 若将T中层数相同的顶点都标定次序 则称T为有序树 2 分类 根据根树T中每个分支点儿子数以及是否有序r叉树 每个分支点至多有r个儿子r叉有序树 r叉树是有序的r叉正则树 每个分支点恰有r个儿子r叉正则有序树 r叉正则树是有序的r叉完全正则树 树叶层数均为树高的r叉正则树r叉完全正则有序树 r叉完全正则树是有序的 30 最优二叉树 定义16 9设2叉树T有t片树叶v1 v2 vt 权分别为w1 w2 wt 称为T的权 其中l vi 是vi的层数 在所有有t片树叶 带权w1 w2 wt的2叉树中 权最小的2叉树称为最优2叉树 31 举例 下图所示的三棵2叉树T1 T2 T3都是带权为2 2 3 3 5的2叉树 W T1 2 2 2 2 3 3 5 3 3 2 38W T2 3 4 5 4 3 3 2 2 2 1 47W T3 3 3 3 3 5 2 2 2 2 2 36 32 求最优树的算法 Huffman算法 给定实数w1 w2 wt 且w1 w2 wt 连接权为w1 w2的两片树叶 得一个分支点 其权为w1 w2 在w1 w2 w3 wt中选出两个最小的权 连接它们对应的顶点 不一定是树叶 得新分支点及所带的权 重复 直到形成t 1个分支点 t片树叶为止 33 算法举例 例如 求带权为1 1 2 3 4 5的最优树 解答 W T 38 34 1 最佳前最码的定义定义16 10设 1 2 n 1 n是长度为n的符号串 称其子串 1 1 2 1 2 n 1分别为该字符串的长度为1 2 n的前缀 设A 1 2 m 为一个符号串集合 若对于任意的 i j A i j i j互不为前缀 则称A为前缀码 若 i i 1 2 m 中只出现0与1两个符号 则称A为二元前缀码 2 如何产生二元前缀码 定理16 6由一棵给定的2叉正则树 可以产生唯一的一个二元前缀码 最佳前缀码 35 方法 将每个分支点引出的两条边分别标上0和1 结果 图所示树产生的前缀码为 00 10 11 011 0100 0101 36 用Huffman算法产生最佳前缀码 例16 6在通信中 八进制数字出现的频率如下 0 25 1 20 2 15 3 10 4 10 5 10 6 5 7 5 求传输它们的最佳前缀码 求传输10n n 2 个按上述比例出现的八进制数字需要多少个二进制数字 若用等长的 长为3 的码字传输需要多少个二进制数字 37 解答 以100乘各频率为权 并按小到大排列 得w1 5 w2 5 w3 10 w4 10 w5 10 w6 15 w7 20 w8 25 产生的最优树如下 0 011 112 0013 1004 1015 00016 000007 00001 传100个按比例出现的八进制数字所需二进制数字个数W T 285 所以传10n n 2 个所用二进制数字应为2 85 10n 用等长码 长为3 应该用3 10n个数字 38 由于在每一步选择两个最小的权的选法不唯一 因为两个权对应的顶点所放左右位置不同 画出的最优树可能不同 最佳前缀码并不唯一 但有一点是共同的 就是它们的权应该相等 即它们都应该是最优树 说明 39 3 波兰符号法与逆波兰符号法对一棵根树的每个顶点