Минимальное остовное дерево
Минимальное остовное дерево (Minimum spanning tree, MST) взвешенного графа --- это такой его каркас, который обладает наименьшим суммарным весом ребер среди всех его каркасов.
Заметим, что граф может иметь несколько минимальных остовных деревьев.
Назовем подграф [math]\displaystyle{ T }[/math] графа [math]\displaystyle{ G }[/math] безопасным (Safe subgraph), если он является подграфом какого-то его минимального остовного дерева. Назовем ребро [math]\displaystyle{ ( u, v ) \notin T }[/math] безопасным (Safe edge), если при добавлении его в подграф [math]\displaystyle{ T }[/math] получившийся подграф также является безопасным, то есть подграфом какого-то минимального остовного дерева. Разрезом (Сut) связного неориентированного графа [math]\displaystyle{ G }[/math] будем называть граф, состоящий из двух компонент связности: [math]\displaystyle{ T }[/math] и подграфа, порожденного подмножеством вершин графа [math]\displaystyle{ G }[/math], не принадлежащих [math]\displaystyle{ T }[/math]. Ребро графа [math]\displaystyle{ G }[/math] пересекает (Сrosses) данный разрез, если при его добавлении к данному разрезу полученный граф становится связным.
Многие алгоритмы для поиска минимального остовного дерева опираются на следующее утверждение:
Лемма о безопасном ребре (Safe edge lemma). Рассмотрим произвольный разрез какого-либо подграфа минимального остова. Тогда ребро минимального веса, пересекающее этот разрез, является безопасным.
Другое название --- минимальный каркас, каркас наименьшего веса.
Cм. также
Литература
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ : Вильямс, 2-е издание, 2005
