Алгоритм Борувки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
(Доказательство корректности)
Строка 27: Строка 27:
 
Докажем это по индукции.
 
Докажем это по индукции.
  
База: <tex>n<\tex> = 1(Лемма 1).
+
База: <tex>n</tex> = 1(Лемма 1).
Переход: Пусть лес <tex>T<\tex> получившийся после <tex>n<\tex> итераций алгоритма можно достроить до MST. Докажем что после <tex>n<\tex>+1-й итерации получившийся лес <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'<\tex> - <tex>T<\tex>. На этом цикле имеется ребро большее по весу чем ребро <tex>x<\tex>, иначе компонента для которой <tex>x<\tex> было минимальным ни с кем больше ни связана.Следовательно исходя из критерия тарьяна мы получили противоречие.
+
Переход: Пусть лес <tex>T</tex> получившийся после <tex>n<\tex> итераций алгоритма можно достроить до MST. Докажем что после <tex>n</tex>+1-й итерации получившийся лес <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'</tex> - <tex>T</tex>. На этом цикле имеется ребро большее по весу чем ребро <tex>x</tex>, иначе компонента для которой <tex>x<\tex> было минимальным ни с кем больше ни связана.Следовательно исходя из критерия тарьяна мы получили противоречие.
 
   
 
   
 
}}
 
}}

Версия 21:13, 15 декабря 2012

Алгоритм Борувки — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе. Впервые был опубликован в 1926 году Отакаром Борувкой.

Описание алгоритма

Пусть [math]T[/math] подграф графа [math]G[/math]. Изначально [math]T[/math] содердит все вершины из [math]G[/math] и не содержит ребер.

Будем добавлять в [math]T[/math] ребра следующим образом:

Пока [math]T[/math] не является деревом

  1. Для каждой компоненты связанности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не принадлежащей данной компоненте.
  2. Добавим в [math]T[/math] все ребра, которые хотя бы для одной компоненты оказались минимальными.

Получившийся граф [math]T[/math] является минимальным остовным деревом графа [math]G[/math].

Доказательство корректности

Лемма:
Рассмотрим связный неориентированный взвешенный граф [math] G = (V, E) [/math] с весовой функцией [math]w : E \to \mathbb{R}[/math]. Тогда после первой итерации алгоритма Борувки получившийся подграф можно достроить до MST.
Доказательство:
[math]\triangleright[/math]
Предположим обратное: пусть любое MST графа [math]G[/math] не содержит [math]T[/math]. Рассмотрим какое-нибудь MST.Тогда существует ребро x из [math]T[/math] такое что [math]x[/math] не принадлежит MST. Добавив ребро [math]x[/math] в MST получаем цикл в котором [math]x[/math] не максимально т.к оно было минимальным. Тогда, исходя из критерия тарьяна, получаем противоречие.
[math]\triangleleft[/math]

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

Докажем это по индукции.

База: [math]n[/math] = 1(Лемма 1). Переход: Пусть лес [math]T[/math] получившийся после [math]n\lt \tex\gt итераций алгоритма можно достроить до MST. Докажем что после \lt tex\gt n[/math]+1-й итерации получившийся лес [math]T'[/math] можно достроить до MST.Предположим обратное: [math]T'[/math] нельзя достроить до MST. Тогда существует [math]F[/math] = MST графа [math]G[/math], содержащее [math]T[/math] и не содержащее [math]T'[/math]. Тогда рассмотрим цикл получающийся добавлением в [math]F[/math] какого-нибудь ребра [math]x[/math] из [math]T'[/math] - [math]T[/math]. На этом цикле имеется ребро большее по весу чем ребро [math]x[/math], иначе компонента для которой [math]x\lt \tex\gt было минимальным ни с кем больше ни связана.Следовательно исходя из критерия тарьяна мы получили противоречие. }} ==Реализация== {| width = 100% |- | Graph Boruvka(Graph G) while T.size \lt n init() // у вершины есть поле comp(компонента которой принадлежит вершина) findComp(T) // разбиваеv граф T на компоненты связынности обычным dfs-ом for uv \lt tex\gt \in[/math] E

               if u.comp != v.comp
                   if minEdge[u.comp].w < uv.w
                       minEdge[u.comp] = uv
                   if minEdge[v.comp].w < uv.w
                       minEdge[v.comp] = uv)
           for k [math]\in[/math] Comp                                       // Comp — множество компонент связанности в T
                   T.addEdge(minEdge[k])
      return T;     

|}

Асимптотика

Время работы внутри главного цикла будет равно [math]O(E + V)[/math].

Количество итераций которое выполняется главным циклом равно [math]O(\log{V})[/math] так как на каждой итерации количество компонент связанности уменьшается в 2 раза (изначально количество компонент равно [math]|V|[/math], в итоге должна стать одна компонента).

Общее время работы алгоритма получается [math]O(E\log{V})[/math]

Литература

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

См. также