234
правки
Изменения
→Корректность
''' Замечания: '''
* После перевзвешивания в каждую вершину, кроме <tex>v</tex>, входит по крайней мере одно ребро нулевого веса.<br>
* Пусть <tex>T</tex> — искомое дерево в <tex>G</tex> с весовой функцией <tex>w</tex>. <tex>w'(T) = w(T) - \sum \limits_{u \in V \setminus v}m(u)</tex>, т.е. <tex>T</tex> - MST в <tex>G</tex> с весовой функцией <tex>w</tex> тогда и только тогда, когда <tex>T</tex> — MST в <tex>G</tex> с весовой функцией <tex>w'</tex>.<br>
Из сделанных замечаний и леммы следует, что дерево <tex>T'</tex> — MST в <tex>G</tex>.
<br><br>
=== Реализация ===
<br>
