Изменения

Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая следующий инвариант: пытаясь на каждом шаге достроить <tex>F</tex> можно достроить до некоторого MST. Начнем с того, что включим в <tex>F</tex> все вершины графа <tex>G</tex>. Теперь будем обходить множество <tex>E(G)</tex> в порядке неубывания веса весов ребер. Добавление очередного ребра Если очередное ребро <tex>e</tex> в соединяет вершины одной компоненты связности <tex>F</tex> может привести , то добавление его в остов приведет к возникновению цикла в одной из компонент этой компоненте связности <tex>F</tex>. В этом таком случае, очевидно, <tex>e</tex> не может быть включено в <tex>F</tex>. В противном случае Иначе <tex>e</tex> соединяет разные компоненты связности <tex>F</tex>, тогда существует [[Лемма о безопасном ребре#Необходимые определения|разрез]] <tex> \langle S, T \rangle </tex> [[Лемма о безопасном ребре#Необходимые определения|разрез]] такой, что одна из компонент связности составляет одну его часть, а оставшаяся часть графа — вторую. Тогда <tex>e</tex> и есть — минимальное ребро, пересекающее этот разрез. Значит, из [[Лемма о безопасном ребре#Лемма о безопасном ребре|леммы о безопасном ребре]] следует, что <tex>F+e</tex> можно продолжить до MSTявляется безопасным, поэтому добавим это ребро в <tex>F</tex>.На последнем шаге ребро соединит две оставшиеся компоненты связности, полученный подграф будет минимальным остовным деревом графа <tex>G<br/tex>.Для проверки возможности добавления ребра используется [[СНМ (реализация с помощью леса корневых деревьев) | система непересекающихся множеств]].

<tex> \mathtt{F}\ =\ \mathtt{F} \bigcup vu\</tex> '''return''' <tex> \mathtt{vuF}\</tex>

ОчевидноЛегко показать, что максимальное ребро в MST минимально. Пусть это не так, тогда рассмотрим разрез, который оно пересекает. В этом разрезе должно быть ребро с меньшим весом, иначе максимальное ребро было бы минимальным, но Обратное в таком общем случае минимальный остов не является минимальным, следовательно, максимальное ребро в минимальном остовном дереве минимально. Если же максимальное ребро в остовном дереве минимально, то такое дерево может не быть минимальнымневерно. Зато его можно найти быстрее чем Но MST, а конкретно из-за сортировки строится за <tex>O(E \log E)</tex>. Для этого с Однако из-за того, что необходимо минимизировать только максимальное ребро, а не сумму всех рёбер, можно предъявить алгоритм, решающий задачу за линейное время. С помощью [[Поиск_k-ой_порядковой_статистики_за_линейное_время | алгоритма поиска k-ой порядковой статистики]] найдем ребро-медиану за <tex>O(E)</tex> ребро-медиану и разделим множество ребер на два подмножестваравных по мощности так, так чтобы ребра в первом подмножестве ребра были меньше медианы, а не превосходили по весу ребер во втором больше. Проверим образуют ли ребра из первого подмножества остовграфа, просто запустив [[Использование_обхода_в_глубину_для_проверки_связности|обход в глубину]] за <tex>O(E)</tex>. * Если да, то удалим все ребра, которые больше медианы, и рекурсивно запустим алгоритм от первого подмножестванего. Иначе сожмем * В противном случае сконденсируем получившиеся несвязные компоненты связности в супервершины, и рассмотрим новый граф с такими этими вершинами и оставшимися ребрами, то есть ребрами, которые соединяют из второго подмножества.На последнем шаге останутся две компоненты связности старого графаи одно ребро в первом подмножестве — это максимальное ребро минимального веса. <br> На каждой итерации остается половина каждом шаге реберстановится в два раза меньше, следовательноа все операции выполняются за время пропорциональное количеству ребер на текущем шаге, тогда время работы алгоритма <tex>O(E+\frac{E}{2}+\frac{E}{4}+...+1)=O(E)</tex>.

Работа с [[СНМ (реализация с помощью леса корневых деревьев) | системой непересекающихся множеств]] займет <tex>O(E\alpha(V))</tex>, где <tex>\alpha</tex> — обратная функция Аккермана, которая не превосходит <tex>4 </tex> во всех практических приложениях и которую можно принять за константу.<br>

[[Категория: Остовные деревья ]][[Категория: Построение остовных деревьев]]