Изменения
Нет описания правки
'''Алгоритм двух китайцев''' - алгоритм построения корневого дерева с минимальной суммой весов содержащихся в нем ребер во взвешенном ориентированном графе, разработанный Чу Йонджином и Лю Цзенхонгом.
== Постановка задачи ==
Пусть <tex>G_0 = (V_0, E_0)</tex> - исходный граф.<br>
1) Если хотя бы одна вершина графа <tex>G_0</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br>
2) Для каждой вершины <tex>u \ne v</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>
3) Строим граф <tex>K = (V_0,K_0)</tex>, где <tex>K_0</tex> - множество рёбер нулевого веса графа <tex>G_0</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_0</tex> с весовой функцией <tex>w'</tex>, идущих из <tex>Y</tex> в <tex>Z</tex>.<br>
== Сложность ==
Всего будет построено не более <tex>|V|</tex> конденсаций. Конденсацию можно построить за <tex>O(|E|)</tex>. Значит алгоритм можно реализовать за <tex>O(|V||E|)</tex>.
== Источники ==
*Романрвский И. В. - Баранский В. А., Расин В. В. - Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - '''ISBN 5-7940-0114-3'''
* [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
