212
правок
Изменения
м
Докажем это по индукции. '''База. ''' <tex>n = 1</tex>(см. [[#lemma1|ЛеммаЛемму]]).
Нет описания правки
<b>Алгоритм Борувки</b> (англ. ''Borůvka's algorithm'') — {{---}} алгоритм поиска минимального остовного дерева (англ. ''minimum spanning tree, MST'') во взвешенном неориентированном связном графе.
Впервые был опубликован в 1926 году Отакаром Борувкой.
|id=th1.
|statement=Алгоритм Борувки строит ''MST''.
|proof=Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф <tex>T</tex> можно достроить до ''MST''. Докажем это по индукции.
'''Переход. ''' Пусть лес <tex>T</tex>, получившийся после <tex>n</tex> итераций алгоритма, можно достроить до ''MST''. Докажем, что после <tex>n+1</tex> итерации получившийся лес <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' {{---}} T</tex>. На этом цикле имеется ребро, большее по весу чем ребро <tex>x</tex>, иначе компонента для которой <tex>x</tex> является минимальным ребром ни с кем больше ни связана. Исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.
==Реализация==
У вершины есть поле comp — {{---}} компонента связности, которой принадлежит эта вершина.
{| width = 100%
* [[Алгоритм двух китайцев]]
== Ссылки Источники информации ==
* [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]
