什么是斯坦纳树问题

这里只简要描述一下经典的最小斯坦纳树问题 (Minimum Steiner Tree)：

给定一个无向赋权连通图G=(V, E)，边的权值非负，顶点集D是V的一个非空子集。要求：找一个包含D中所有节点的树 (这颗树可以包含D之外的节点)，使得树的边权和最小。

可见，该问题是最小生成树问题的推广。当D=V时，就退化成了最小生成树问题。它被证明是NP-难的。

斯坦纳树问题的定义随着历史的发展在不断的扩展和推广。 瑞士数学家斯坦纳（J.Steiner，1796—1863）将问题推广成：在平面上求一点，使得这一点到平面 上给定的若干个点（称为所与点）的距离之和最小。这可以看作斯坦纳树问题的雏形。 考虑到点的其他相关因素，加入了权重的表示。形成的推广定义，德国的两位数学家韦伯(H.Weber，1842—1913)和维斯菲尔德（E.Wieszfeld）分别在1909年和1937年将该问题作为工 厂选址问题提出来：某地有给定的若干个仓库，每个仓库的其他相关因素可以换算成一个权重表示，求一建造工厂的合适地点，使工厂到每个仓库的距离与权重乘积 的总和最小，则这个工厂的地址是最经济、便利的。 库朗（R.Courant）和罗宾斯（H.Robbins）提出第一个定义中，斯坦纳对此问题的推广是一种平庸的推广。要得到一个有意义的推广，需要考虑的不是引进一个点，而应是引进若干个点，使引进的点与原来给定的点 连成的网络最小。他们将此新问题称为斯坦纳树问题。给出的定义为：

假设原来已经给定了n个点，库朗等指出需要引进的点数至多为n-2，此种点称为斯坦纳点。过每一斯坦纳点，至多有三条边通过。若为三条边，则它们两两交成 120°角；若为两条边，则此斯坦纳点必为某一已给定的点，且此两条边交成的角必大于或等于120°。其中最小的网络称为已给定点的集合的最小斯坦纳树， 记作SMT。若此SMT的斯坦纳点中有等于给定点的点，则称此SMT为退化的，此给定点称为退化点。

假设原来已经给定了n个点，库朗等指出需要引进的点数至多为n 2，此种点称为斯坦纳点。过每一斯坦纳点，至多有三条边通过。若为三条边，则它们两两交成120°角；若为两条边，则此斯坦纳点必为某一已给定的点，且此两条边交成的角必大于或等于120°。其中最小的网络称为已给定点的集合的最小斯坦纳树，记作SMT。若此SMT的斯坦纳点中有等于给定点的点，则称此SMT为退化的，此给定点称为退化点。

---