對於圖 
的頂點子集，斯坦納樹是包含所有頂點的最小權重連通子圖 
。它始終是一棵樹。斯坦納樹具有實際應用，例如，在確定連線若干個點所需的最短電線總長度時（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.tw/SteinerTree.html