Изменения

<b>Алгоритм Краскала</b>(англ. ''Kruskal's algorithm'') — алгоритм поиска [[Лемма о безопасном ребре#Необходимые определения | минимального остовного дерева]] (англ. ''minimum spanning tree'', ''MST'') во взвешенном [[Основные определения теории графов#Неориентированные графы | неориентированном связном графе]].

Будем последовательно строить подграф <tex>F</tex> графа <tex>G</tex> ("растущий лес"), поддерживая следующий инвариант: пытаясь на каждом шаге достроить <tex>F</tex> можно достроить до некоторого MST. Начнем с того, что включим в <tex>F</tex> все вершины графа <tex>G</tex>. Теперь будем обходить множество <tex>EGE(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>.На последнем шаге ребро соединит две оставшиеся компоненты связности, полученный подграф будет минимальным остовным деревом графа <brtex>G</tex>.Несложно понять, что после выполнения такой процедуры получится остовное дерево, при этом его минимальность вытекает из леммы о безопасном ребреДля проверки возможности добавления ребра используется [[СНМ (реализация с помощью леса корневых деревьев) | система непересекающихся множеств]].

<tex> \mathtt{F}\ =\ \varnothing </tex> '''for''' <tex>v \in leftarrow V(G)</tex> <tex>\mathtt{makeSet}(v)\</tex>

'''for''' <tex>vu \in E(G)</tex> в отсортированном порядке '''if''' <tex>\mathtt{findSet}(v</tex> и <tex>u)\ \ne \mathtt{findSet}(v)</tex> в разных компонентах связности <tex>F</tex> <tex> \mathtt{F}\ =\ \mathtt{F} \bigcup \mathtt{vu}\</tex> '''return''' <tex>\mathtt{UniteF}(v, u)\ </tex>

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

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

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