第九讲   最小生成树

            （教材：第九章   最小生成树）

 1(本页) 2 3 4 5 6

一.  树、生成树和最小生成树的概念

二.  在给定网络内求最小生成树的三种算法

三.  斯坦纳最小树的概念和一些基本性质

四.  求斯坦纳最小树的关键，通讯网络的最小生成树

一.  树、生成树和最小生成树的概念

1.  森、树、生成树等有关概念

    无圈图称为森，连通的无圈图称为树。若 和图 的边集和点集之间有关系：，则称 是图 的子图。若图 的子图 还满足 ，则称 是图 的生成子图。若 是图 的生成子图，且 本身是树，则称 为 的生成树。树是最简单但又十分重要的一类图。

一个图的生成树可能不只一个，例如下面的一个图：

它有许多生成树，例如下面每个树都是它的生成树：

2.  树的性质

    图 以 分别记点的数目和边的数目，设

关于树有如下一些的等价命题：

(1) 是一个树；

(2) 无圈，且 ；

(3) 连通，且 ；

(4) 无圈，但加一条新边即得唯一一个圈；

(5) 连通，但舍去一边就不连通；

(6) 中任意两点，有唯一链相连。

    上述每一个命题都可作为树的定义，它们对判断和构造树将极为方便。

    对图 的每一条边 赋以相应的实数权 ，得到一个网络，记为。设 是 的一个生成树，令 ，则 称为树 的权，中权最小的生成树称为 的最小生成树。

1(本页) 2 3 4 5 6