シュタイナー木（Steiner tree）とは、エッジの集合Eとノードの集合Vから成る無向グラフG=(V,E)において、Vの部分集合Tが与えられたとき、Tに含まれるノードすべてを含む木のことである。定義より、T=Vのとき、シュタイナー木は全域木となることは明らかである。