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

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

Версия от 17:26, 15 октября 2009

Евклидова задача Штейнера (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] точек. Получающееся наикратчайшее дерево называют наикратчайшим деревом Штейнера.

Литература

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