Алгоритм двух китайцев — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Алгоритм== Дан взвешенный ориентированный граф <tex>G</tex> и начальная вершина <tex>v</tex>. Требуе…»)
 
Строка 1: Строка 1:
==Алгоритм==
+
== Алгоритм ==
 
Дан взвешенный ориентированный граф <tex>G</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex> минимального веса.
 
Дан взвешенный ориентированный граф <tex>G</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex> минимального веса.
  
Строка 5: Строка 5:
 
Теперь в каждую вершину графа <tex>G_0</tex> входит по крайней мере 1 ребро нулевого веса. <tex>m(u) = \min \limits_{v \in V_0}w(vu), w'(vu) = w(vu) - m(u)</tex>.<br>Пусть <tex>T</tex> - искомое дерево в <tex>G_0</tex> с весовой функцией <tex>w</tex>. <tex>w'(T) = w(T) - \sum \limits_{u \in V_0 \setminus v}m(u)</tex>, т.е. <tex>T</tex> - MST в <tex>G_0</tex> с весовой функцией <tex>w</tex> тогда и только тогда, когда <tex>T</tex> - MST в <tex>G_0</tex> с весовой функцией <tex>w'</tex>.<br>Рассмотрим граф <tex>K = (V_0,K_0)</tex>, где <tex>K_0</tex> - множество рёбер нулевого веса графа <tex>G_0</tex> c весовой функцией <tex>w'</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>Пусть <tex>T</tex> - искомое дерево в <tex>G_0</tex> с весовой функцией <tex>w</tex>. <tex>w'(T) = w(T) - \sum \limits_{u \in V_0 \setminus v}m(u)</tex>, т.е. <tex>T</tex> - MST в <tex>G_0</tex> с весовой функцией <tex>w</tex> тогда и только тогда, когда <tex>T</tex> - MST в <tex>G_0</tex> с весовой функцией <tex>w'</tex>.<br>Рассмотрим граф <tex>K = (V_0,K_0)</tex>, где <tex>K_0</tex> - множество рёбер нулевого веса графа <tex>G_0</tex> c весовой функцией <tex>w'</tex>.
 
Понятно, что если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым. Пусть теперь такого дерева нет.<br>Пусть есть некоторый путь от вершины <tex>v</tex> до некоторой вершины <tex>u</tex> в графе <tex>G_0</tex> с весовой функцией <tex>w'</tex>. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>u</tex> (по нулевым путям из <tex>u</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_0</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>В графе <tex>C</tex> содержится меньше вершин, чем в графе <tex>G_0</tex>. Иначе, если бы в <tex>C</tex> было бы столько же вершин, сколько в <tex>G_0</tex>, то в <tex>K</tex> все компоненты сильной связности состояли бы из единственной вершины. Значит в <tex>G_0</tex> с весовой функцией <tex>w'</tex> не было бы нулевых циклов. То есть мы смогли бы построить в <tex>K</tex> остовное дерево с корнем в <tex>v</tex>, что противоречит нашему предположению.<br>Предположим теперь, что в <tex>C</tex> уже построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в <tex>G_0</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_0</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> и получим дерево <tex>T'</tex> - MST в графе <tex>G_0</tex>.
 
Понятно, что если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым. Пусть теперь такого дерева нет.<br>Пусть есть некоторый путь от вершины <tex>v</tex> до некоторой вершины <tex>u</tex> в графе <tex>G_0</tex> с весовой функцией <tex>w'</tex>. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>u</tex> (по нулевым путям из <tex>u</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_0</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>В графе <tex>C</tex> содержится меньше вершин, чем в графе <tex>G_0</tex>. Иначе, если бы в <tex>C</tex> было бы столько же вершин, сколько в <tex>G_0</tex>, то в <tex>K</tex> все компоненты сильной связности состояли бы из единственной вершины. Значит в <tex>G_0</tex> с весовой функцией <tex>w'</tex> не было бы нулевых циклов. То есть мы смогли бы построить в <tex>K</tex> остовное дерево с корнем в <tex>v</tex>, что противоречит нашему предположению.<br>Предположим теперь, что в <tex>C</tex> уже построено MST <tex>T</tex>. Построим теперь MST <tex>T'</tex> в <tex>G_0</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_0</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> и получим дерево <tex>T'</tex> - MST в графе <tex>G_0</tex>.
 +
 +
== Сложность ==
 +
Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит алгоритм можно реализовать за <tex>O(|V| * |E|)</tex>.

Версия 21:57, 13 января 2011

