4430
правок
Минимальное остовное дерево: различия между версиями
Материал из WEGA
Минимальное остовное дерево (посмотреть исходный код)
Версия от 19:23, 22 декабря 2015
, 22 декабря 2015→Базовый жадный алгоритм
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 33: | Строка 33: | ||
Моделирование MST-алгоритмов | Моделирование MST-алгоритмов | ||
Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому MST-алгоритмы естественно моделировать при помощи [[бинарные деревья решений|бинарных деревьев решений]], где вершины дерева решений определяются при помощи сравнения весов ребер, а потомки вершины соответствуют возможным результатам сравнения. В такой модели дерева решений тривиальная нижняя граница '''времени''' исполнения оптимального MST-алгоритма представляет собой '''глубину''' оптимального дерева решений. | Еще одно следствие свойств разрезов и циклов заключается в том, что множество минимальных остовных деревьев графа определяется исключительно по относительному порядку весов ребер – их конкретные численные значения не важны. Поэтому MST-алгоритмы естественно моделировать при помощи [[бинарные деревья решений|бинарных деревьев решений]], где вершины дерева решений определяются при помощи сравнения весов ребер, а потомки вершины соответствуют возможным результатам сравнения. В такой модели дерева решений тривиальная нижняя граница '''времени''' исполнения оптимального MST-алгоритма представляет собой '''глубину''' оптимального дерева решений. | ||
