Изменения

Пусть <tex>G_0 = (V_0, E_0)</tex> - исходный граф. <br>1) Если хотя бы одна вершина графа <tex>G_0</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя. Теперь для <br>2) Для каждой вершины <tex>u</tex> графа <tex>G_0</tex> произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex> и вычтем его вес из весов всех остальных рёбер, входящих в <tex>u</tex>.Теперь в каждую вершину графа <tex>G_0</tex> входит по крайней мере 1 ребро нулевого веса. <tex>m(u) = \min \limits_{v \in V_0}w(vu), w'(vu) = w(vu) - m(u)</tex>.<br>Пусть 3) Строим граф <tex>K = (V_0,K_0)</tex>, где <tex>TK_0</tex> - искомое дерево в множество рёбер нулевого веса графа <tex>G_0</tex> с c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <tex>w'(T) = w(T) - \sum \limits_{u \in V_0 \setminus v}m(u)</tex>, т.ето оно и будет искомым. <br>4) Если такого дерева нет, то построим граф <tex>TC</tex> - MST в конденсацию графа <tex>G_0K</tex> с весовой функцией . Пусть <tex>wy</tex> тогда и только тогда, когда <tex>Tz</tex> - MST в две вершины графа <tex>G_0C</tex> с весовой функцией , отвечающие компонентам сильной связности <tex>w'Y</tex>.и <tex>Z<br/tex>Рассмотрим граф графа <tex>K = (V_0,K_0)</tex>, где соответственно. Положим вес ребра между вершинами <tex>y</tex> и <tex>K_0z</tex> - множество равным минимальному среди весов рёбер нулевого веса графа <tex>G_0</tex> c с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>Понятно5) Продолжим с пункта 2, что если в этом графе найдётся остовное дерево с корнем в используя граф <tex>C</tex> вместо <tex>vG_0</tex>, то оно и будет искомым. Пусть теперь такого дерева нет.<br>Пусть есть некоторый путь от вершины 6) В <tex>C</tex> построено MST <tex>vT</tex> до некоторой вершины . Построим теперь MST <tex>uT'</tex> в графе <tex>G_0</tex> с весовой функцией <tex>w'</tex>. Тогда мы можем добавить Добавим к нашему дереву <tex>T'</tex> все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>uv</tex> (по нулевым путям из <tex>uv</tex>). При этом вес нашего дерева не изменится.<br>Теперь построим граф Пусть в <tex>CT</tex> - конденсацию графа есть ребро <tex>Kyz</tex>. Пусть , <tex>y</tex> и отвечает компоненте сильной связности <tex>zY</tex> - две вершины графа , а <tex>Cz</tex>, отвечающие компонентам - компоненте сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес ребра между вершинами Между <tex>yY</tex> и <tex>zZ</tex> равным минимальному среди весов рёбер графа в графе <tex>G_0</tex> с весовой функцией <tex>w'</tex>, идущих из есть ребро <tex>Yy'z'</tex> в , вес которого равен весу ребра <tex>Zyz</tex>.<br>В графе Добавим это ребро к дереву <tex>CT'</tex> содержится меньше вершин, чем в графе . Добавим к <tex>G_0T'</tex>. Иначе, если бы в все вершины компоненты <tex>CZ</tex> было бы столько же вершин, сколько в по нулевым путям из <tex>G_0z'</tex>, то в . Сделаем так для каждого ребра дерева <tex>KT</tex> все компоненты сильной связности состояли бы из единственной вершины. Значит в <br>7) Полученное дерево <tex>G_0T'</tex> с весовой функцией - MST в графе <tex>w'G_0</tex> не было бы нулевых циклов. То есть мы смогли бы построить  == Корректность == 1) После перевзвешивания в каждую вершину входит по крайней мере 1 ребро нулевого веса.<br>2) Пусть <tex>KT</tex> остовное - искомое дерево с корнем в <tex>vG_0</tex>, что противоречит нашему предположению.<br>Предположим теперь, что в с весовой функцией <tex>Cw</tex> уже построено MST . <tex>w'(T) = w(T) - \sum \limits_{u \in V_0 \setminus v}m(u)</tex>, т.е. Построим теперь MST <tex>T'</tex> - MST в <tex>G_0</tex> с весовой функцией <tex>w'</tex>. Добавим к тогда и только тогда, когда <tex>T'</tex> все вершины компоненты сильной связности графа - MST в <tex>KG_0</tex>, которой принадлежит с весовой функцией <tex>vw'</tex> (по нулевым путям из .<br>3) Пусть есть некоторый путь от вершины <tex>v</tex>). Пусть в до некоторой вершины <tex>Tu</tex> есть ребро в графе <tex>yzG_0</tex>, с весовой функцией <tex>yw'</tex> отвечает компоненте . Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа <tex>YK</tex>, а которой принадлежит вершина <tex>zu</tex> - компоненте сильной связности (по нулевым путям из <tex>Zu</tex> графа ). При этом вес нашего дерева не изменится.<br>4) Если в графе <tex>K</tex>. Между нет остовного дерева с корнем в <tex>Yv</tex> и , то в графе <tex>ZC</tex> содержится меньше вершин, чем в графе <tex>G_0</tex> с весовой функцией . Иначе, если бы в <tex>w'C</tex> есть ребро было бы столько же вершин, сколько в <tex>y'z'G_0</tex>, вес которого равен весу ребра то в <tex>yzK</tex>все компоненты сильной связности состояли бы из единственной вершины. Добавим это ребро к дереву Значит в <tex>T'G_0</tex>. Добавим к с весовой функцией <tex>Tw'</tex> все вершины компоненты не было бы нулевых циклов. То есть мы смогли бы построить в <tex>ZK</tex> по нулевым путям из остовное дерево с корнем в <tex>z'v</tex>, что противоречит нашему предположению. Сделаем так для каждого ребра дерева <texbr>T</tex> и получим 5) Из сделанных замечаний следует, что дерево <tex>T'</tex> - MST в графе <tex>G_0</tex>.