Изменения

== Алгоритм ==

=== Описание ===

Если хотя бы одна вершина графа <tex>G</tex> недостижима из <tex>v</tex>, то требуемое дерево построить нельзя.<br>

<br>

# Для каждой вершины <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>K = (V,K_0)</tex>, где <tex>K_0</tex> — множество рёбер нулевого веса графа <tex>G</tex> c весовой функцией <tex>w'</tex>. Если в этом графе найдётся остовное дерево с корнем в <tex>v</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>.

=== Корректность ===

*Романовский И. В. '''Дискретный анализ''', 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - '''ISBN 5-7940-0114-3'''

* [http://is.ifmo.ru/vis/ctree/ http://is.ifmo.ru]

[[Категория: Алгоритмы и структуры данных]]

[[Категория: Остовные деревья ]]