Минимальное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 29: | Строка 29: | ||
== Базовый жадный алгоритм == | == Базовый жадный алгоритм == | ||
До недавних пор все алгоритмы расчета MST можно было считать вариациями данного базового жадного алгоритма. Пусть T изначально состоит из n тривиальных деревьев, каждое из которых содержит одну вершину графа G. Повторить следующий шаг n - 1 раз. Выбрать любой элемент T | До недавних пор все алгоритмы расчета MST можно было считать вариациями данного базового жадного алгоритма. Пусть <math>\mathcal{T} \;</math> изначально состоит из n тривиальных деревьев, каждое из которых содержит одну вершину графа G. Повторить следующий шаг n - 1 раз. Выбрать любой элемент <math>T \in \mathcal{T} \;</math> и найти ребро с минимальным весом (u, v), у которого <math>u \in T \;</math>, а v принадлежит другому дереву, скажем, <math>T' \in \mathcal{T} \;</math>. Заменить T и T' в <math>\mathcal{T} \;</math> одним деревом <math>T \cup \{ (u, v) \} \cup T' \;</math>. После n - 1 итераций получаем <math>\mathcal{T} = \{ MST(G) \} \;</math>. Согласно свойству разрезов, каждое ребро, выбранное этим алгоритмом, содержится в MST. | ||
Моделирование MST-алгоритмов | Моделирование MST-алгоритмов | ||
Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому MST-алгоритмы естественно моделировать при помощи бинарных деревьев решений, где вершины дерева решений определяются при помощи сравнения весов ребер, а потомки вершины соответствуют возможным результатам сравнения. В такой модели дерева решений тривиальная нижняя граница времени исполнения оптимального MST-алгоритма представляет собой глубину оптимального дерева решений. | Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому MST-алгоритмы естественно моделировать при помощи [[бинарные деревья решений|бинарных деревьев решений]], где вершины дерева решений определяются при помощи сравнения весов ребер, а потомки вершины соответствуют возможным результатам сравнения. В такой модели дерева решений тривиальная нижняя граница времени исполнения оптимального MST-алгоритма представляет собой глубину оптимального дерева решений. | ||
== Основные результаты == | == Основные результаты == | ||