离散数学 第12章 树.ppt

第十二章树主讲 熊焕亮 2 第十二章树 树是图论中重要内容之一 在计算机科学技术中有着广泛的应用 树的概念由数学家约当 Jordan 给出了统一的定义 在讨论本章内容之前 首先作个说明 就是本章所谈回路均指初级回路 圈 或简单回路 而不含复杂回路 有重复边出现的回路 3 第十二章树 12 1树的概念及性质12 2最小生成树12 3根树12 4树的应用 4 12 1树的概念及性质 12 1 1树的定义12 1 2树的一些性质 5 12 1 1树的定义 定义12 1 1若简单连通无回路的无向图称为无向树 或简称树 常用表示树 平凡图称为平凡树 无向树中度数为1的顶点称为树叶 度数大于等于2的顶点称为分支点 只有一个顶点 无边 的简单图称为平凡树 若无向图G至少有两个连通分支 则称G为森林 也就是说 无向 树是连通无回路的简单图 后面提到树时 如果没有特别说明都是指无向树 在证明树的性质前 先回忆一下桥 或说割边 的定义 将看到树的每一条边都是桥 6 12 1 1树的定义 定义12 1 2给定图 说边是G的桥 割边 如果 即G中删除之后会增加连通分支数 显然 如果e是G的桥 则有 即删除一条边 最多增加一个连通分支 另一方面 若e是G的桥 则e不属于G的任意回路 7 12 1 2树的一些性质 无向树有许多性质 这些性质中有些既是树的必要条件又是充分条件 因而都可以看作树的等价定义 见下面定理 8 12 1 2树的一些性质 定理12 1 1设是n阶m条边的无向图 则下面各命题是等价的 1 G是树 2 G中任意两个顶点之间存在惟一的路径 3 G中无回路且 4 G是连通的且 5 G是连通的且G中任何边均为桥 6 G中没有回路 但在任何两个不同的顶点之间加一条新边 在所得图中得到惟一的一个含新边的圈 9 12 1 2树的一些性质 证 1 2 对n作归纳 n 1时 m 0 显然有m n 1 假设n k时命题成立 现证n k 1也成立 由于G连通而无回路 所以G中至少有一个度数为1的结点 在G中删去及其关联的边 便得到k个结点的连通而无回路的图 由归纳假设知它有k 1条边 再将结点及其关联的边加回到原图G 所以G中含有k 1个结点和k条边 符合公式m n 1 所以 G中无回路 且m n 1 10 12 1 2树的一些性质 2 3 首先证明G中无回路 若G中存在关联某顶点v的环 则v到v存在长为0和1的两条路径 注意初级回路是路径的特殊情况 这与已知矛盾 若G中存在长度大于或等于2的圈 则圈上任何两个顶点之间都存在两条不同的路径 这也引出矛盾 下面用归纳法证明m n 1 n 1时 G为平凡图 结论显然成立 设n时结论成立 当n k 1时 设为G中的一条边 由于G中无回路 所以G e为两个连通分支 设分别为中的顶点数和边数 则 由归纳假设可知 于是 11 12 1 2树的一些性质 3 4 只要证明G是连通的 否则设G有个连通分支 中均无回路 因而全为树 由 1 2 3 可知 于是由于 这与矛盾 12 12 1 2树的一些性质 4 5 若G不连通 则存在两结点和 在和之间无通路 此时增加边 不会产生回路 但这与题设矛盾 由于G无回路 所以删去任一边 图便不连通 13 12 1 2树的一些性质 5 6 由于G中每条边均为桥 因而G中无圈 又由于G连通 所以G为树 由 1 2 可知 且 则之间存在惟一的路径 则 为加的新边 为中G的圈 显然圈是惟一的 14 12 1 2树的一些性质 6 1 只要证明G是连通的 且 则新边产生惟一的圈 显然有为G中u到v的通路 故u v 由的任意性可知 G是连通的 15 12 2最小生成树 12 2 1生成树12 2 2最小代价生成树 16 12 2 1生成树 任何无向连通图都有一种特殊的生成子图 这就是树 17 12 2 1生成树 定义12 2 1设T是无向图G的子图并且为树 则称T为G的树 若T是G的树且为生成子图 则称T是G的生成树 设T的G生成树 若则称e为T的树枝 否则称e为T的弦 并称导出子图为T的余树 记作 注意不一定连通 也不一定不含回路 在图12 2 1所示图中 实边图为该图的一棵生成树T 余树为虚边所示 它不连通 同时也含回路 18 12 2 1生成树 图12 2 1余树概念示意图 19 12 2 1生成树 定理12 2 1无向图G具有生成树当且仅当G是连通图 证必要性显然 只需证明充分性 若G中无回路 G为自己的生成树 若G中含圈 任取一圈 随意地删除圈上的一条边 若再有圈再删除圈上的一条边 直到最后无圈为止 易知所得图无圈 当然无回路 连通且为G的生成子图 即G的生成树 常称此种产生生成树的方法为破圈法 20 12 2 1生成树 推论12 2 1设G为n阶m条边的无向连通图 则 证由定理12 2 1可知 G有生成树 设T为G的一棵生成树 则 21 12 2 1生成树 推论12 2 2设G是n阶m条边的无向连通图 T为G的生成树 则T的余树中含条边 即T有条弦 由推论12 2 1立刻可知推论12 2 2正确 22 12 2 1生成树 推论12 2 3设T是连通图G的一棵生成树 为T的余树 C为G中任意一个圈 则 证若 则这说明C为T中圈 这与T为树矛盾 23 12 2 1生成树 定理12 2 2设T为无向连通图G中一棵生成树 e为T的任意一条弦 则T中含G中只含一条弦其余边均为树枝的圈 而且不同的弦对应的圈也不同 证设 由定理12 1 1可知 在T中 之间存在惟一的路径 则满足要求 不同的弦对应的圈也不同是显然的 24 12 2 1生成树 由定理12 2 2 可以给出下面的定义 定义12 2 3设T是n阶m条边的无向连通图G的一棵生成树 设 为T的弦 设为T添加弦产生的G中只含弦 其余边均为树枝的圈 称为G的对应T的弦的基本回路或基本圈 并称为G对应T的基本回路系统 称为G的圈秩 记作 25 12 2 1生成树 在图12 2 1中 对应生成树的弦分别为 设它们对应的基本回路分别为 从对应的弦开始 按顺时针 也可都按逆时针 的顺序写出它们 分别为 26 12 2 1生成树 上图的圈秩为5 基本回路系统为 从定义不难看出 无向连通图的圈秩与生成树的选取无关 但不同生成树对应的基本回路系统可能不同 27 12 2 1生成树 定理12 2 3设T是连通图G的一棵生成树 e为T的树枝 则G中存在只含树枝e 其余边都是弦的割集 且不同的树枝对应的割集也不同 证由定理12 1 1可知 e是T的桥 因而有两个连通分支和 令且e的两个端点分别属于和 由构造显然可知为G的割集 且中除e外都是弦 所以为所求 不同树枝对应的割集是不同的也是显然的 28 12 2 1生成树 定义12 2 4设T是n阶连通图G的一棵生成树 为T的树枝 是G的只含树枝的割集 则称为G的对应生成树T由树枝生成的基本割集 并称为G对应T的基本割集系统 称n 1为G的割集秩 记作 在图12 2 1所示图中 为T的树枝 设它们对应的基本割集分别为 以树枝为集合中第一个元素的方式写出它们 当然集合中的元素是不讲顺序的 这里为了区分树枝和弦 基本割集系统为 割集秩为6 连通图G的割集秩 不因生成树的不同而改变 但不同生成树对应的基本割集系统可以不同 29 12 2 2最小代价生成树 下面讨论求连通带权图中的最小生成树问题 定义12 2 5设无向连通带权图 T是G的一棵生成树 T的各边权之和称为T的权 记作 G的所有生成树中权最小的生成树称为G的最小生成树 求最小生成树已经有许多算法 这里介绍避圈法 Kruskal算法 设n阶无向连通带权圈有m条边 不妨设G中没有环 否则 可以将所有的环先删去 将m条边按权从小到大顺序排列 设为 取在T中 然后依次检查 若与已在T中的边不能构成回路 则取在T中 否则弃去 算法停止时得到的T为G的最小生成树 证明略 30 12 2 2最小代价生成树 例题12 2 1求图12 2 2所示两个图中的最小生成树 31 12 2 2最小代价生成树 解用避圈法算法 求出的 a 中最小生成树为图12 2 3中 a 中实线边所示的生成树 b 中的最小生成树 b 为图12 2 3中实边所示的生成树 32 12 3根树 12 3 1根树的定义12 3 2根树的分类 33 12 3 1根树的定义 定义12 3 1一个有向图 若略去所有有向边的方向所得到的无向图是一棵树 则这个有向图称为有向树 34 12 3 1根树的定义 定义12 3 2一棵平凡的有向树 如果恰有一个结点的入度为0 其余所有结点的入度均为1 则称之为根树或外向树 入度为0的结点称为根 出度为0的结点称为叶 入度为1 出度大于0的结点称为内点 又将内点和根统称为分支点 在根树中 从根到任一结点的通路长度 称为该结点的层数 称层数相同的结点在同一层上 所有结点的层数中最大的称为根树的高 35 12 3 1根树的定义 定义12 3 3在根树中 若从结点可达 则称是的祖先 是的后代 又若 是根树中的有向边 则称是的父亲 是的儿子 如果两个结点是同一个结点的儿子 则称这两个结点是兄弟 36 12 3 2根树的分类 定义12 3 4如果在根树中规定了每一层上结点的次序 这样的根树称为有序树 37 12 3 2根树的分类 定义12 3 5在根树T中 若每个分支点至多有k个儿子 则称为k元树 若每个分支点都恰有k个儿子 则称T为k元完全树 若k元树T是有序的 则称T为k元有序树 若k元完全树T是有序的 则称T为k元有序完全树 在根树T中 任一结点v及其所有后代导出的子图称为T的以v为根的子树 二元有序树的每个结点v至多有两个儿子 分别称为v的左儿子和右儿子 二元有序树的每个结点v至多有两棵子树 分别称为v的左子树和右子树 38 12 3 2根树的分类 例12 3 1判断图12 3 1中的几棵根树是什么树 解在图12 3 1 a 中每个分支结点恰有2个儿子 因此是2元完全树 b 中分支结点有的有3个儿子 有的有2个儿子 因此是3元树 c 中每个分支结点恰有3个儿子 因此是3元完全树 d 中每个分支结点恰有3个儿子 并且对所有边都给出了次序 因此是3元有序完全树 39 12 3 2根树的分类 定理12 3 1在k元完全树中 若叶数为t 分支点数为i 则下式成立 证明由假设知 该树有个结点 该树的边数为 由握手定理知 所有结点的出度之和等于边数 而根据元完全树的定义知 所有分支点的出度为 因此有即 40 12 4树的应用 12 4 1决策树12 4 2博奕树 41 12 4 1决策树 定义12 4 1设有一棵树 如果其每个分支点都代表一个提出的问题 从根开始 每回答一个问题 走相应的边 最后到达一个叶结点 即获得一个决策 则称之为决策树 42 12 4 1决策树 例12 4 1 硬币问题 现有5枚外观一样的硬币 只有1枚硬币与其它的重量不同 问如何用一架天平来判别哪枚硬币是坏的 重还是轻 分析用天平来称和两枚硬币 只有 三种可能的情形 因此可构造3元决策树来解决 43 12 4 1决策树 图12 4 1例12 4 1决策树 44 12 4 1决策树 解设硬币标号为A B C D E 用 表示分别将硬币A和B放入天平的左右两边 用 表示左边比右边重 表示A是坏币而且轻 表示A是坏币而且重 其余类似 构造决策树如图所示 从根到叶就是一种求解过程 由于该树有10片叶子 因此最多有10种可能的解 又由于该树高为3 因此最坏情形下需要3次判别就能得到结论 45 12 4 2博奕树 实际生活中有很多有益的博奕 如围棋 象棋 五子棋等 每名选手交替动作 直至结束 下面介绍如何将根树应用到博奕比赛策略的研究中 46 12 4 2博奕树 例12 4 2现有7根火柴 甲 乙两人依次从中取走1根或2根 但不能不取 取走最后一根的就是胜利者 分析由于每次甲 乙至多有2种选择 因此可构造2元博奕树来解决 解用7表示轮到甲取时有7根火柴 4表示轮到乙取时有4根火柴 以此类推 得到2元博奕树 47 12 4 2博奕树 图12 4 2博弈树示意图 48 12 4 2博奕树 显然 当出现1或2时 甲获胜 不必再进行下去 同样 1或者2是乙获胜的状态 若甲获胜时 设其得1分 乙获胜时甲得 1分 无疑轮