<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="ru">
		<id>https://nerc.itmo.ru/wiki/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=217.66.157.12&amp;*</id>
		<title>Викиконспекты - Вклад участника [ru]</title>
		<link rel="self" type="application/atom+xml" href="https://nerc.itmo.ru/wiki/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=217.66.157.12&amp;*"/>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D0%BA%D0%BB%D0%B0%D0%B4/217.66.157.12"/>
		<updated>2026-11-19T06:12:54Z</updated>
		<subtitle>Вклад участника</subtitle>
		<generator>MediaWiki 1.30.0</generator>

	<entry>
		<id>https://nerc.itmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8&amp;diff=27889</id>
		<title>Алгоритм Борувки</title>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8&amp;diff=27889"/>
				<updated>2012-12-17T20:07:49Z</updated>
		
		<summary type="html">&lt;p&gt;217.66.157.12: /* Доказательство корректности */&lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;&amp;lt;b&amp;gt;Алгоритм Борувки&amp;lt;/b&amp;gt; — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе.&lt;br /&gt;
Впервые был опубликован в 1926 году Отакаром Борувкой.&lt;br /&gt;
&lt;br /&gt;
==Описание алгоритма==&lt;br /&gt;
Пусть &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; подграф графа &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt;. Изначально &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; содержит все вершины из &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt; и не содержит ребер.&lt;br /&gt;
&lt;br /&gt;
Будем добавлять в &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; ребра следующим образом: &lt;br /&gt;
&lt;br /&gt;
Пока &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; не является деревом&lt;br /&gt;
# Для каждой компоненты связности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не    принадлежащей данной компоненте.  &lt;br /&gt;
# Добавим в &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; все ребра, которые хотя бы для одной компоненты связности оказались минимальными.&lt;br /&gt;
&lt;br /&gt;
Получившийся граф &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; является минимальным остовным деревом графа &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.&lt;br /&gt;
&lt;br /&gt;
Доказательство будем проводить, считая веса всех ребер различными.&lt;br /&gt;
&lt;br /&gt;
==Доказательство корректности==&lt;br /&gt;
{{Лемма&lt;br /&gt;
|id=lemma1&lt;br /&gt;
|statement=Рассмотрим связный неориентированный взвешенный граф &amp;lt;tex&amp;gt; G = (V, E)  &amp;lt;/tex&amp;gt; с инъективной весовой функцией &amp;lt;tex&amp;gt;w : E \to \mathbb{R}&amp;lt;/tex&amp;gt; .&lt;br /&gt;
Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до MST.&lt;br /&gt;
|proof=Предположим обратное: пусть любое MST графа &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt; не содержит &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt;. Рассмотрим какое-нибудь MST. Тогда существует ребро &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; из &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; такое что &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; не принадлежит MST. Добавив ребро &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; в MST, получаем цикл в котором &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; не максимально, т.к оно было минимальным. Тогда, исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.&lt;br /&gt;
}}&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
{{Теорема&lt;br /&gt;
|id=th1. &lt;br /&gt;
|statement=Алгоритм Борувки строит MST.&lt;br /&gt;
|proof=Очевидно, что алгоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; можно достроить до MST.&lt;br /&gt;
&lt;br /&gt;
Докажем это по индукции.&lt;br /&gt;
&lt;br /&gt;
* База: &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt; = 1([[#lemma1|Лемма]]).&lt;br /&gt;
* Переход: Пусть лес &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt;, получившийся после &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt; итераций алгоритма, можно достроить до MST. Докажем, что после &amp;lt;tex&amp;gt;n+1&amp;lt;/tex&amp;gt; итерации получившийся лес &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt; можно достроить до MST.Предположим обратное: &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt; нельзя достроить до MST. Тогда существует &amp;lt;tex&amp;gt;F&amp;lt;/tex&amp;gt; = MST графа &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt;, содержащее &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt;  и не содержащее &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt;. Тогда рассмотрим цикл, получающийся добавлением в &amp;lt;tex&amp;gt;F&amp;lt;/tex&amp;gt; какого-нибудь ребра &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; из &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt; - &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt;. На этом цикле имеется ребро, большее по весу чем ребро &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt;, иначе компонента для которой &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; является минимальным ребром ни с кем больше ни связана.Исходя из  [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.&lt;br /&gt;
Получаем &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt; можно достроить до MST. Следовательно предположение индукции верно.&lt;br /&gt;
 &lt;br /&gt;
}}&lt;br /&gt;
&lt;br /&gt;
==Реализация==&lt;br /&gt;
{| width = 100%&lt;br /&gt;
|-&lt;br /&gt;
| &lt;br /&gt;
   Graph Boruvka(Graph G)&lt;br /&gt;
       while T.size &amp;lt; n&lt;br /&gt;
            init()                                            // у вершины есть поле comp(компонента, которой принадлежит вершина) &lt;br /&gt;
            findComp(T)                                       // разбиваеv граф T на компоненты связности обычным dfs-ом&lt;br /&gt;
            for uv &amp;lt;tex&amp;gt;\in&amp;lt;/tex&amp;gt; E&lt;br /&gt;
                if u.comp != v.comp&lt;br /&gt;
                    if minEdge[u.comp].w &amp;lt; uv.w&lt;br /&gt;
                        minEdge[u.comp] = uv&lt;br /&gt;
                    if minEdge[v.comp].w &amp;lt; uv.w&lt;br /&gt;
                        minEdge[v.comp] = uv)&lt;br /&gt;
            for k &amp;lt;tex&amp;gt;\in&amp;lt;/tex&amp;gt; Component                                 // Component — множество компонент связности в T&lt;br /&gt;
                    T.addEdge(minEdge[k])                     // добавляем ребро если его не было в T&lt;br /&gt;
       return T;     &lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
==Асимптотика==&lt;br /&gt;
Время работы внутри главного цикла будет равно &amp;lt;tex&amp;gt;O(E + V)&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Количество итераций, которое выполняется главным циклом равно &amp;lt;tex&amp;gt;O(\log{V})&amp;lt;/tex&amp;gt; так как на каждой итерации количество компонент связности уменьшается в 2 раза (изначально количество компонент равно &amp;lt;tex&amp;gt;|V|&amp;lt;/tex&amp;gt;, в итоге должна стать одна компонента).&lt;br /&gt;
&lt;br /&gt;
Общее время работы алгоритма получается &amp;lt;tex&amp;gt;O(E\log{V})&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
== Ссылки ==&lt;br /&gt;
*[http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]&lt;br /&gt;
*[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8 Алгоритм Борувки— Википедия]&lt;br /&gt;
&lt;br /&gt;
==См. также==&lt;br /&gt;
* [[Алгоритм Прима]]&lt;br /&gt;
* [[Алгоритм Краскала]]&lt;br /&gt;
&lt;br /&gt;
[[Категория: Алгоритмы и структуры данных]]&lt;br /&gt;
[[Категория: Остовные деревья ]]&lt;/div&gt;</summary>
		<author><name>217.66.157.12</name></author>	</entry>

	<entry>
		<id>https://nerc.itmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8&amp;diff=27888</id>
		<title>Алгоритм Борувки</title>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8&amp;diff=27888"/>
				<updated>2012-12-17T20:07:05Z</updated>
		
		<summary type="html">&lt;p&gt;217.66.157.12: /* Описание алгоритма */&lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;&amp;lt;b&amp;gt;Алгоритм Борувки&amp;lt;/b&amp;gt; — алгоритм поиска минимального остовного дерева (minimum spanning tree, MST) во взвешенном неориентированном связном графе.&lt;br /&gt;
Впервые был опубликован в 1926 году Отакаром Борувкой.&lt;br /&gt;
&lt;br /&gt;
==Описание алгоритма==&lt;br /&gt;
Пусть &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; подграф графа &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt;. Изначально &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; содержит все вершины из &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt; и не содержит ребер.&lt;br /&gt;
&lt;br /&gt;
Будем добавлять в &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; ребра следующим образом: &lt;br /&gt;
&lt;br /&gt;
Пока &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; не является деревом&lt;br /&gt;
# Для каждой компоненты связности находим минимальное по весу ребро, которое связывает вершину из данной компоненты с вершиной, не    принадлежащей данной компоненте.  &lt;br /&gt;
# Добавим в &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; все ребра, которые хотя бы для одной компоненты связности оказались минимальными.&lt;br /&gt;
&lt;br /&gt;
Получившийся граф &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; является минимальным остовным деревом графа &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Данный алгоритм может работать неправильно, если в графе есть ребра равные по весу. Например, полный граф из трех вершин, вес каждого ребра равен один. В &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; могут быть добавлены все три ребра. Избежать эту проблему можно, выбирая в первом пункте среди ребер, равных по весу, ребро с наименьшим номером.&lt;br /&gt;
&lt;br /&gt;
Доказательство будем проводить, считая веса всех ребер различными.&lt;br /&gt;
&lt;br /&gt;
==Доказательство корректности==&lt;br /&gt;
{{Лемма&lt;br /&gt;
|id=lemma1&lt;br /&gt;
|statement=Рассмотрим связный неориентированный взвешенный граф &amp;lt;tex&amp;gt; G = (V, E)  &amp;lt;/tex&amp;gt; с инъективной весовой функцией &amp;lt;tex&amp;gt;w : E \to \mathbb{R}&amp;lt;/tex&amp;gt; .&lt;br /&gt;
Тогда после первой итерации главного цикла алгоритма Борувки получившийся подграф можно достроить до MST.&lt;br /&gt;
|proof=Предположим обратное: пусть любое MST графа &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt; не содержит &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt;. Рассмотрим какое-нибудь MST. Тогда существует ребро &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; из &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; такое что &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; не принадлежит MST. Добавив ребро &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; в MST, получаем цикл в котором &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; не максимально, т.к оно было минимальным. Тогда, исходя из [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.&lt;br /&gt;
}}&lt;br /&gt;
&lt;br /&gt;
&lt;br /&gt;
{{Теорема&lt;br /&gt;
|id=th1. &lt;br /&gt;
|statement=Алгоритм Борувки строит MST.&lt;br /&gt;
|proof=Очевидно, что агоритм Борувки строит дерево.Будем доказывать что после каждой итерации главного цикла в алгоритме Борувки текущий подграф &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt; можно достроить до MST.&lt;br /&gt;
&lt;br /&gt;
Докажем это по индукции.&lt;br /&gt;
&lt;br /&gt;
* База: &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt; = 1([[#lemma1|Лемма]]).&lt;br /&gt;
* Переход: Пусть лес &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt;, получившийся после &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt; итераций алгоритма, можно достроить до MST. Докажем, что после &amp;lt;tex&amp;gt;n+1&amp;lt;/tex&amp;gt; итерации получившийся лес &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt; можно достроить до MST.Предположим обратное: &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt; нельзя достроить до MST. Тогда существует &amp;lt;tex&amp;gt;F&amp;lt;/tex&amp;gt; = MST графа &amp;lt;tex&amp;gt;G&amp;lt;/tex&amp;gt;, содержащее &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt;  и не содержащее &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt;. Тогда рассмотрим цикл, получающийся добавлением в &amp;lt;tex&amp;gt;F&amp;lt;/tex&amp;gt; какого-нибудь ребра &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; из &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt; - &amp;lt;tex&amp;gt;T&amp;lt;/tex&amp;gt;. На этом цикле имеется ребро, большее по весу чем ребро &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt;, иначе компонента для которой &amp;lt;tex&amp;gt;x&amp;lt;/tex&amp;gt; является минимальным ребром ни с кем больше ни связана.Исходя из  [[Критерий Тарьяна минимальности остовного дерева|критерия Тарьяна]], получаем противоречие.&lt;br /&gt;
Получаем &amp;lt;tex&amp;gt;T'&amp;lt;/tex&amp;gt; можно достроить до MST. Следовательно предположение индукции верно.&lt;br /&gt;
 &lt;br /&gt;
}}&lt;br /&gt;
&lt;br /&gt;
==Реализация==&lt;br /&gt;
{| width = 100%&lt;br /&gt;
|-&lt;br /&gt;
| &lt;br /&gt;
   Graph Boruvka(Graph G)&lt;br /&gt;
       while T.size &amp;lt; n&lt;br /&gt;
            init()                                            // у вершины есть поле comp(компонента, которой принадлежит вершина) &lt;br /&gt;
            findComp(T)                                       // разбиваеv граф T на компоненты связности обычным dfs-ом&lt;br /&gt;
            for uv &amp;lt;tex&amp;gt;\in&amp;lt;/tex&amp;gt; E&lt;br /&gt;
                if u.comp != v.comp&lt;br /&gt;
                    if minEdge[u.comp].w &amp;lt; uv.w&lt;br /&gt;
                        minEdge[u.comp] = uv&lt;br /&gt;
                    if minEdge[v.comp].w &amp;lt; uv.w&lt;br /&gt;
                        minEdge[v.comp] = uv)&lt;br /&gt;
            for k &amp;lt;tex&amp;gt;\in&amp;lt;/tex&amp;gt; Component                                 // Component — множество компонент связности в T&lt;br /&gt;
                    T.addEdge(minEdge[k])                     // добавляем ребро если его не было в T&lt;br /&gt;
       return T;     &lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
==Асимптотика==&lt;br /&gt;
Время работы внутри главного цикла будет равно &amp;lt;tex&amp;gt;O(E + V)&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
Количество итераций, которое выполняется главным циклом равно &amp;lt;tex&amp;gt;O(\log{V})&amp;lt;/tex&amp;gt; так как на каждой итерации количество компонент связности уменьшается в 2 раза (изначально количество компонент равно &amp;lt;tex&amp;gt;|V|&amp;lt;/tex&amp;gt;, в итоге должна стать одна компонента).&lt;br /&gt;
&lt;br /&gt;
Общее время работы алгоритма получается &amp;lt;tex&amp;gt;O(E\log{V})&amp;lt;/tex&amp;gt;.&lt;br /&gt;
&lt;br /&gt;
== Ссылки ==&lt;br /&gt;
*[http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]&lt;br /&gt;
*[http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8 Алгоритм Борувки— Википедия]&lt;br /&gt;
&lt;br /&gt;
==См. также==&lt;br /&gt;
* [[Алгоритм Прима]]&lt;br /&gt;
* [[Алгоритм Краскала]]&lt;br /&gt;
&lt;br /&gt;
[[Категория: Алгоритмы и структуры данных]]&lt;br /&gt;
[[Категория: Остовные деревья ]]&lt;/div&gt;</summary>
		<author><name>217.66.157.12</name></author>	</entry>

	</feed>