Евклидова задача Штейнера: различия между версиями

'''Евклидова задача Штейнера''' (''[[Steiner's problem in Euclid plane]]'') - соединить  точки множества <math>P</math> на плоскости прямыми линиями так, чтобы минимизировать суммарную длину отрезков. Если не допускаются пересечения любых двух линий в точках вне заданного множества <math>P</math>, то задача сводится к одной из задач определения ''кратчайшей связывающей сети'' эквивалентного [[граф|графа]] на <math>|P|</math> [[вершина|вершинах]] с [[матрица весов|матрицей весов]], вычисленных как евклидово расстояние между точками множества <math>P</math>. Если допускается на плоскости введение дополнительных "искусственных" вершин (называемых точками Штейнера), то вес (длину) кратчайшей связывающей [[сеть|сети]] можно уменьшить соответствующим подбором

точек. Таким образом, для решения задачи Штейнера можно добавить в любых местах плоскости столько точек Штейнера, сколько необходимо для построения наикратчайшего дерева, стягивающего множество из <math>P</math> точек.

Получающееся наикратчайшее [[дерево]] называют ''[[наикратчайшее дерево Штейнера|наикратчайшим деревом Штейнера]]''.