前言
1956年Kruskal设计了求最优树的有效算法。 树是一类既简单而又非常重要的图，是计算机中一种基本的数据结构和 表示方法，在输电网络分析设计、有机化学、最短连接及渠道设计等领 域也都有广泛的应用。 本章将对树进行详细的讨论，主要包括树的基本性质和生成树，以及有 向树中的m叉树、有序树和搜索树等。
11.1 树与生成树
生成树与最小生成树
定理11.2 无向图 为连通当且仅当 有生成树。
证明：先采用反证法来证明必要性。 若 G 不连通，则它的任何生成子图也不连通，因此不可能有生成树，与 G 有 生成树矛盾，故 G 是连通图。 再证充分性。 设 G 连通，则 G 必有连通的生成子图，令 T 是 G 的含有边数最少的生成子图， 于是 T 中必无回路（否则删去回路上的一条边不影响连通性，与 T 含边数最少矛 盾），故 T 是一棵树，即生成树。
第十一章 树
离散数学
陈志奎主编 人民邮电出版社
前言
1847年，德国学者柯希霍夫（Kirchhof）在研究物理问题时提出了树 的概念。他用一类线性方程组来描述一个电路网络的每一条支路中和环 绕每一个回路的电流。他像数学家一样抽象地思考问题：用一个只由点 和线组成的相应的组合结构来代替原来的电路网络，而并不指明每条线 所代表的电器元件的种类。事实上，他把每个电路网络用一个基本图来 代替。为了解相应的方程组，他用一种结构方法指出，只要考虑一个图 的任何一个“生成树”所决定的那些独立圈就够了。他的方法现已成为 图论中的标准方法。
证明：由 m 知道T至少有一个度数大于1的内点v，再由定理11.1中命题（5）， n 1 T-v不是连通的，故v必是割点。
11.1 树与生成树
生成树与最小生成树
定义11.3 若无向（连通图）G的生成子图是一棵树，则称该树是G的生
成树或支撑树，记为 T
T
G
G
。生成树 T
G
G
中的边称为树枝。图G中其他边称为
11.1 树与生成树
生成树与最小生成树
定义11.4 设<G，W>是加权无向图， G' G ， G ' 中所有边的加权长度 之和称为 G ' 的加权长度。G的所有生成树中加权长度最小者称为<G， W>的最小生成树。
最小生成树有很广泛的应用。例如要建造一个连接若干城市的通讯网络，已知
城市 v i 和 v
前言
1857年，英国数学家凯莱（Caylay Arthur）从事计数由给定的碳原子 数n的饱和碳氢化合物的同分异构物时，独立地提出了树的概念。凯莱把 这个问题抽象地叙述为：求有P个点的树的数目，其中每个点的度等于1 或4，树上的点对应一个氢原子或一个碳原子。凯莱的工作是图的计数理 论的起源。法国数学家若尔当在1869年作为一个纯数学对象独立地发现 了树，他并不知道树与现代的化学学说有关。 1889年凯莱给出了完全图Kn的概念。
i 1
213 x 的节点数 n
n15 x T 的边数 m
又由 2 m d( vi )
n
( 5 x )2 2 3 1 4 3 x 得2
所以 x
i 1
9，即树 T
有9片树叶。
11.1 树与生成树
树及其性质
推论11.2 阶大于2的树必有割点。
解：这实际上是求 G 的生成树的边数问题。 一般情况下，设连通图 G 有n个节点，m条边。由树的性质知，T有n个节点， n-1条树枝，m-n+1 条弦。 在图11.2（a）中， n=5，则n-1=4 ，所以至少要修４条路才行。 由图11.2可见，要在一个连通图 中找到一棵生成树，只要不断地从 的回路上 删去一条边，最后所得无回路的子图就是 的一棵生成树。于是有以下定理。
的补。
的弦。所有这些弦的集合称为 T
例11.3 图11.2中（b）、（c）所示的树 、 是图（a）的生成树，而（d）所示的 树 不是图（a）的生成树。
图11.2
11.1 树与生成树
生成树与最小生成树
例11.4 某地要兴建５个工厂，拟修筑道路连接这５处。经勘测其道路可依如图
11.2（a）的无向边铺设。为使这５处都有道路相通，问至少要铺几条路？
j
之间通讯线路的造价，设计一个总造价为最小的通讯网络，就是求最
小生成树 。
11.1 树与生成树
生成树与最小生成树
例11.5 图11.3显示了利用Kruskal算法生成最小生成树的过程。通俗地讲，该算 法就是想将图中的边按权重从小到大排列，再从小到大一次取出每条边做检查。一 开始取最小的边，由该边导出一部分子图，然后依次每取一边加入得到的部分子图。 若仍为无回路，将该边与原有部分子图的边导出一个新子图；若得到回路，将该边 放弃。上述过程继续进行直到所有的边都检查完毕，这样得到的生成子图就是最小
主要内容
PART 01
树与生成树
PART 02
有向树及其应用
11.1 树与生成树
树及其性质
定义11.1 连通且不含回路的图称为树。树中度为1的结点称为叶，度大 于1的结点称为枝点或内点。
根据这个定义，平凡图K1也是树。K1是一个既无叶又无内点的平凡树。
定义11.2 在定义11.1中去掉连通的条件，所定义的图称为森林。森林 的每个支都是树。
11.1 树与生成树
树及其性质
例11.1 图11.1所示是森林，他的每个分支（a）、（b）都是一棵树。
图11.1
11.1 树与生成树
树及其性质
定理11.1 设T是无向（n，m）图，则下述命题相互等价。
（1）T连通且无回路。
（2）T无回路且m=n-1。 （3）T连通且m=n-1。 （4）T无回路但新增加任何一条边（端点属于T）后有且仅有一个回路。 （5）T连通，但是删去任何一边后便不再连通。 （6）T的每一对结点之间有且仅有一条道路可通。
11.1 树与生成树
树及其性质
推论11.1 任 2 ( n t) ，由定理11.1中命题 证明：设（n,m）树T有t片叶，则 2
n
( n t ) ≥ t 2 n 2 t，即 t ≥ 2 （2），可得 2
例11.2 设 是一棵树，它有两个2度节点，一个3度节点，三个4度节点，求 的树 叶数。 解：设树 T 有 x 片树叶，则T