Изменения

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

==ИдеяОписание алгоритма==Будем последовательно строить подграф Алгоритм состоит из нескольких шагов: # Изначально каждая вершина графа <tex> G </tex >{{---}} тривиальное дерево, а ребра не принадлежат никакому дереву.# Для каждого дерева <tex> T </tex> найдем минимальное инцидентное ему ребро. Добавим все такие ребра.# Повторяем шаг <tex>F2 </tex> графа пока в графе не останется только одно дерево <tex>GT </tex> ("растущий лес").   Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, поддерживая следующий инвариант: на каждом шаге вес каждого ребра равен один. В <tex>FT</tex> могут быть добавлены все три ребра. Избежать эту проблему можно достроить до некоторого , например, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером. ==Доказательство корректности== {{Теорема|statement= Алгоритм Борувки строит '''MST'''. Начнем с того|proof=Очевидно, что включим в результате работы алгоритма получается дерево. Пусть <tex>FT </tex> все вершины {{---}} минимальное остовное дерево графа <tex>G</tex>, а <tex> T' </tex> {{---}} дерево полученное после работы алгоритма. Покажем, что <tex> T = T'</tex>. Теперь будем обходить множество  Предположим обратное <tex>EGT \neq T' </tex> в порядке увеличения веса ребер. Добавление очередного ребра Пусть ребро <tex>e' </tex> {{---}} первое добавленное ребро дерева <tex> T' </tex> , не принадлежащее дереву <tex> T </tex>. Пусть <tex> P </tex> {{---}} путь, соединяющий в дереве <tex>FT </tex> может привести к возникновению цикла в одной из компонент связности вершины ребра <tex>Fe' </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>. Получили противоречение. Следовательно <tex> T = T'</tex>.}} ==Реализация==У вершины есть поле <tex>\mathtt{comp}</tex> {{---}} компонента связности, которой принадлежит эта вершина. {| width = 100%|-| <font color=green>// <tex>G</tex> {{---}} исходный граф</font> <font color=green>// <tex>w</tex> {{---}} весовая функция</font> '''function''' <tex>\mathtt{boruvkaMST}():</tex> '''while''' <tex>T\mathtt{.size} < n - 1</tex> '''for''' <tex>k \in </tex> Component <font color = "green">// Component {{---}} множество компонент связности в <tex>FT</tex>. В противном случае Для </font> <tex>ew(\mathtt{minEdge}[k])=\infty</tex> соединяет разные <font color = "green">// каждой компоненты связности вес минимального ребра = <tex>F\infty</tex>.</font> <tex>\mathtt{findComp(}T\mathtt{)}</tex> <font color = "green">// Разбиваем граф <tex>T</tex> на компоненты связности обычным ''dfs''-ом.</font> '''for''' <tex>\mathtt{(u, тогда существует v)} \in E </tex> '''if''' <tex>\mathtt{u.comp} \neq \mathtt{v.comp}</tex> '''if''' <tex>w(\mathtt{minEdge}[\mathtt{u.comp}]) > w(u,v)</tex> <tex>\mathtt{minEdge}[Лемма о безопасном ребре#Необходимые определения|разрез\mathtt{u.comp}]= (u,v)</tex> '''if''' <tex>w(\mathtt{minEdge}[\mathtt{v.comp}] ) > w(u,v)</tex> <tex> \langle Smathtt{minEdge}[\mathtt{v.comp}] = (u, v)</tex> '''for''' <tex>k \in </tex> Component <tex>T \rangle 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>|На первой итерации внешнего цикла для каждой компоненты были добавлены минимальные сопряженные ребра. Тогда Некоторые ребра добавлены несколько раз (<texdpi = 120>eAD</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>F+e(i - 1) </tex> можно продолжить до MST-й итерации. Значит, поэтому добавим это ребро на каждой итерации число компонент уменьшается как минимум в <tex>F2 </tex>раза.Тогда внешний цикл повторяется <tex>O(\log{V})<br/tex>Несложно понятьраз, так как количество компонент изначально равно количеству вершин. Что же касается внутреннего цикла, что после выполнения такой процедуры получится остовное деревото он выполняется за <tex>O(E)</tex>, при этом его минимальность вытекает из леммы о безопасном ребрегде <tex>E</tex> {{---}} количество рёбер в исходном графе. Следовательно конечное время работы алгоритма <tex>O(E\log{V})</tex>. ==См. также==* [[Алгоритм Прима]]* [[Алгоритм Краскала]]* [[Алгоритм двух китайцев]] == Источники информации ==* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2006 Визуализатор алгоритма]* [http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]* [[wikipedia:ru:Алгоритм Борувки|Алгоритм Борувки— Википедия]] [[Категория: Алгоритмы и структуры данных]][[Категория: Остовные деревья ]]