5.4.2 Построение минимального покрывающего дерева

Итак, пусть дан связный неориентированный граф G = (V, Е) и весовая функция w: ЕR. Мы хотим найти минимальное покрывающее дерево (мини- мальный остов), следуя жадной стратегии.

Общая схема всех наших алгоритмов будет такова. Искомый остов строится постепенно: к изначально пустому множеству А на каждом шаге добавляется одно ребро. Множество А всегда является подмножеством некоторого мини- мального остова. Ребро (u, v), добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства: тоже должно быть подмноже- ством минимального остова. Мы называем такое ребро безопасным ребром (safe edge) для А.

Листинг 5.8 – Общий алгоритм построения минимального покрывающего дерева

По определению безопасного ребра свойство «А является подмножеством некоторого минимального остова» остаётся истинным после любого числа ите- раций цикла (для пустого множества это свойство, очевидно, выполнено), так что в строке 5 алгоритм выдаёт минимальный остов. Конечно, главный вопрос состоит в том, как искать безопасное ребро в строке 3. Такое ребро существует (если А является подмножеством минимального остова, то любое ребро этого остова, не входящее в А, является безопасным).

Заметим, что множество А не может содержать циклов (поскольку является частью минимального остова). Поэтому добавляемое в строке 4 ребро соеди- няет различные компоненты графа G_А = (V, A), и с каждой итерацией цикла число компонент уменьшается на 1. Вначале каждая точка представляет собой отдельную компоненту; в конце весь остов одна компонента, так что цикл повторяется |V| – 1 раз.

В оставшейся части этого раздела будет приведено правило отыскания безопас- ных рёбер. В следующем разделе будут описаны два алгоритма, использующих это правило для эффективного поиска безопасных рёбер.

Начнём с определений. Разрезом (cut) (S, V \ S) неориентированного графа G = (V, E) называется разбиение множества его вершин на два подмножества (рис. 5.7) .

Говорят, что ребро (и, v) Е пересекает (crosses) разрез (S, V \ S), если один из его концов лежит в S, а другой – в V \ S. Разрез согласован с множе- ством рёбер А (respects the set А), если ни одно ребро из А не пересекает этот разрез. В множестве пересекающих разрез рёбер выделяют ребра наименьшего (в этом множестве) веса, называя их лёгкими (light edges).

Теорема 5.8. Пусть G = (V, Е) – связный неориентированный граф, на множе- стве вершин которого определена вещественная функция w. Пусть А – мно- жество рёбер, являющееся подмножеством некоторого минимального остова графа G. Пусть (S, V \ S) – разрез графа G, согласованный с А, а (u, v) – лёгкое ребро для этого разреза. Тогда ребро (u, v) является безопасным для А.

Доказательство. Пусть Т – минимальный остов, содержащий А. Предположим, что Т не содержит ребра (и, v), поскольку в противном случае доказываемое утверждение очевидно. Покажем, что существует другой минимальный остов Т ', содержащий,так что ребро (и, v) является безопасным для А.

Рисунок 5.7 – Два изображения одного и того же разреза графа

На рисунке 5.7: (а) Вершины множе- ства S изображены чёрными. вершины из V \ S –белыми. Рёбра, пересекающие разрез, соединяют белые вершины с чёрными. Единственное лёгкое ребро, пересекающее разрез – ребро (d, с). Множество А состоит из серых рёбер. Разрез (S, V \ S) согласован с А (ни одно ребро из А не пересекает разрез). (б) Вершины множества S изображены слева, вершины V \ S – справа. Ребро пересекает разрез, если оно пересекает вертикальную прямую.

Рисунок 5.8 – К доказательству теоремы 5.8

На рисунке 5.8 все вершины S – чёрные, вершины V \ S – белые. Изображены только рёбра минимального остова (назовём его Т). Рёбра множества А выделены серым цветом; (u, v) лёгкое ребро, пересекающее разрез (S, V \ S); (х, у) – ребро единственного пути р от u к v в Т.

Остов Т связен и потому содержит некоторый (единственный) путь р из и в v (рис. 5.8); ребро (и, v) замыкает этот путь в цикл. Поскольку вершины и и v принадлежат разным частям разреза (S, V \ S), в пути р есть по крайней мере одно ребро (х, у), пересекающее разрез. Это ребро не лежит в А, так как разрез согласован с А. Добавив к дереву Т ребро (и, v) и удалив из получившегося цикла ребро (х, у), получим новый остов Т ' = Т \ {(х, у)} {(u, v)}.

Покажем, что Т ' минимальный остов. Поскольку (и, v) – лёгкое ребро, пересекающее разрез (S, V \ S), изъятое из Т ребро (х, у) имеет не меньший вес, чем добавленное вместо него ребро (и, v), так что вес остова мог только уменьшиться. Но остов был минимальным, значит, вес его остался прежним, и новый остов Т ' будет другим минимальным остовом (того же веса). Поэтому ребро (и, v), содержащееся в Т ', является безопасным.

Следствие 5.9. Пусть G = (V, Е) связный неориентированный граф и на мно- жестве Е определена весовая функция w. Пусть А – множество рёбер графа, являющееся подмножеством некоторого минимального остова. Рассмотрим лес G_A = (V, А). Пусть дерево С – одна из связных компонент леса G_A. Рассмот- рим все рёбра графа, соединящие вершины из С с вершинами не из С, и возьмём среди них ребро наименьшего веса. Тогда это ребро безопасно для А.

Доказательство. Оно очевидно: разрез (С, V \ С) согласован с А, а ребро (и,v) – лёгкое ребро для этого разреза.