《[2017年整理]离散数学第十一章 树》由会员分享，可在线阅读，更多相关《[2017年整理]离散数学第十一章 树（49页珍藏版）》请在金锄头文库上搜索。
1、第十一章 树离散数学 陈志奎主编 人民邮电出版社前言n1847年，德国学者柯希霍夫（Kirchhof）在研究物理问题时提出了树的概念。他用一类线性方程组来描述一个电路网络的每一条支路中和环绕每一个回路的电流。他像数学家一样抽象地思考问题：用一个只由点和线组成的相应的组合结构来代替原来的电路网络，而并不指明每条线所代表的电器元件的种类。事实上，他把每个电路网络用一个基本图来代替。为了解相应的方程组，他用一种结构方法指出，只要考虑一个图的任何一个“生成树”所决定的那些独立圈就够了。他的方法现已成为图论中的标准方法。前言n1857年，英国数学家凯莱（Caylay Arthur）从事计数由给定的碳原子
2、数n的饱和碳氢化合物的同分异构物时，独立地提出了树的概念。凯莱把这个问题抽象地叙述为：求有P个点的树的数目，其中每个点的度等于1或4，树上的点对应一个氢原子或一个碳原子。凯莱的工作是图的计数理论的起源。法国数学家若尔当在1869年作为一个纯数学对象独立地发现了树，他并不知道树与现代的化学学说有关。n1889年凯莱给出了完全图Kn的概念。前言n1956年Kruskal设计了求最优树的有效算法。n树是一类既简单而又非常重要的图，是计算机中一种基本的数据结构和表示方法，在输电网络分析设计、有机化学、最短连接及渠道设计等领域也都有广泛的应用。n本章将对树进行详细的讨论，主要包括树的基本性质和生成树，以
3、及有向树中的m叉树、有序树和搜索树等。PART PART 0101PART PART 0202树与生成树有向树及其应用主要内容11.1 树与生成树n定义11.1 连通且不含回路的图称为树。树中度为1的结点称为叶，度大于1的结点称为枝点或内点。根据这个定义，平凡图K1也是树。K1是一个既无叶又无内点的平凡树。n定义11.2 在定义11.1中去掉连通的条件，所定义的图称为森林。森林的每个支都是树。6树及其性质11.1 树与生成树n例11.1 图11.1所示是森林，他的每个分支（a）、（b）都是一棵树。图11.17树及其性质11.1 树与生成树n定理11.1 设T是无向（n，m）图，则下述命题相互等
4、价。 （1）T连通且无回路。 （2）T无回路且m=n-1。 （3）T连通且m=n-1。 （4）T无回路但新增加任何一条边（端点属于T）后有且仅有一个回路。 （5）T连通，但是删去任何一边后便不再连通。 （6）T的每一对结点之间有且仅有一条道路可通。8树及其性质11.1 树与生成树n推论11.1 任何非平凡树至少有二片叶。证明：设（n,m）树T有t片叶，则 ，由定理11.1中命题（2），可得 ，即n例11.2 设 是一棵树，它有两个2度节点，一个3度节点，三个4度节点，求 的树叶数。解：设树 有 片树叶，则 的节点数的边数又由 得 所以 ，即树 有9片树叶。9树及其性质11.1 树与生成树n推论
5、11.2 阶大于2的树必有割点。证明：由 知道T至少有一个度数大于1的内点v，再由定理11.1中命题（5），T-v不是连通的，故v必是割点。10树及其性质11.1 树与生成树n定义11.3 若无向（连通图）G的生成子图是一棵树，则称该树是G的生成树或支撑树，记为 。生成树 中的边称为树枝。图G中其他边称为 的弦。所有这些弦的集合称为 的补。n例11.3 图11.2中（b）、（c）所示的树 、 是图（a）的生成树，而（d）所示的树 不是图（a）的生成树。图11.211生成树与最小生成树11.1 树与生成树n例11.4 某地要兴建个工厂，拟修筑道路连接这处。经勘测其道路可依如图11.2（a）的无向
6、边铺设。为使这处都有道路相通，问至少要铺几条路？解：这实际上是求 G 的生成树的边数问题。 一般情况下，设连通图 G 有n个节点，m条边。由树的性质知，T有n个节点，n-1条树枝，m-n+1 条弦。 在图11.2（a）中， n=5，则n-1=4 ，所以至少要修条路才行。 由图11.2可见，要在一个连通图 中找到一棵生成树，只要不断地从 的回路上删去一条边，最后所得无回路的子图就是 的一棵生成树。于是有以下定理。12生成树与最小生成树11.1 树与生成树n定理11.2 无向图 为连通当且仅当 有生成树。证明：先采用反证法来证明必要性。若 G 不连通，则它的任何生成子图也不连通，因此不可能有生成树
7、，与 G 有生成树矛盾，故 G 是连通图。再证充分性。设 G 连通，则 G 必有连通的生成子图，令 T 是 G 的含有边数最少的生成子图，于是 T 中必无回路（否则删去回路上的一条边不影响连通性，与 T 含边数最少矛盾），故 T 是一棵树，即生成树。13生成树与最小生成树11.1 树与生成树n定义11.4 设是加权无向图， ， 中所有边的加权长度之和称为 的加权长度。G的所有生成树中加权长度最小者称为的最小生成树。最小生成树有很广泛的应用。例如要建造一个连接若干城市的通讯网络，已知城市 和 之间通讯线路的造价，设计一个总造价为最小的通讯网络，就是求最小生成树 。14生成树与最小生成树11.1
8、树与生成树n例11.5 图11.3显示了利用Kruskal算法生成最小生成树的过程。通俗地讲，该算法就是想将图中的边按权重从小到大排列，再从小到大一次取出每条边做检查。一开始取最小的边，由该边导出一部分子图，然后依次每取一边加入得到的部分子图。若仍为无回路，将该边与原有部分子图的边导出一个新子图；若得到回路，将该边放弃。上述过程继续进行直到所有的边都检查完毕，这样得到的生成子图就是最小生成树。图11.315生成树与最小生成树11.1 树与生成树nKruskal算法 （1）选取G中权最小的一条边，设为 。令 （2）若 ，输出G（S），算法结束。 （3）设已选边构成集合 。从E-S中选边 ，使其满
9、足条件： 不含圈； 在E-S的所有满足条件的边中， 有最小的权。 （4） 转（2）。16生成树与最小生成树PART PART 0101PART PART 0202树与生成树有向树及其应用主要内容11.2 有向树及其应用n定义11.5 一个结点的入度为0，其余结点的入度均为1的弱连通有向图，称为有向树。在有向树中，入度为0的结点称为根，出度为0的结点称为叶，出度大于0的结点称为分支结点，从根至任意结点的距离称为该结点的层或级，所有结点的级的最大值称为有向树的高度。n例11.6 图11.4画出了一棵有向树， 是根， 是叶， 是分支结点，定点 的层数是1，树的高度是3。图11.418有向树11.2
10、有向树及其应用n定理11.3 设 是有向图D的结点。D是以 为根的有向树，当且仅当从 至D的任意结点恰有一条路径。19有向树11.2 有向树及其应用n定义11.6 每个弱分支都是有向树的有向图，称为有向森林。n定义11.7 在有向树中，若从 到 可达，则称 是 的祖先， 是 的后代；又若是根树中的有向边，则称 是 的父亲， 是 的儿子；如果两个节点是同一节点的儿子，则称这两个节点是兄弟。20有向树11.2 有向树及其应用n定义11.8 在有向树T中，若任何结点的出度最多为m，则称T为m叉树；如果每个分支结点的出度都等于m，则称T为完全m叉树；进一步，若T的全部叶点位于同一层次，则称T为正则m叉
11、树。n例11.7 在图11.5(a)是一棵二叉树，而且是正则二叉树；图11.5(b)是一棵完全二叉树；图11.5(c)是一棵三叉树，而且是正则三叉树；图11.5(d)是一棵完全三叉树。21m叉树图11.511.2 有向树及其应用n定理11.4 若T是完全m叉树，其叶数为t，分枝点数为i，则 证明：在分枝点中，除根的度数为m外，其余各分枝结点的度皆为m+1。各叶点的度为1，总边数为mi，由图论基本定理得到 即这个定理实质上可以用每局有m个选手参加的单淘汰制比赛来说明。t个叶表示t个参赛的选手，i则表示必须按排的总的比赛局数。每一局由m个参赛者中产生一个优胜者，最后决出一个冠军。22m叉树11.2
12、 有向树及其应用n例11.8 设有28盏电灯，拟公用一个电源插座，问需要多少块具有四插座的接线板？这个公用插座可以看成是正则四叉树的根，每个接线板看成是其它的分枝点，灯泡看成是叶，则问题就是求总的分枝点的数目，由定理11.4可以算得 。因此，至少需要9块接线板才能达到目的。23m叉树11.2 有向树及其应用n定义11.9 设V是二叉树D的叶子的集合，R+是全体正实数的集合，W:VR+，则称为加权二叉树。对于D的任意叶v，称W(v)为v的权 ，称 （其中 ,V是叶子的集合）为的叶加权路径长度，其中W(v)是叶子v的权，L(v)为v的级。我们用叶子表示字母或符号，用分支结点表示判断，用权表示字母或
13、符号出现的机率，则叶加权路径长度就表示算法的平均执行时间。2411.2 有向树及其应用n例11.9 图11.6（a）和（b）表示了识别A,B,C,D的两个算法，A,B,C,D出现的概率分别是0.5，0.3，0.05，0.15。图11.6（b）表示的算法优于11.6（a）表示的算法。25图11.611.2 有向树及其应用n定义11.10 设是叶加权二叉树。如果对于一切叶加权二叉树 只要对于任意正实数r，D和 中权等于r的叶的数目相同，就有的叶加权路径长度不大于 的叶加权路径长度，则称为最优的。这样，我们把求某问题的最佳算法就归结为求最优二叉树的问题。2611.2 有向树及其应用假定我们要找有m片
14、叶，并且它们的权分别为 的最优二叉树。不妨设 是按递增顺序排列的。即 。设是满足要求的最优二叉树，D中以 为权的叶分别为 。显然，在所有的叶中， 和 的级最大。不妨设 和 与同一个分支结点 邻接，令 ，并且 ，容易证明，是最优的，当且仅当 是最优的。这样把求m片叶的最优二叉树归结为求m-1片叶的最优二叉树。继续这个过程，直到归结为求两片叶的最优二叉树，问题就解决了。2711.2 有向树及其应用n例11.10 求叶的权分别为0.1、0.3、0.4、0.5、0.5、0.6、0.9的最优二叉树。计算过程如下：所得出的最优二叉树如图11.7所示，叶中的数表示权，所有分支结点中的数之和就是叶加权路径长度。28图11.711.2 有向树及其应用n定义11.11 如果在有向树中规定了每一层次上节点的次序，这样的有向树称为有序树。在有序树中规定同一层次节点的次序是从左至右。29有序树11.2 有向树及其应用n例11.11 我们可以用有向有序树表达算术表达式，其中叶表示参加运算的数或变量，分支节点表示运算符。如代数式
