Изменения

=== Постановка задачи Описание === Если хотя бы одна вершина графа <tex>G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.

Дан взвешенный ориентированный {||-|width="70%"|# Для каждой вершины <tex>u \ne v</tex> графа <tex>G</tex> произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex>, и вычтем вес этого ребра из весов всех рёбер, входящих в <tex>u</tex>. <tex>m(u) = \min \limits_{tu \in E}w(tu), w'(tu) = w(tu) - m(u)</tex>.<br># Строим граф <tex>GK = (V, EK_0)</tex> и начальная вершина , где <tex>K_0</tex> — множество рёбер нулевого веса графа <tex>G</tex> c весовой функцией <tex>vw'</tex>. Требуется построить корневое Если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым.<br># Если такого дерева нет, то построим граф <tex>C</tex> — конденсацию графа <tex>K</tex>. Пусть <tex>y</tex> и <tex>z</tex> — две вершины графа <tex>C</tex>, отвечающие компонентам сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес ребра между вершинами <tex>y</tex> и <tex>z</tex> равным минимальному среди весов рёбер графа <tex>G</tex> с корнем весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br># Продолжим с пункта 2, используя граф <tex>C</tex> вместо <tex>G</tex>.<br># В <tex>C</tex> построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в вершине <tex>G</tex> с весовой функцией <tex>w'</tex>. Добавим к <tex>T'</tex> все вершины компоненты сильной связности графа <tex>K</tex>, которой принадлежит <tex>v</tex> (по путям нулевого веса из <tex>v</tex>). Пусть в <tex>T</tex> есть ребро <tex>yz</tex>, где <tex>y</tex> отвечает компоненте сильной связности <tex>Y</tex>, а <tex>z</tex> — компоненте сильной связности <tex>Z</tex> графа <tex>K</tex>. Между <tex>Y</tex> и <tex>Z</tex> в графе <tex>G</tex> с весовой функцией <tex>w'</tex> есть ребро <tex>y'z'</tex>, сумма весов всех ребер вес которого минимальнаравен весу ребра <tex>yz</tex>. Добавим это ребро к дереву <tex>T'</tex>. Добавим к <tex>T'</tex> все вершины компоненты <tex>Z</tex> по путям нулевого веса из <tex>z'</tex>. Сделаем так для каждого ребра дерева <tex>T</tex>.<br># Полученное дерево <tex>T'</tex> — MST в графе <tex>G</tex>.||}

=== Описание Пример ===

{| class = "wikitable" width="70%"|-! Описание !! Изображение |-|Исходный граф.|[[Файл:китайГраф1.png|200px]]|-|Произведем спуск до нулевых ребер (Фаза 1, 2) Если хотя бы одна вершина графа <tex>G</tex> недостижима .|[[Файл:китайГраф2.png|200px]]|-|По нулевым ребрам нельзя дойти до всех вершин из <tex>v</tex>, то требуемое дерево построить нельзяпоэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).<br>2) Для каждой вершины Найдем <tex>u \ne vMST</tex> для данного графа <tex>G</tex> произведём следующую операцию.|[[Файл: найдём ребро минимального веса, входящее в <tex>u</tex>, и вычтем вес этого ребра из весов всех рёбер, входящих в <tex>u</tex>китайГраф3. <tex>mpng|200px]]|-|Произведем спуск до нулевых ребер (u) = \min \limits_{tu \in E}w(tu)Фаза 1, w'(tu) = w(tu2) - m(u)</tex>.<br>3) Строим граф <tex>K = (V,K_0)</tex>, где <tex>K_0</tex> — множество рёбер нулевого веса графа <tex>G</tex> c весовой функцией <tex>w'</tex>|[[Файл:китайГраф4. Если в этом графе найдётся остовное дерево с корнем в png|200px]]|-|По нулевым ребрам нельзя дойти до всех вершин из <tex>v</tex>, то оно и будет искомым.<br>4) Если такого дерева нет, то построим граф <tex>C</tex> — поэтому строим конденсацию графа <tex>K</tex>. Пусть <tex>y</tex> и <tex>z</tex> — две вершины графа <tex>C</tex>, отвечающие компонентам сильной связности <tex>Y</tex> и <tex>Z</tex> графа <tex>K</tex> соответственно. Положим вес добавляем наименьшие ребра между вершинами компонентами (Фаза 3).Найдем <tex>yMST</tex> и <tex>z</tex> равным минимальному среди весов рёбер для данного графа <tex>G</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>5) Продолжим с пункта 2, используя граф <tex>C</tex> вместо <tex>G</tex>|[[Файл:китайГраф5.<br>png|200px]]|-6|Произведем спуск до нулевых ребер (Фаза 1, 2) В <tex>C</tex> построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в <tex>G</tex> с весовой функцией <tex>w'</tex>По полученным нулевым ребрам можно дойти из корня до всех вершин. Добавим к <tex>T'</tex> все вершины компоненты сильной связности графа <tex>KТогда запускаем </tex>, которой принадлежит <tex>vdfs</tex> (по путям нулевого веса из <tex>v</tex>)корня и возвращаем ребра.|[[Файл:китайГраф6. Пусть png|200px]]|-|Находим корень в <tex>T</tex> есть ребро <tex>yz</tex>каждой из компонент, где из каждого такого корня запускаем <tex>y</tex> отвечает компоненте сильной связности <tex>Ydfs</tex>по нулевым ребрам, а <tex>z</tex> — компоненте сильной связности <tex>Z</tex> графа <tex>K</tex>возвращаем результат.|[[Файл:китайГраф7. Между <tex>Y</tex> и <tex>Z</tex> png|200px]]|-|Находим корень в графе <tex>G</tex> с весовой функцией <tex>w'</tex> есть ребро <tex>y'z'</tex>каждой из компонент, вес которого равен весу ребра <tex>yz</tex>. Добавим это ребро к дереву <tex>T'</tex>. Добавим к <tex>T'</tex> все вершины компоненты <tex>Z</tex> по путям нулевого веса из <tex>z'</tex>. Сделаем так для каждого ребра дерева такого корня запускаем <tex>Tdfs</tex>по нулевым ребрам.<br>7) Полученное Полученое дерево и есть <tex>T'MST</tex> — MST в исходном графе <tex>G</tex>.|[[Файл:китайГраф8.png|200px]]|}

