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

Материал из WikiGrapp
Версия от 14:47, 15 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Евклидова задача Штейнера''' (''Steiner's problem in Euclid plane'') - соединить точки множ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

Литература

[Кристофидес]