Евклидова задача Штейнера

Steiner's problem in Euclid plane

соединить точки множества P на плоскости прямыми линиями так, чтобы минимизировать суммарную длину отрезков. Если не допускаются пересечения любых двух линий в точках вне заданного множества P, то задача сводится к одной из задач определения кратчайшей связывающей сети эквивалентного графа на  вершинах с матрицей весов, вычисленных как евклидово расстояние между точками множества P. Если допускается на плоскости введение дополнительных "искусственных" вершин (называемых точками Штейнера), то вес (длину) кратчайшей связывающей сети можно уменьшить соответствующим подбором точек. Таким образом, для решения задачи Штейнера можно добавить в любых местах плоскости столько точек Штейнера, сколько необходимо для построения наикратчайшего дерева, стягивающего множество из P точек. Получающееся наикратчайшее дерево называют наикратчайшим деревом Штейнера.

Литература: [Кристофидес] .