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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
(Доказательство корректности)
Строка 13: Строка 13:
  
 
==Доказательство корректности==
 
==Доказательство корректности==
{{Лемма
+
{{Лемма 1
 
|id=lemma1
 
|id=lemma1
 
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E)  </tex> с весовой функцией <tex>w : E \to \mathbb{R}</tex>.
 
|statement=Рассмотрим связный неориентированный взвешенный граф <tex> G = (V, E)  </tex> с весовой функцией <tex>w : E \to \mathbb{R}</tex>.
 
Тогда после первой итерации алгоритма Борувки получившийся подграф можно достроить до MST.
 
Тогда после первой итерации алгоритма Борувки получившийся подграф можно достроить до MST.
 
|proof=Предположим обратное: пусть любое MST графа <tex>G</tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь MST.Тогда существует ребро x из <tex>T</tex> такое что <tex>x</tex> не принадлежит MST. Добавив ребро <tex>x</tex> в MST получаем цикл в котором <tex>x</tex> не максимально т.к оно было минимальным. Тогда, исходя из критерия тарьяна, получаем противоречие.
 
|proof=Предположим обратное: пусть любое MST графа <tex>G</tex> не содержит <tex>T</tex>. Рассмотрим какое-нибудь MST.Тогда существует ребро x из <tex>T</tex> такое что <tex>x</tex> не принадлежит MST. Добавив ребро <tex>x</tex> в MST получаем цикл в котором <tex>x</tex> не максимально т.к оно было минимальным. Тогда, исходя из критерия тарьяна, получаем противоречие.
 +
}}
 +
 +
{{Теорема
 +
|id=th1.
 +
|statement=Алгоритм Борувки строит MST.
 +
|proof=Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки мы можем текущее дерево <tex>T</tex> до MST.Докажем это по индукции.
 +
База: n = 1(Лемма 1).
 +
Переход: Пусть дерево получившееся после n итераций алгоритма можно достроить до MST.
 +
 
}}
 
}}
  

Версия 20:06, 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]n[/math] в перестановке не является подвижным элементом тогда и толко тогда когда первая компонента перестановки есть (n, ←) или последняя

Теорема:
Алгоритм Борувки строит MST.
Доказательство:
[math]\triangleright[/math]

Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки мы можем текущее дерево [math]T[/math] до MST.Докажем это по индукции. База: n = 1(Лемма 1).

Переход: Пусть дерево получившееся после n итераций алгоритма можно достроить до MST.
[math]\triangleleft[/math]

Реализация

  Graph Boruvka(Graph G)
      while T.size < n
           init()                                            // у вершины есть поле comp(компонента которой принадлежит вершина) 
           findComp(T)                                       // разбиваеv граф T на компоненты связынности обычным dfs-ом
           for uv [math]\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 (рус.)

См. также