4551
правка
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 23:54, 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>, то мы имеем дело с ''прямолинейным МОД''. | ||
