对于图 
的顶点子集，斯坦纳树是包含所有顶点的最小权重连通子图 
。它始终是一棵树。斯坦纳树具有实际应用，例如，在确定连接若干个点所需的最短电线总长度时（Hoffman 1998，第164-165页）。
确定斯坦纳树是 NP 完全问题，甚至难以近似。存在由 Robins 和 Zelikovski (2000) 提出的 1.55 近似算法，但已知在 95/94 内的近似是 NP 困难的 (Chlebik 和 Chlebikova 2002)。
斯坦纳树
另请参阅
普拉托问题, 树使用 探索
参考文献
Chlebik, M. and J.Chlebikova, J. "Approximation Hardness of the Steiner Tree Problem on Graphs." Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT). Springer-Verlag, pp. 170-179, 2002.Chopra, S. and Rao, M. R. "The Steiner Tree Problem 1: Formulations, Compositions, and Extension of Facets." Mathematical Programming 64, 209-229, 1994.Chopra, S. and Rao, M. R. "The Steiner Tree Problem 2: Properties and Classes of Facets." Mathematical Programming 64, 231-246, 1994.Chung, F. R. K.; Gardner, M.; and Graham, R. L. "Steiner Trees on a Checkerboard." Math. Mag. 62, 83-96, 1989.Cieslik, D. Steiner Minimal Trees. Amsterdam: Kluwer, 1998.Du, D.-Z.; Smith, J. M.; and Rubinstein, J. H. Advances in Steiner Trees. Dordrecht, Netherlands: Kluwer, 2000.Ganley, J. "The Steiner Tree Page." http://ganley.org/steiner/.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, 1998.Hwang, F.; Richards, D.; and Winter, P. The Steiner Tree Problem. Amsterdam, Netherlands: North-Holland, 1992.Ivanov, A. O. and Tuzhilin, A. A. Minimal Networks: The Steiner Problem and Its Generalizations. Boca Raton, FL: CRC Press, 1994.Robins, G. and Zelikovski, A. "Improved Steiner Tree Approximation in Graphs." In Proc. 11th ACM-SIAM Symposium on Discrete Algorithms. pp. 770-779, 2000.Skiena, S. S. "Steiner Tree." §8.5.10 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 339-342, 1997.在 中被引用
斯坦纳树请这样引用
韦斯坦因，埃里克·W. "斯坦纳树。" 来自 Web 资源。 https://mathworld.net.cn/SteinerTree.html