Изменения

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

Будем добавлять в <tex>T</tex> ребра следующим образомАлгоритм состоит из нескольких шагов:

Пока # Изначально каждая вершина графа <tex>TG </tex> {{---}} тривиальное дерево, а ребра не является деревомпринадлежат никакому дереву.# Для каждой компоненты связности находим каждого дерева <tex> T </tex> найдем минимальное по весу инцидентное ему ребро, которое связывает вершину из данной компоненты с вершиной, не принадлежащей данной компоненте. Добавим все такие ребра.# Добавим Повторяем шаг <tex> 2 </tex> пока в графе не останется только одно дерево <tex>T</tex> все ребра, которые хотя бы для одной компоненты связности оказались минимальными.

Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В <tex>T</tex> могут быть добавлены все три ребра. Избежать эту проблему можно, например, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером. Доказательство будем проводить, считая веса всех ребер различными.

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

Докажем это по индукцииПредположим обратное <tex> T \neq T' </tex>. Пусть ребро <tex> e' </tex> {{---}} первое добавленное ребро дерева <tex> T' </tex>, не принадлежащее дереву <tex> T </tex>. Пусть <tex> P </tex> {{---}} путь, соединяющий в дереве <tex> T </tex> вершины ребра <tex> e' </tex>.

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

У вершины есть поле <tex>\mathtt{comp — }</tex> {{---}} компонента связности, которой принадлежит эта вершина.

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> '''for''' <tex>k \in </tex> Component <font color = "green">// пока Component {{---}} множество компонент связности в <tex>T не дерево</tex>. Для </font> init <tex>w(\mathtt{minEdge}[k]) =\infty</tex> <font color = "green">// для каждой компоненты связности вес минимального ребра равен бесконечности= <tex>\infty</tex>.</font> <tex>\mathtt{findComp(}T\mathtt{) }</tex> <font color = "green">// разбиваеv Разбиваем граф <tex>T </tex> на компоненты связности обычным ''dfs''-ом.</font> '''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> <font color = "green">// добавляем Добавляем ребро , если его не было в <tex>T</tex></font> '''return ''' <tex>T; </tex> |} ==Пример=={| class = "wikitable"! Изображение !! Компоненты связности !! Описание|-align="center"|[[Файл:Boruvka_1.png|250px]]| <tex>\{A\}</tex><br/><tex>\{B\}</tex><br/><tex>\{C\}</tex><br/><tex>\{D\}</tex><br/><tex>\{E\}</tex><br/><tex>\{F\}</tex><br/><tex>\{G\}</tex>|Начальный граф <tex>G</tex>. Каждая вершина является компонентой (синие окружности).|-align="center"|[[Файл:Boruvka_2.png|250px]]| <tex>\{ABDF\}</tex><br/><tex>\{CEG\}</tex>|На первой итерации внешнего цикла для каждой компоненты были добавлены минимальные сопряженные ребра. Некоторые ребра добавлены несколько раз (<tex dpi = 120>AD</tex> и <tex dpi = 120>CE</tex>). Осталось две компоненты.|-align="center"|[[Файл:Boruvka_3.png|250px]]| <tex>\{ABCDEFG\}</tex>|На последней итерации внешнего цикла было добавлено минимальное ребро, соединяющее две оставшиеся компоненты (ребро <tex dpi = 120>BE</tex>). Осталась одна компонента. Минимальное остовное дерево графа <tex dpi = 120>G</tex> построено. |-

Время работы внутри главного На <tex> i </tex>-ой итерации внешнего цикла будет равно каждая компонента состоит как минимум из двух компонент из <tex>O(E + Vi - 1)</tex>-й итерации. Количество итерацийЗначит, которое выполняется главным циклом равно на каждой итерации число компонент уменьшается как минимум в <tex> 2 </tex> раза. Тогда внешний цикл повторяется <tex>O(\log{V})</tex> раз, так как на каждой итерации количество компонент связности уменьшается в 2 раза (изначально количество компонент равно количеству вершин. Что же касается внутреннего цикла, то он выполняется за <tex>|V|O(E)</tex>, где <tex>E</tex> {{---}} количество рёбер в итоге должна стать одна компонента)исходном графе. Общее Следовательно конечное время работы алгоритма получается <tex>O(E\log{V})</tex>. == Ссылки ==*[http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]*[http://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 Алгоритм Борувки— Википедия]