=== Корректность ===

:* После перевзвешивания в каждую вершину, кроме <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>

|statement=&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Катчайшее Кратчайшее дерево путей <tex>T'</tex> в графе <tex>G</tex> можно получить, найдя кратчайшее дерево путей <tex>T</tex> в графе <tex>C</tex>, а затем заменив в нем каждую компоненту сильной связности &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;деревом, построенным из дуг нулевой длинны.

:Зафиксируем любое дерево путей и покажем, что в графе <tex>G</tex> найдется дерево не большей длины, имеющее такую структуру, как сказано в лемме. Для такой структуры дерева необходимо и достаточно, чтобы в каждое из подмножеств входило только по одному ребру. Меньше быть не может, иначе получится отдельная компонента связности. Если же в какое-то подмножество входит больше чем одно ребро, то все ребра кроме одного можно заменить ребрами нулевой длины, лежащими внутри подмножества, что разве лишь уменьшит длину дерева и не нарушит связности. Повторяя это преобразование нужное число раз мы добьемся искомой структуры дерева.

=== Реализация === Обозначения:*Граф хранится в виде множества ребер + индекс корня.*Множество ребер - список смежности.*Ребро - структура {from, to, weight}.*root - текущий корень. Особенность реализации: алгоритму не важна кратность ребер, поэтому при составлении нового графа кратные ребра могутпоявиться - это уменьшает асимптотику с <tex>O(V^2)</tex> до <tex>O(E)</tex> Проверяем, можно ли дойти из <tex>v</tex> до остальных вершин. Если можно - запускаем findMST. int findMST(edges, n, root): int res = 0 int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью. for each <tex>e \in </tex> edges minEdge[e.to] = min(e.w, minEdge[e.to]) for each <tex>v \in V \backslash \{root\}</tex> res += minEdge[v] //веса минимальных ребер точно будут в результате edge zeroEdges[] //создаем массив нулевых ребер for each <tex>e \in </tex> edges if e.w == minEdge[e.to] zeroEdges.pushback(<tex>e_1</tex>) // <tex>e_1</tex> - ребро е, уменьшенное на минимальный вес, входящий в e.to if dfs(root, zeroEdges) // проверяем, можно ли дойти до всех вершин по нулевым ребрам return res int newComponents[n] // будущие компоненты связности newComponents = Сondensation(zeroEdges) edge newEdges[] //создаем массив ребер в новом графе с вершинами в полученных компонентах for each <tex>e \in</tex> edges if e.to и e.from в разных компонентах добавляем в newEdges ребро с концами в данных компонентах и весом e.w - minEdge[e.to] res += findMST(newEdges, ComponentsCount, newComponents[root]) return res === Сложность ===Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит, алгоритм можно реализовать за <tex>O(|V||E|VE)</tex>.