http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=MaminВикиконспекты - Вклад участника [ru]2026-06-09T15:09:44ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%B4%D0%B2%D1%83%D1%85_%D0%BA%D0%B8%D1%82%D0%B0%D0%B9%D1%86%D0%B5%D0%B2&diff=7312Алгоритм двух китайцев2011-01-19T02:23:09Z<p>Mamin: </p>
<hr />
<div>== Постановка задачи ==<br />
<br />
Дан взвешенный ориентированный граф <tex>G</tex> и начальная вершина <tex>v</tex>. Требуется построить корневое остовное дерево в <tex>G</tex> с корнем в вершине <tex>v</tex> минимального веса.<br />
<br />
== Алгоритм ==<br />
<br />
[[Файл:graph1.png|thumb|right|300x200px|Исходный граф <tex>G_0</tex>]]<br />
[[Файл:graph2.png|thumb|right|300x200px|Граф <tex>C</tex>, построенный по графу <tex>G_0</tex>]]<br />
<br />
Пусть <tex>G_0 = (V_0, E_0)</tex> - исходный граф.<br><br />
1) Если хотя бы одна вершина графа <tex>G_0</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br><br />
2) Для каждой вершины <tex>u</tex> графа <tex>G_0</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><br />
3) Строим граф <tex>K = (V_0,K_0)</tex>, где <tex>K_0</tex> - множество рёбер нулевого веса графа <tex>G_0</tex> c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <tex>v</tex>, то оно и будет искомым.<br><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_0</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br><br />
5) Продолжим с пункта 2, используя граф <tex>C</tex> вместо <tex>G_0</tex>.<br><br />
6) В <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>.<br><br />
7) Полученное дерево <tex>T'</tex> - MST в графе <tex>G_0</tex>.<br />
<br />
== Корректность ==<br />
<br />
1) После перевзвешивания в каждую вершину входит по крайней мере 1 ребро нулевого веса.<br><br />
2) Пусть <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><br />
3) Пусть есть некоторый путь от вершины <tex>v</tex> до некоторой вершины <tex>u</tex> в графе <tex>G_0</tex> с весовой функцией <tex>w'</tex>. Тогда мы можем добавить к нашему дереву все вершины из компоненты сильной связности графа <tex>K</tex>, которой принадлежит вершина <tex>u</tex> (по нулевым путям из <tex>u</tex>). При этом вес нашего дерева не изменится.<br><br />
4) Если в графе <tex>K</tex> нет остовного дерева с корнем в <tex>v</tex>, то в графе <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><br />
5) Из сделанных замечаний следует, что дерево <tex>T'</tex> - MST в <tex>G_0</tex>.<br />
<br />
== Сложность ==<br />
Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит алгоритм можно реализовать за <tex>O(|V||E|)</tex>.<br />
<br />
[[Категория: Алгоритмы и структуры данных]]<br />
[[Категория: Остовные деревья ]]</div>Maminhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Graph2.png&diff=7311Файл:Graph2.png2011-01-19T02:22:36Z<p>Mamin: </p>
<hr />
<div></div>Maminhttp://neerc.ifmo.ru/wiki/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Graph1.png&diff=7310Файл:Graph1.png2011-01-19T01:53:54Z<p>Mamin: </p>
<hr />
<div></div>Mamin