42 3. Задача о минимальном остове
3. Задача о минимальном остове
Пусть G = (V, E) — связный обыкновенный граф. Напомним (см.
разд. ??), что его остовом называется остовный подграф, являющийся
деревом. Остов (n, m)-графа легко найти поиском в глубину или поис-
ком в ширину. Поскольку оба поиска имеют сложность O(m + n) и в
связном графе m > n −1, остов связного (n, m)-графа можно на йти за
время O(m).
Граф G = (V, E) называется взвешенным, если задана функция
c : E −→ R. Это означает, что каждому ребру e такого графа по-
ставлено в соответствие чиcло c(e), называемое весом или стоимостью
ребра e. Иными словами, взвешенный граф — это тройка (V, E, c). Для
произвольного ненулевого подграфа H его весом c(H) будет называться
сумма весов всех ребер подграф а H.
Остов T взвешенного графа G назовем минимальным остовом, если
для любого остова T
0
выполнено неравенство c(T ) 6 c(T
0
).
Этот раздел посвящен решению следующей задачи: в данном связном
графе найти минимальный остов (задача о минимальном остове).
Пусть G — связный граф. Ациклический остовный подграф F из G
будем называть остовным лесом графа G. В том случае, когда остов-
ный лес графа G связен, он является остовом графа G. Ребро e = uv
называется внешним к остовному лесу F , если его концы лежат в раз-
ных компонентах связности леса F . Если H — некоторая компонента
связности остовного леса F , то через Ext(H) будет обозначаться мно-
жество всех внешних ребер, каждое из которых инцидентно некоторой
вершине из H. Ясно, что Ext(H) является сечением графа G.
Предположим, что F — остовный лес связно го взвешенного графа
G. Будем говорить, что F продолжаем до минимального остова, если
существует такой минимальный остов T , что F 6 T .
Лемма 1. Пу сть остовный лес F продолжаем до минимального
остова и H — одна из компонент связности леса F . Если e — реб-
ро минимального веса из Ext(H), то остовный л ес F + e продолжаем
до минимального остова.
Доказательство. Пусть T — такой минимальный остов графа G,
что F 6 T и e 6∈ ET . Из теоремы ?? следует, что подграф T + e содер-
жит единственный цикл C. В разд. ?? было показано, что любое сечение
и любой цикл имеют четное число общих ребер. Поскольку ребро e яв-
ляется общим для сечения Ext(H) и цикла C, найдется еще одно ребро