4551
правка
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 23:55, 28 апреля 2016
, 28 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Пусть дано множество из n точек на плоскости. [[Остовное дерево]] представляет собой множество ребер, соединяющее все точки и не содержащее циклов. Если каждому ребру приписан вес при помощи некоторой метрики, связанной с расстоянием между инцидентными точками, то ''метрическим минимальным остовным деревом'' будет [[минимальное остовное дерево]] (МОД) с минимальной суммой этих весов. Если используется евклидово расстояние <math>(L_2) \;</math>, такое дерево называется ''евклидовым МОД''; если расстояние по прямой <math>(L_1) \;</math>, то мы имеем дело с ''прямолинейным МОД''. | Пусть дано множество из n точек на плоскости. [[Остовное дерево]] представляет собой множество ребер, соединяющее все точки и не содержащее циклов. Если каждому ребру приписан вес при помощи некоторой метрики, связанной с расстоянием между инцидентными точками, то ''метрическим минимальным остовным деревом'' будет [[минимальное остовное дерево]] (МОД) с минимальной суммой этих весов. Если используется евклидово расстояние <math>(L_2) \;</math>, такое дерево называется ''евклидовым МОД''; если расстояние по прямой <math>(L_1) \;</math>, то мы имеем дело с ''прямолинейным МОД''. | ||
Минимальные остовные деревья на взвешенных графах хорошо изучены. Обычный подход к построению метрического МОД заключается в определении [[взвешенный граф|взвешенного графа]] на множестве точек и затем в построении на его основе остовного дерева. | |||
Минимальные остовные деревья на взвешенных графах хорошо изучены. Обычный подход к построению метрического МОД заключается в определении [[взвешенный граф|взвешенного графа]] на множестве точек и затем в построении остовного дерева | |||
