Изменения

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

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

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

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

'''База. ''' Покажем, что <tex>n T = 1T'</tex> (см. [[#lemma1|Лемму]]).

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

Понятно, что в момент, когда ребро <tex> e'</tex> добавляли, какое-то ребро <tex> P </tex> (назовем его <tex> e </tex>) не было добавлено. По алгоритму <tex> w(e) \geqslant w(e''Получаем) </tex>. Однако тогда <tex> T - e + e''' </tex> {{---}} остовное дерево веса не превышающего вес дерева <tex>T'</tex> можно достроить до ''MST''. Получили противоречение. Следовательно предположение индукции верно<tex> T = T'</tex>.

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

'''for''' <tex>k \in </tex> Component <font color = "green">// Component — {{---}} множество компонент связности в <tex>T</tex>. Для </font> <tex>w(\mathtt{minEdge}[k])=\infty</tex> <font color = "green">// для каждой компоненты связности вес минимального ребра = <tex>\infty</tex>.</font> <tex>\mathtt{findComp(}T\mathtt{)}</tex> <font color = "green">// разбиваем Разбиваем граф <tex>T</tex> на компоненты связности обычным ''dfs''-ом.</font>

'''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) < > w(u,v)</tex>

'''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}]) < > w(u,v)</tex>

<tex>T\mathtt{.addEdge}(\mathtt{minEdge}[k])</tex> <font color = "green">// добавляем Добавляем ребро , если его не было в <tex>T</tex></font>

|-align="center"

| <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>

|-align="center"

| <tex>\{ABDF\}</tex><br/><tex>\{CEG\}</tex>

|-align="center"

| <tex>\{ABCDEFG\}</tex>

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