Алгоритм

Дан взвешенный ориентированный граф [math]G[/math] и начальная вершина [math]v[/math]. Требуется построить корневое остовное дерево в [math]G[/math] с корнем в вершине [math]v[/math] минимального веса.

Пусть [math]G_0 = (V_0, E_0)[/math] - исходный граф. Если хотя бы одна вершина графа [math]G_0[/math] недостижима из [math]v[/math], то требуемое дерево построить нельзя. Теперь для каждой вершины [math]u[/math] графа [math]G_0[/math] произведём следующую операцию: найдём ребро минимального веса, входящее в [math]u[/math] и вычтем его вес из весов всех остальных рёбер, входящих в [math]u[/math]. Теперь в каждую вершину графа [math]G_0[/math] входит по крайней мере 1 ребро нулевого веса. [math]m(u) = \min \limits_{v \in V_0}w(vu), w'(vu) = w(vu) - m(u)[/math].
Пусть [math]T[/math] - искомое дерево в [math]G_0[/math] с весовой функцией [math]w[/math]. [math]w'(T) = w(T) - \sum \limits_{u \in V_0 \setminus v}m(u)[/math], т.е. [math]T[/math] - MST в [math]G_0[/math] с весовой функцией [math]w[/math] тогда и только тогда, когда [math]T[/math] - MST в [math]G_0[/math] с весовой функцией [math]w'[/math].
Рассмотрим граф [math]K = (V_0,K_0)[/math], где [math]K_0[/math] - множество рёбер нулевого веса графа [math]G_0[/math] c весовой функцией [math]w'[/math]. Понятно, что если в этом графе найдётся остовное дерево с корнем в [math]v[/math], то оно и будет искомым. Пусть теперь такого дерева нет.
Пусть есть некоторый путь от вершины [math]v[/math] до некоторой вершины [math]u[/math] в графе [math]G_0[/math] с весовой функцией [math]w'[/math]. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа [math]K[/math], которой принадлежит вершина [math]u[/math] (по нулевым путям из [math]u[/math]). При этом вес нашего дерева не изменится.
Теперь построим граф [math]C[/math] - конденсацию графа [math]K[/math]. Пусть [math]y[/math] и [math]z[/math] - две вершины графа [math]C[/math], отвечающие компонентам сильной связности [math]Y[/math] и [math]Z[/math] графа [math]K[/math] соответственно. Положим вес ребра между вершинами [math]y[/math] и [math]z[/math] равным минимальному среди весов рёбер графа [math]G_0[/math] с весовой функцией [math]w'[/math], идущих из [math]Y[/math] в [math]Z[/math].
В графе [math]C[/math] содержится меньше вершин, чем в графе [math]G_0[/math]. Иначе, если бы в [math]C[/math] было бы столько же вершин, сколько в [math]G_0[/math], то в [math]K[/math] все компоненты сильной связности состояли бы из единственной вершины. Значит в [math]G_0[/math] с весовой функцией [math]w'[/math] не было бы нулевых циклов. То есть мы смогли бы построить в [math]K[/math] остовное дерево с корнем в [math]v[/math], что противоречит нашему предположению.
Предположим теперь, что в [math]C[/math] уже построено MST [math]T[/math]. Построим теперь MST [math]T'[/math] в [math]G_0[/math] с весовой функцией [math]w'[/math]. Добавим к [math]T'[/math] все вершины компоненты сильной связности графа [math]K[/math], которой принадлежит [math]v[/math] (по нулевым путям из [math]v[/math]). Пусть в [math]T[/math] есть ребро [math]yz[/math], [math]y[/math] отвечает компоненте сильной связности [math]Y[/math], а [math]z[/math] - компоненте сильной связности [math]Z[/math] графа [math]K[/math]. Между [math]Y[/math] и [math]Z[/math] в графе [math]G_0[/math] с весовой функцией [math]w'[/math] есть ребро [math]y'z'[/math], вес которого равен весу ребра [math]yz[/math]. Добавим это ребро к дереву [math]T'[/math]. Добавим к [math]T'[/math] все вершины компоненты [math]Z[/math] по нулевым путям из [math]z'[/math]. Сделаем так для каждого ребра дерева [math]T[/math] и получим дерево [math]T'[/math] - MST в графе [math]G_0[/math].

Сложность

Всего будет построено не более [math]|V|[/math] конденсаций. Конденсацию можно построить за [math]O(|E|)[/math]. Значит алгоритм можно реализовать за [math]O(|V| * |E|)[/math].