212
правок
Изменения
м
→Доказательство корректности
{{Теорема
|statement= Алгоритм Борувки строит '''MST'''.
|proof=Очевидно, что в результате работы алгоритма получается дерево. Пусть <tex> T </tex> {{---}} минимальное остовное дерево графа <tex> G </tex>, а <tex> T' </tex> {{---}} дерево полученное после работы алгоритма.
Покажем, что <tex> T = T'</tex>.
Предположим обратное <tex> T \neq T' </tex>. Пусть ребро <tex> e' </tex> {{---}} первое окрашенное добавленное ребро дерева <tex> T' </tex>, не принадлежащее дереву <tex> T </tex>. Пусть <tex> P </tex> {{---}} путь, соединяющий в дереве <tex> T </tex> вершины ребра <tex> e' </tex>.
Понятно, что в момент, когда ребро <tex> e' </tex> красилидобавляли, какое-то ребро <tex> P </tex> (назовем его <tex> e </tex>) не было покрашенодобавлено. По алгоритму <tex> w(e) \geqslant w(e') </tex>. Однако тогда <tex> T - e + e' </tex> {{---}} остовное дерево веса не превышающего вес дерева <tex> T </tex>. Получили противоречение. Следовательно <tex> T = T'</tex>.
}}
