Изменения

=== '''Алгоритм ===Дан взвешенный ориентированный граф <tex>G</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> двух китайцев''' — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине <tex>v</tex> минимального веса. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.

Пусть == Постановка задачи == Дан взвешенный ориентированный граф <tex>G_0 = G(V_0V, E_0E)</tex> - исходный графи начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex>, сумма весов всех ребер которого минимальна.  == Алгоритм ==  === Описание === Если хотя бы одна вершина графа <tex>G_0G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя. Теперь для  {||-|width="70%"|# Для каждой вершины <tex>u\ne v</tex> графа <tex>G_0G</tex> произведём следующую операцию: найдём ребро минимального веса, входящее в <tex>u</tex> , и вычтем его вес этого ребра из весов всех остальных рёбер, входящих в <tex>u</tex>.Теперь в каждую вершину графа <tex>G_0</tex> входит по крайней мере 1 ребро нулевого веса. <tex>m(u) = \min \limits_{v tu \in V_0E}w(vutu), w'(vutu) = w(vutu) - m(u)</tex>.<br>Пусть # Строим граф <tex>K = (V,K_0)</tex>, где <tex>TK_0</tex> - искомое дерево в — множество рёбер нулевого веса графа <tex>G_0G</tex> с c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <tex>w'(T) = w(T) - \sum \limits_{u \in V_0 \setminus v}m(u)</tex>, т.ето оно и будет искомым. <br># Если такого дерева нет, то построим граф <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_0G</tex> c с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>Понятно# Продолжим с пункта 2, что если в этом графе найдётся остовное дерево с корнем в используя граф <tex>C</tex> вместо <tex>vG</tex>, то оно и будет искомым. Пусть теперь такого дерева нет.<br>Пусть есть некоторый путь от вершины # В <tex>C</tex> построено MST <tex>vT</tex> до некоторой вершины . Построим теперь MST <tex>uT'</tex> в графе <tex>G_0G</tex> с весовой функцией <tex>w'</tex>. Тогда мы можем добавить Добавим к нашему дереву <tex>T'</tex> все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>uv</tex> (по нулевым путям нулевого веса из <tex>uv</tex>). При этом вес нашего дерева не изменится.Пусть в <tex>T<br/tex>Теперь построим граф есть ребро <tex>Cyz</tex> - конденсацию графа , где <tex>Ky</tex>. Пусть отвечает компоненте сильной связности <tex>yY</tex> и , а <tex>z</tex> - две вершины — компоненте сильной связности <tex>Z</tex> графа <tex>CK</tex>, отвечающие компонентам сильной связности . Между <tex>Y</tex> и <tex>Z</tex> графа в графе <tex>G</tex> с весовой функцией <tex>w'</tex> есть ребро <tex>Ky'z'</tex> соответственно. Положим , вес которого равен весу ребра между вершинами <tex>yyz</tex> и . Добавим это ребро к дереву <tex>zT'</tex> равным минимальному среди весов рёбер графа . Добавим к <tex>G_0T'</tex> с весовой функцией все вершины компоненты <tex>w'Z</tex>, идущих по путям нулевого веса из <tex>Yz'</tex> в . Сделаем так для каждого ребра дерева <tex>ZT</tex>.<br>В графе # Полученное дерево <tex>CT'</tex> содержится меньше вершин, чем — MST в графе <tex>G_0G</tex>. Иначе||} === Пример === {| class = "wikitable" width="70%"|-! Описание !! Изображение |-|Исходный граф.|[[Файл:китайГраф1.png|200px]]|-|Произведем спуск до нулевых ребер (Фаза 1, если бы в 2).|[[Файл:китайГраф2.png|200px]]|-|По нулевым ребрам нельзя дойти до всех вершин из <tex>Cv</tex> было бы столько же вершин, сколько в поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3).Найдем <tex>G_0MST</tex>для данного графа.|[[Файл:китайГраф3.png|200px]]|-|Произведем спуск до нулевых ребер (Фаза 1, то в 2).|[[Файл:китайГраф4.png|200px]]|-|По нулевым ребрам нельзя дойти до всех вершин из <tex>Kv</tex> все компоненты сильной связности состояли бы из единственной вершины, поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3). Значит в Найдем <tex>G_0MST</tex> с весовой функцией для данного графа.|[[Файл:китайГраф5.png|200px]]|-|Произведем спуск до нулевых ребер (Фаза 1, 2). По полученным нулевым ребрам можно дойти из корня до всех вершин. Тогда запускаем <tex>w'dfs</tex> не было бы нулевых цикловиз корня и возвращаем ребра.|[[Файл:китайГраф6. То есть мы смогли бы построить png|200px]]|-|Находим корень в каждой из компонент, из каждого такого корня запускаем <tex>Kdfs</tex> остовное дерево с корнем по нулевым ребрам, возвращаем результат.|[[Файл:китайГраф7.png|200px]]|-|Находим корень в каждой из компонент, из каждого такого корня запускаем <tex>vdfs</tex>, что противоречит нашему предположениюпо нулевым ребрам.<br>Предположим теперь, что в Полученое дерево и есть <tex>CMST</tex> уже построено MST в исходном графе.|[[Файл:китайГраф8.png|200px]]|} === Корректность === ''' Замечания: '''* После перевзвешивания в каждую вершину кроме <tex>Tv</tex>входит по крайней мере одно ребро нулевого веса. Построим теперь MST <br>* Пусть <tex>T'</tex> — искомое дерево в <tex>G_0G</tex> с весовой функцией <tex>w'</tex>. Добавим к <tex>w'(T) = w(T') - \sum \limits_{u \in V \setminus v}m(u)</tex> все вершины компоненты сильной связности графа , т.е. <tex>KT</tex>, которой принадлежит - MST в <tex>vG</tex> (по нулевым путям из с весовой функцией <tex>vw</tex>). Пусть в тогда и только тогда, когда <tex>T</tex> есть ребро — MST в <tex>yzG</tex>, с весовой функцией <tex>yw'</tex> отвечает компоненте сильной связности .<br> {{Лемма |statement=Кратчайшее дерево путей <tex>YT'</tex>, а в графе <tex>zG</tex> - компоненте сильной связности можно получить, найдя кратчайшее дерево путей <tex>ZT</tex> графа в графе <tex>KC</tex>, а затем заменив в нем каждую компоненту сильной связности деревом, построенным из дуг нулевой длинны. Между |proof=Зафиксируем любое дерево путей и покажем, что в графе <tex>YG</tex> найдется дерево не большей длины, имеющее такую структуру, как сказано в лемме. Для такой структуры дерева необходимо и достаточно, чтобы в каждое из подмножеств входило только по одному ребру. Меньше быть не может, иначе получится отдельная компонента связности. Если же в какое-то подмножество входит больше чем одно ребро, то все ребра кроме одного можно заменить ребрами нулевой длины, лежащими внутри подмножества, что разве лишь уменьшит длину дерева и не нарушит связности. Повторяя это преобразование нужное число раз мы добьемся искомой структуры дерева.}} Из сделанных замечаний и леммы следует, что дерево <tex>ZT'</tex> — MST в графе <tex>G_0G</tex> . === Реализация === Обозначения:*Граф хранится в виде множества ребер + индекс корня.*Множество ребер - список смежности.*Ребро - структура {from, to, weight}.*root - текущий корень. Особенность реализации: алгоритму не важна кратность ребер, поэтому при составлении нового графа кратные ребра могутпоявиться - это уменьшает асимптотику с весовой функцией <tex>w'O(V^2)</tex> есть ребро до <tex>y'z'O(E)</tex> Проверяем, вес которого равен весу ребра можно ли дойти из <tex>yzv</tex>до остальных вершин. Если можно - запускаем findMST. int findMST(edges, n, root): int res = 0 int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью. Добавим это ребро к дереву for each <tex>T'e \in </tex>edges minEdge[e.to] = min(e. Добавим к w, minEdge[e.to]) for each <tex>T'v \in V \backslash \{root\}</tex> все вершины компоненты <tex>Z< res += minEdge[v] //веса минимальных ребер точно будут в результате edge zeroEdges[] //tex> по нулевым путям из создаем массив нулевых ребер for each <tex>z'e \in </tex>edges if e.w == minEdge[e.to] zeroEdges. Сделаем так для каждого ребра дерева pushback(<tex>Te_1</tex> и получим дерево ) // <tex>T'e_1</tex> - MST ребро е, уменьшенное на минимальный вес, входящий в e.to if dfs(root, zeroEdges) // проверяем, можно ли дойти до всех вершин по нулевым ребрам return res int newComponents[n] // будущие компоненты связности newComponents = Сondensation(zeroEdges) edge newEdges[] //создаем массив ребер в новом графе с вершинами в полученных компонентах for each <tex>G_0e \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>. == Источники ==*Романовский И. В. '''Дискретный анализ''', 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 Визуализатор алгоритма] [[Категория: Алгоритмы и структуры данных]][[Категория: Остовные деревья ]]