Изменения

1) После перевзвешивания в каждую вершину, кроме <tex>v</tex>, входит по крайней мере 1 одно ребро нулевого веса.<br>2) Пусть <tex>T</tex> — искомое дерево в <tex>G</tex> с весовой функцией <tex>w</tex>. <tex>w'(T) = w(T) - \sum \limits_{u \in V_0 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) Пусть есть некоторый путь от вершины <tex>v</tex> до некоторой вершины <tex>u</tex> в графе <tex>G</tex> с весовой функцией <tex>w'</tex>. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>u</tex> (по нулевым путям нулевого веса из <tex>u</tex>). При этом вес нашего дерева не изменится.<br>4) Если в графе <tex>K</tex> нет остовного дерева с корнем в <tex>v</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>