第九讲 最小生成树
（教材：第九章 最小生成树）
2. 斯坦纳最小树和最小生成树
添加斯坦纳点的斯坦纳最小树，往往比不添加斯坦纳点的最小生成树的长度更短些。例如在教材中图
9.4(a) (见下图) 所示的一个简例中，不添加斯坦纳点的最小生成树的长度是
，而添加斯坦纳点后的斯坦纳最小树的长度为3，显然添加斯坦纳点后的长度要短。
求斯坦纳最小树后得到的是欧氏平面上连通给定点集中所有点的最短距离，而求最小生成树则是在由给定的点集、边集和权组成的网络中求权最小的生成树，两者一般是不同的。后者所得的并不一定是欧氏平面上连通给定点集中所有点的最短距离，因为受到给定网络中边集的限制。
图9.4(a)中点
是边长为
的等边三角形的三个顶点，而图(b)中的
是一个矩形的四个顶点，其中
间的边长为
，而
间的为
。
3. SRT 的一些基本性质
教材中不加证明地列举了一些SRT的基本性质。
四. 求斯坦纳最小树的关键，通讯网络的最小生成树
求斯坦纳最小树的关键是要确定点集
，即斯坦纳点的个数和位置。一旦知道了 
的位置，我们就可以构作以 
为顶点的完全图 
（即每两点都有边连接的图）；然后按各点对之间的欧氏距离定义各边的长度；再求得所得网络的最小生成树，这就是
SRT。
但是确定斯坦纳点的个数和位置的问题，是一个相当复杂的问题。已经证明，对一般的斯坦纳问题，人们不能期望找到多项式次数算法来求解。因此，当前人们正从下列三方面考虑一般的斯坦纳问题：
(1) 寻找这一问题的组合性质和遍数算法。
(2) 研究斯坦纳问题的各种近似算法。
(3) 研究各种特殊情况的斯坦纳问题的算法。