1
правка
Изменения
м
[[Файл:graph1.png|thumb|right|300x200px|Исходный граф <tex>G_0</tex>]]
[[Файл:graph2.png|thumb|right|300x200px|Граф <tex>C</tex>, построенный по графу <tex>G_0</tex>]]
Дан взвешенный ориентированный Если хотя бы одна вершина графа <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>w'</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).|[[Файл:китайГраф2.png|200px]]|-|По нулевым ребрам нельзя дойти до всех вершин из <tex>v</tex>, сумма весов поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).Найдем <tex>MST</tex> для данного графа.|[[Файл:китайГраф3.png|200px]]|-|Произведем спуск до нулевых ребер (Фаза 1, 2).|[[Файл:китайГраф4.png|200px]]|-|По нулевым ребрам нельзя дойти до всех вершин из <tex>v</tex>, поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).Найдем <tex>MST</tex> для данного графа.|[[Файл:китайГраф5.png|200px]]|-|Произведем спуск до нулевых ребер которого минимальна(Фаза 1, 2). По полученным нулевым ребрам можно дойти из корня до всех вершин. Тогда запускаем <tex>dfs</tex> из корня и возвращаем ребра.|[[Файл:китайГраф6.png|200px]]|-|Находим корень в каждой из компонент, из каждого такого корня запускаем <tex>dfs</tex> по нулевым ребрам, возвращаем результат.|[[Файл:китайГраф7.png|200px]]|-|Находим корень в каждой из компонент, из каждого такого корня запускаем <tex>dfs</tex> по нулевым ребрам. Полученое дерево и есть <tex>MST</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> {{Лемма
1) Если хотя бы одна вершина графа <tex>G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br>2) Для каждой вершины <tex>u \ne v</tex> графа <tex>G</tex>, произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex>, и вычтем вес этого ребра из весов всех рёбер, входящих в <tex>u</tex>. <tex>m(u) = \min \limits_{v \in V_0}w(vu), w'(vu) = w(vu) - m(u)</tex>.<br>3) Строим граф <tex>K = (V,K_0)</tex>, где <tex>K_0</tex> — множество рёбер нулевого веса графа <tex>G</tex> c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <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> соответственно. Положим вес ребра между вершинами <tex>y</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>.<br>6) В <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>7) Полученное что дерево <tex>T'</tex> — MST в графе <tex>G</tex>.
1) После перевзвешивания Обозначения:*Граф хранится в каждую вершинувиде множества ребер + индекс корня.*Множество ребер - список смежности.*Ребро - структура {from, кроме <tex>v</tex>to, входит по крайней мере 1 ребро нулевого весаweight}.*root - текущий корень.<br>2) Пусть <tex>T</tex> — искомое дерево в <tex>G</tex> Особенность реализации: алгоритму не важна кратность ребер, поэтому при составлении нового графа кратные ребра могутпоявиться - это уменьшает асимптотику с весовой функцией <tex>wO(V^2)</tex>. до <tex>w'(T) = w(T) - \sum \limits_{u \in V_0 \setminus v}mO(uE)</tex> Проверяем, т.е. можно ли дойти из <tex>Tv</tex> до остальных вершин. Если можно - MST в <tex>G<запускаем findMST. int findMST(edges, n, root): int res = 0 int minEdge[n] /tex> с весовой функцией <tex>w</tex> тогда и только тогдасоздаем массив минимумов, когда <tex>T</tex> — MST входящих в каждую компоненту, инициализируем бесконечностью. for each <tex>Ge \in </tex> с весовой функцией <tex>edges minEdge[e.to] = min(e.w'</tex>, minEdge[e.<br>to])3) Пусть есть некоторый путь от вершины for each <tex>v\in V \backslash \{root\}</tex> до некоторой вершины <tex>u< res += minEdge[v] //tex> веса минимальных ребер точно будут в графе результате edge zeroEdges[] //создаем массив нулевых ребер for each <tex>Ge \in </tex> с весовой функцией <tex>edges if e.w'</tex>== minEdge[e.to] zeroEdges. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>u</tex> pushback(по нулевым путям из <tex>ue_1</tex>). При этом вес нашего дерева не изменится.<br>4) Если в графе <tex>K</tex> нет остовного дерева с корнем в / <tex>ve_1</tex>- ребро е, то в графе <tex>C</tex> содержится меньше вершинуменьшенное на минимальный вес, чем входящий в графе <tex>G</tex>e. Иначеto if dfs(root, если бы в <tex>C<zeroEdges) //tex> было бы столько же проверяем, можно ли дойти до всех вершин, сколько в <tex>G<по нулевым ребрам return res int newComponents[n] /tex>, то в <tex>K</tex> все будущие компоненты сильной связности состояли бы из единственной вершины. Значит newComponents = Сondensation(zeroEdges) edge newEdges[] //создаем массив ребер в <tex>G</tex> новом графе с весовой функцией вершинами в полученных компонентах for each <tex>w'e \in</tex> не было бы нулевых цикловedges if e.to и e. То есть мы смогли бы построить from в <tex>K</tex> остовное дерево разных компонентах добавляем в newEdges ребро с корнем концами в <tex>v</tex>, что противоречит нашему предположениюданных компонентах и весом e.w - minEdge[e.<br>to]5 res += findMST(newEdges, ComponentsCount, newComponents[root]) Из сделанных замечаний следует, что дерево <tex>T'</tex> — MST в <tex>G</tex>. return res
Исправление ошибки в псевдокоде
'''Алгоритм двух китайцев''' — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.
== Постановка задачи ==
Дан взвешенный ориентированный граф <tex>G(V, E)</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex>, сумма весов всех ребер которого минимальна.
== Алгоритм ==
=== Постановка задачи Описание ===
|statement=Кратчайшее дерево путей <tex>T'</tex> в графе <tex>G</tex> можно получить, найдя кратчайшее дерево путей <tex>T</tex> в графе <tex>C</tex>, а затем заменив в нем каждую компоненту сильной связности деревом, построенным из дуг нулевой длинны.|proof== Описание ===Зафиксируем любое дерево путей и покажем, что в графе <tex>G</tex> найдется дерево не большей длины, имеющее такую структуру, как сказано в лемме. Для такой структуры дерева необходимо и достаточно, чтобы в каждое из подмножеств входило только по одному ребру. Меньше быть не может, иначе получится отдельная компонента связности. Если же в какое-то подмножество входит больше чем одно ребро, то все ребра кроме одного можно заменить ребрами нулевой длины, лежащими внутри подмножества, что разве лишь уменьшит длину дерева и не нарушит связности. Повторяя это преобразование нужное число раз мы добьемся искомой структуры дерева.}}
== Корректность = Реализация ===
=== Сложность ===Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит , алгоритм можно реализовать за <tex>O(|V||E|VE)</tex>.
== Источники ==
*Романовский И. В. '''Дискретный анализ''', 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - '''ISBN 5-7940-0114-3'''
* [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]
==См. также==
* [[Алгоритм Борувки]]
* [http://en.wikipedia.org/wiki/Edmonds%27_algorithm Edmonds' Algorithm]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/shortest-tree-chinese-2003 Визуализатор алгоритма]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
