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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Доказательство корректности)
(Описание алгоритма)
Строка 3: Строка 3:
  
 
==Описание алгоритма==
 
==Описание алгоритма==
Пусть <tex>T</tex> подграф графа <tex>G</tex>. Изначально <tex>T</tex> содердит все вершины из <tex>G</tex> и не содержит ребер.
+
Пусть <tex>T</tex> подграф графа <tex>G</tex>. Изначально <tex>T</tex> содержит все вершины из <tex>G</tex> и не содержит ребер.
  
 
Будем добавлять в <tex>T</tex> ребра следующим образом:  
 
Будем добавлять в <tex>T</tex> ребра следующим образом:  
  
 
Пока <tex>T</tex> не является деревом
 
Пока <tex>T</tex> не является деревом
# Для каждой компоненты связанности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не    принадлежащей данной компоненте.   
+
# Для каждой компоненты связности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не    принадлежащей данной компоненте.   
# Добавим в <tex>T</tex> все ребра, которые хотя бы для одной компоненты связанности оказались минимальными.
+
# Добавим в <tex>T</tex> все ребра, которые хотя бы для одной компоненты связности оказались минимальными.
  
 
Получившийся граф <tex>T</tex> является минимальным остовным деревом графа <tex>G</tex>.
 
Получившийся граф <tex>T</tex> является минимальным остовным деревом графа <tex>G</tex>.
Строка 15: Строка 15:
 
Данный алгоритм может работать неправильно если в графе есть ребра, равные по весу. Например полный граф из 3-х вершин, вес каждого ребра равен 1. Избежать эту проблему можно, выбирая в пункте 1 среди ребер, равных по весу ребро с наименьшим номером.
 
Данный алгоритм может работать неправильно если в графе есть ребра, равные по весу. Например полный граф из 3-х вершин, вес каждого ребра равен 1. Избежать эту проблему можно, выбирая в пункте 1 среди ребер, равных по весу ребро с наименьшим номером.
  
Доказательство будем производить, считая веса всех ребер различными.
+
Доказательство будем проводить, считая веса всех ребер различными.
  
 
==Доказательство корректности==
 
==Доказательство корректности==

Версия 23:48, 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].

Данный алгоритм может работать неправильно если в графе есть ребра, равные по весу. Например полный граф из 3-х вершин, вес каждого ребра равен 1. Избежать эту проблему можно, выбирая в пункте 1 среди ребер, равных по весу ребро с наименьшим номером.

Доказательство будем проводить, считая веса всех ребер различными.

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

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


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

Очевидно, что агоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф [math]T[/math] можно достроить до MST.

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

  • База: [math]n[/math] = 1(Лемма).
  • Переход: Пусть лес [math]T[/math], получившийся после [math]n[/math] итераций алгоритма, можно достроить до MST. Докажем, что после [math]n+1[/math] итерации получившийся лес [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[/math] является минимальным ребром ни с кем больше ни связана.Исходя из критерия Тарьяна, получаем противоречие.
Получаем [math]T'[/math] можно достроить до 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] Component                                 // Component — множество компонент связанности в T
                   T.addEdge(minEdge[k])                     // добавляем ребро если его не было в T
      return T;     

Асимптотика

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

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

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

Ссылки

См. также