第九讲 最小生成树
（教材：第九章 最小生成树）
斯坦纳最小树问题的例：通讯网络的最小生成树
利用前面介绍的知识和方法，我们来研究求解一个斯坦纳最小树问题：通讯网络的最小生成树（见教材
关于问题的完整叙述）。
注意：这是一个矩形距离的斯坦纳最小树问题。它与欧氏距离的斯坦纳最小树问题有重要区别：
(1) 平面上两点
间的欧氏距离为
，而其矩形距离为 
；
(2) 欧氏空间中两点的最短连线是唯一确定的；而按矩形距离，连接两点的最短线一般不是唯一的；
(3) 在本问题中，按欧氏距离计算，可能的斯坦纳点有无限多个，即一个凸多边形内所有的点都可能是斯坦纳点。而这里按问题中的设定，只有格子点才有可能是斯坦纳点。因而可能的斯坦纳点仅有限多个，即该凸多边形内格子点。因此这也意味着我们可以利用穷举法来求解（这就是下面的算法一－－精确法）。
(4) 在矩形距离下，两条边的夹角不再有意义。
教材中结合本问题介绍矩形距离下求斯坦纳最小树的三种算法。
(1) 精确法
(2) 迭代算法
(3) 近似算法
若要考虑通讯站的费用，则只需对前面的两种算法
(算法二、算法三) 稍加修正。在计算树的权时，不仅考虑它的边的权，还需加上点的权，取这两个值和的最小者为最小生成树，由此求得第二部分的解如教科书
中图 9.9。本课程没有详细叙述求解过程，有兴趣的同学可以自己演算。
通讯网问题的第三部分－－推广该问题，可以多方面进行。例如，可以考虑点集
不是平面点集，而由 
维空间的 
个点组成，等等。有兴趣的通讯可以参考下列论文：F.K.Hwang，D.S.Richards and
P.Winter，The Steiner Tree Problem，Annals of Discrete Mathematics，Vol.53。
作业简答