离散数学第十一章树

《离散数学第十一章树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章树离散数学陈志奎主编人民邮电出版社前言1847年，德国学者柯希霍夫（Kirchhof）在研究物理问题时提出了树的概念。他用一类线性方程组来描述一个电路网络的每一条支路中和环绕每一个回路的电流。他像数学家一样抽象地思考问题：用一个只由点和线组成的相应的组合结构来代替原来的电路网络，而并不指明每条线所代表的电器元件的种类。事实上，他把每个电路网络用一个基本图来代替。为了解相应的方程组，他用一种结构方法指出，只要考虑一个图的任何一个“生成树”所决定的那些独立圈就够了。他的方法现已成为图论中的标准方法。前言1857年，英国数学家凯莱（CaylayArthur）从事计数由

2、给定的碳原子数n的饱和碳氢化合物的同分异构物时，独立地提出了树的概念。凯莱把这个问题抽象地叙述为：求有P个点的树的数目，其中每个点的度等于1或4，树上的点对应一个氢原子或一个碳原子。凯莱的工作是图的计数理论的起源。法国数学家若尔当在1869年作为一个纯数学对象独立地发现了树，他并不知道树与现代的化学学说有关。1889年凯莱给出了完全图Kn的概念。前言1956年Kruskal设计了求最优树的有效算法。树是一类既简单而又非常重要的图，是计算机中一种基本的数据结构和表示方法，在输电网络分析设计、有机化学、最短连接及渠道设计等领域也都有广泛的应用。本章将对树进行详细的讨论，主要

3、包括树的基本性质和生成树，以及有向树中的m叉树、有序树和搜索树等。PART01PART02树与生成树有向树及其应用主要内容11.1树与生成树定义11.1连通且不含回路的图称为树。树中度为1的结点称为叶，度大于1的结点称为枝点或内点。根据这个定义，平凡图K1也是树。K1是一个既无叶又无内点的平凡树。定义11.2在定义11.1中去掉连通的条件，所定义的图称为森林。森林的每个支都是树。6树及其性质11.1树与生成树例11.1图11.1所示是森林，他的每个分支（a）、（b）都是一棵树。图11.17树及其性质11.1树与生成树定理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树与生成树推论11.1任何非平凡树至少有二片叶。证明：设（n,m）树T有t片叶，则，由定理11.1中命题（2），可得，即例11.2设是一棵树，它有两个2度节点，一个3度节点，三个4度节点，求的树叶数。解：设树有片树叶，则的节点数的边数又由得所以，即树有9片树叶。9树及其性质11.1树与生成树推论11.2阶大于2的树必有割

5、点。证明：由知道T至少有一个度数大于1的内点v，再由定理11.1中命题（5），T-v不是连通的，故v必是割点。10树及其性质11.1树与生成树定义11.3若无向（连通图）G的生成子图是一棵树，则称该树是G的生成树或支撑树，记为。生成树中的边称为树枝。图G中其他边称为的弦。所有这些弦的集合称为的补。例11.3图11.2中（b）、（c）所示的树、是图（a）的生成树，而（d）所示的树不是图（a）的生成树。图11.211生成树与最小生成树11.1树与生成树例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树与生成树定理11.2无向图为连通当且仅当有生成树。证明：先采用反证法来证明必要性。若G不连通，则它的任何生成子图也不连通，因此不可能有生成树，与G有生成树矛盾，故G是连通图。再证充分性

7、。设G连通，则G必有连通的生成子图，令T是G的含有边数最少的生成子图，于是T中必无回路（否则删去回路上的一条边不影响连通性，与T含边数最少矛盾），故T是一棵树，即生成树。13生成树与最小生成树11.1树与生成树定义11.4设是加权无向图，，中所有边的加权长度之和称为的加权长度。G的所有生成树中加权长度最小者称为的最小生成树。最小生成树有很广泛的应用。例如要建造一个连接若干城市的通讯网络，已知城市和之间通讯线路的造价，设计一个总造价为最小的通讯网络，就是求最小生成树。14生成树与最小生成树11.1树与生成树例11.5图1