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