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

Пусть дано множество из n точек на плоскости. [[Остовное дерево]] представляет собой множество ребер, соединяющее все точки и не содержащее циклов. Если каждому ребру приписан вес при помощи некоторой метрики, связанной с расстоянием между инцидентными точками, то метрическим минимальным остовным деревом будет [[минимальное остовное дерево]] (МОД) с минимальной суммой этих весов. Если используется евклидово расстояние (<math>L_2 \;</math>) такое дерево называется евклидовым МОД; если расстояние по прямой (<math>L_1 \;</math>), то мы имеем дело с прямолинейным МОД.