4430
правок
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 15:31, 24 апреля 2016
, 24 апреля 2016→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Метрическое минимальное остовное дерево; [[прямолинейны…») |
Irina (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть дано множество из n точек на плоскости. Остовное дерево представляет собой множество ребер, соединяющее все точки и не содержащее циклов. Если каждому ребру приписан вес при помощи некоторой метрики, связанной с расстоянием между инцидентными точками, то метрическим минимальным остовным деревом будет минимальное остовное дерево (МОД) с минимальной суммой этих весов. Если используется евклидово расстояние ( | Пусть дано множество из n точек на плоскости. Остовное дерево представляет собой множество ребер, соединяющее все точки и не содержащее циклов. Если каждому ребру приписан вес при помощи некоторой метрики, связанной с расстоянием между инцидентными точками, то метрическим минимальным остовным деревом будет [[минимальное остовное дерево]] (МОД) с минимальной суммой этих весов. Если используется евклидово расстояние (<math>L_2 \;</math>) такое дерево называется евклидовым МОД; если расстояние по прямой (<math>L_1 \;</math>), то мы имеем дело с прямолинейным МОД. | ||
Минимальные остовные деревья на взвешенных графах хорошо изучены. Обычный подход к построению метрического МОД заключается в определении [[взвешенный граф|взвешенного графа]] на множестве точек и затем в построении остовного дерева для него. | |||
Определение 1. Пусть дано множество точек V на плоскости. Неориентированный граф G = (V, E) называется остовным графом, если он содержит минимальное остовное дерево для точек V на плоскости. | Подобно тому, как для [[поиск по лабиринту|поиска по лабиринту]] строится [[граф связей]] [4], для построения минимального остовного дерева можно определить остовный граф. | ||
'''Определение 1'''. Пусть дано множество точек V на плоскости. Неориентированный граф G = (V, E) называется [[остовный граф|остовным графом]], если он содержит минимальное остовное дерево для точек V на плоскости. | |||
| Строка 18: | Строка 20: | ||
Алгоритмы построения МОД обычно используют два свойства, позволяющие включать ребра в минимальное остовное дерево и исключать их. Первое свойство, известное как свойство разрезов, гласит, что ребро с минимальным весом, пересекающее любое разбиение множества вершин на два подмножества, принадлежит к МОД. Второе свойство называется свойством циклов и утверждает, что ребро любого цикла графа, имеющее наибольший вес, можно безопасно удалить. Поскольку эти два свойства сформулированы в контексте построения минимального остовного дерева, они оказываются полезными для остовного графа. | Алгоритмы построения МОД обычно используют два свойства, позволяющие включать ребра в минимальное остовное дерево и исключать их. Первое свойство, известное как свойство разрезов, гласит, что ребро с минимальным весом, пересекающее любое разбиение множества вершин на два подмножества, принадлежит к МОД. Второе свойство называется свойством циклов и утверждает, что ребро любого цикла графа, имеющее наибольший вес, можно безопасно удалить. Поскольку эти два свойства сформулированы в контексте построения минимального остовного дерева, они оказываются полезными для остовного графа. | ||
== Основные результаты == | == Основные результаты == | ||
