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

3{\bf do} найти безопасное ребро $(u,v)$ для $А$

4$А \leftarrow А \cvrp \{(u,v)\}$

5{\bf return} $А$

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

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

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

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

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

Теорема 24.1

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

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

разреза. Тогда ребро (и, v) является безопасным для А. Доказательство

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

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

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

Следующее следствие теоремы 24.1 будет использовано в разделе 24.2.

Следствие 24.2

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

Доказательство

очевидно: разрез (С, V\C) согласован с А, а ребро (и, v) - лёгкое ребро для этого разреза. Упражнения 24.1-1

Пусть (и, v) - ребро минимального веса в графе G. Покажите, что (и, v) принадлежит некоторому минимальному остову этого графа.

24.1-2

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

24.1-3

Покажите, что если ребро (и, v) содержится в некотором минимальном остове, то существует некоторый разрез графа, для которого оно является лёгким ребром, пересекающим этот разрез.

24.1-4

Рассмотрим множество всех рёбер, которые являются лёгкими рёбрами всевозможных разрезов графа. Приведите простой пример, когда это множество не является минимальным остовом.

24.1-5

Пусть е - ребро максимального веса в некотором цикле графа G = (V,E). Докажите, что существует минимальный остов графа G = (V,E\ {е}), который является также минимальным остовом графа G.

24.1-6

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

24.1-7

Объясните, почему в графе с положительными весами рёбер любое подмножество рёбер, связывающее все вершины и обладающее минимальным суммарным весом (среди таких подмножеств), является деревом. Приведите пример, показывающий, что это заключение перестаёт быть верным, если веса рёбер могут быть отрицательными.

24.1-8

Пусть Г - минимальный остов графа G. Составим упорядоченный список весов всех рёбер остова Т. Покажите, что для любого другого минимального остова получится тот же самый список.

24.1-9

Пусть Г - минимальный остов графа G = (V,E). Пусть V - подмножество V. Через Т обозначим подграф Г, порождённый С, а через G - подграф G, порождённый V. Покажите, что если Т связен, то Т - минимальный остов G.