Изменения

<b>Алгоритм Борувки</b> (англ. ''Borůvka's algorithm'') — алгоритм поиска минимального остовного дерева (англ. ''minimum spanning tree, MST'') во взвешенном неориентированном связном графе.

Пусть # Построим граф <tex>T</tex> подграф графа <tex>G</tex>. Изначально <tex>T</tex> содержит все вершины из <tex>G</tex> и не содержит ребер(каждая вершина в графе <tex>T</tex> {{---}} отдельная компонента связности). # Будем добавлять в <tex>T</tex> ребра следующим образом:  Пока , пока <tex>T</tex> не является деревом# * Для каждой компоненты связности находим минимальное по весу ребро, которое связывает вершину из данной компоненты эту компоненту с вершиной, не принадлежащей данной компонентедругой. # * Добавим в <tex>T</tex> все ребра, которые хотя бы для одной компоненты связности оказались минимальныминайденные рёбра. # Получившийся граф <tex>T</tex> является минимальным остовным деревом графа <tex>G</tex>.

Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до ''MST''.|proof=Предположим обратное: пусть любое ''MST '' графа <tex>G</tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь ''MST''. Тогда существует ребро <tex>x</tex> из <tex>T</tex> такое что <tex>x</tex> не принадлежит ''MST''. Добавив ребро <tex>x</tex> в ''MST'', получаем цикл в котором <tex>x</tex> не максимально, т.к оно было минимальным. Тогда, исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.

|statement=Алгоритм Борувки строит ''MST''.|proof=Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф <tex>T</tex> можно достроить до ''MST''.

* '''База: . ''' <tex>n = 1</tex>([[#lemma1|Лемма]]).* '''Переход: . ''' Пусть лес <tex>T</tex>, получившийся после <tex>n</tex> итераций алгоритма, можно достроить до ''MST''. Докажем, что после <tex>n+1</tex> итерации получившийся лес <tex>T'</tex> можно достроить до ''MST''.Предположим обратное: <tex>T'</tex> нельзя достроить до ''MST''. Тогда существует <tex>F</tex> = ''MST '' графа <tex>G</tex>, содержащее <tex>T</tex> и не содержащее <tex>T'</tex>. Тогда рассмотрим цикл, получающийся добавлением в <tex>F</tex> какого-нибудь ребра <tex>x</tex> из <tex>T' {{-- -}} T</tex>. На этом цикле имеется ребро, большее по весу чем ребро <tex>x</tex>, иначе компонента для которой <tex>x</tex> является минимальным ребром ни с кем больше ни связана.Исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие. '''Получаем . ''' <tex>T'</tex> можно достроить до ''MST''. Следовательно предположение индукции верно.

Graph Boruvka<font color=green>// <tex>G</tex> {{---}} исходный граф</font> <font color=green>// <tex>w</tex> {{---}} весовая функция</font> '''function''' <tex>\mathtt{boruvkaMST}(Graph G):</tex> '''while ''' <tex>T\mathtt{.size } < n - 1 </tex> init'''for''' <tex>k \in </tex> Component // Component — множество компонент связности в <tex>T</tex> <tex>w(\mathtt{minEdge}[k]) =\infty</tex> // для каждой компоненты связности вес минимального ребра = Inf<tex>\infty</tex> <tex>\mathtt{findComp(}T\mathtt{) }</tex> / разбиваеv / разбиваем граф <tex>T </tex> на компоненты связности обычным ''dfs''-ом '''for uv ''' <tex>\mathtt{(u,v)} \in E </tex> E '''if ''' <tex>\mathtt{u.comp != } \neq \mathtt{v.comp}</tex> '''if ''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}].) < w (u,v)< uv.w/tex> <tex>\mathtt{minEdge}[\mathtt{u.comp}] = uv(u,v)</tex> '''if ''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}].) < w (u,v)< uv.w/tex> <tex>\mathtt{minEdge}[\mathtt{v.comp}] = uv(u,v)</tex> '''for k ''' <tex>k \in</tex> Component // Component — множество компонент связности в T <tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k]) </tex> // добавляем ребро если его не было в <tex>T</tex> '''return ''' <tex>T; </tex>

! Изображение !! Множество рёбер Компоненты связности !! Описание

|[[Файл:Mst_bor_1Step_0.png|200px]]

|Переберём все вершины и отметим для каждой вершины инцидентное ей ребро минимального веса.{| width="100%"|Вершина || '''a''' || '''b''' || '''c''' || '''d''' || '''e'''Начальный граф <tex>T</tex>

|Ребро минимального веса [[Файл:Step_1.png|200px]]| <center>'''aea''' || '''abb''' || '''cdc''' || '''cdd''' || '''aee''' </center>|}Распределим вершины по компонентам.

|[[Файл:Mst_bor_21step_2.png|200px]]||Объединим каждую полученную компоненту связности в одну вершину.<br/center>Полученные вершины ''abe'a' и ''cd'' соединяют рёбра 'b''bc' '', 'c''ac' '', 'd''ec''' и 'e''ed'''.<br/center>Выберем среди них ребро с минимальным весом - '''ac''' и положим его |Пометим минимальные пути между полученными вершинамикомпонентами.<br/>

|[[Файл:Mst_bor_31step_3.png|200px]]<br/>[[Файл:Mst_bor_4.png|200px]]|<center>'''ae''' '''abbae''' '''cd'''</center>|Повторим алгоритм борувки на полученном графе, в результате чего он будет сжат Объединим соединившиеся компоненты в одну вершину.и добавим минимальные рёбра к графу <tex>T</tex><br/>

|<center>[[Файл:Mst_bor_51step_4.png|80px200px]]</center>|<center>'''ae''' '''abbae''' '''cd''' '''ac'''</center>|Граф сжат в одну вершину.<br/>Теперь нужно заменить множество рёбер заданного графа на полученное в алгоритмеПометим минимальные пути между компонентами.

|[[Файл:Mst_bor_61step_5.png|200px]]|<center>'''baecd'''</center>|Полученный граф - минимальное остовное дерево заданного графа.Объединим соединившиеся компоненты в одну и добавим минимальные рёбра к графу <tex>T</tex><br/>

Время работы внутри главного цикла будет равно <tex>O(E + V)Внешний цикл повторяется </tex>. Количество итераций, которое выполняется главным циклом равно <tex>O(\log{V})</tex> раз, так как на каждой итерации количество компонент связности каждый раз уменьшается в 2 раза (двое и изначально количество компонент равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за <tex>|V|E</tex>, где <tex>E</tex> {{---}} количество рёбер в итоге должна стать одна компонента)исходном графе. Общее Следовательно конечное время работы алгоритма получается <tex>O(E\log{V})</tex>.

* [http[wikipedia://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8 :Алгоритм Борувки|Алгоритм Борувки— Википедия]]