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

Перейти к навигации Перейти к поиску
Строка 32: Строка 32:




Моделирование MST-алгоритмов
'''Моделирование MST-алгоритмов'''


Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому MST-алгоритмы естественно моделировать при помощи [[бинарные деревья решений|бинарных деревьев решений]], где вершины дерева решений определяются при помощи сравнения весов ребер, а потомки вершины соответствуют возможным результатам сравнения. В такой модели дерева решений тривиальная нижняя граница '''времени''' исполнения оптимального MST-алгоритма представляет собой '''глубину''' оптимального дерева решений.
Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому MST-алгоритмы естественно моделировать при помощи [[бинарные деревья решений|бинарных деревьев решений]], где вершины дерева решений определяются при помощи сравнения весов ребер, а потомки вершины соответствуют возможным результатам сравнения. В такой модели дерева решений тривиальная нижняя граница '''времени''' исполнения оптимального MST-алгоритма представляет собой '''глубину''' оптимального дерева решений.