Изменения

1) ===== Замечания: =====:* После перевзвешивания в каждую вершину, кроме <tex>v</tex>, входит по крайней мере одно ребро нулевого веса.<br>2) :* Пусть <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>3) Пусть есть некоторый путь от вершины {{Лемма |statement =Катчайшее дерево путей <tex>v</tex> до некоторой вершины <tex>uT'</tex> в графе <tex>G</tex> с весовой функцией можно получить, найдя кратчайшее дерево путей <tex>w'T</tex>. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа в графе <tex>K</tex>, которой принадлежит вершина <tex>u</tex> (по путям нулевого веса а затем заменив в нем каждую компоненту связности деревом, построенным из <tex>u</tex>)дуг нулевой длинны. При этом вес нашего дерева не изменится.<br>4) Если |proof =Зафиксируем любое дерево путей и покажем, что в графе <tex>K</tex> нет остовного дерева с корнем в <tex>vG</tex>найдется дерево не большей длины, имеющее такую структуру, то как сказано в графе <tex>C</tex> содержится меньше вершинлемме. Для такой структуры дерева необходимо и достаточно, чем чтобы в графе <tex>G</tex>каждое из подмножеств входило только по одной дуге. ИначеМеньше быть не может, если бы в <tex>C</tex> было бы столько иначе получится отдельная компонента связности.Если же вершин, сколько в <tex>G</tex>какое-то подмножество входит больше чем одна дуга, то в <tex>K</tex> все компоненты сильной связности состояли бы из единственной вершины. Значитдуги кроме одной можно заменить дугами нулевой длины, лежащими внутри подмножества, в <tex>G</tex> с весовой функцией <tex>w'</tex> что разве лишь уменьшит длину дерева и не было бы нулевых цикловнарушит связности. То есть Повторяя это преобразование нужное число раз мы смогли бы построить в <tex>K</tex> остовное дерево с корнем в <tex>v</tex>, что противоречит нашему предположениюдобьемся искомой структуры дерева.<br>5) }} Из сделанных замечаний и леммы следует, что дерево <tex>T'</tex> — MST в <tex>G</tex>.