Остов графа наименьшего веса

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

Прежде чем рассматривать конкретные алгоритмы, представим себе задачу перечисления всех остовов связного графа. Процедуру можно представить как последовательное наращивание ребер строящегося дерева. Если выбраны k ребер исходного графа, из которых нельзя составить цикла, мы получаем подграф, являющийся неориентированным лесом. К этому лесу можно добавить еще одно ребро из оставшихся, убедившись, что новое ребро не порождает циклов с остальными. Процедура продолжается до тех пор, пока не наберется n − 1 ребро. В результате мы получим граф, содержащий n − 1 ребро и не имеющий циклов. Если это был бы лес, то количество ребер в нем было бы равно количеству вершин минус количество компонент. Количество n − 1 может получиться только в том случае, когда подграф остовный и и имеет одну компоненту связности, т.е. является деревом.

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

Поиск остова наименьшего веса можно представить как оптимальный спуск из корня дерева остовов в лист. На каждом шаге следует принимать решение, какое ребро из допустимых следует выбрать. Особенность этой задачи состоит в том, что оптимальный выбор ребра на каждом шаге гарантирует оптимальность окончательного результата.

В этой процедуре удобно считать, что наращиваемый подграф изначально включает все вер- шины, а пошаговая процедура состоит в последовательной склейке компонент подграфа-леса с помощью ребер исходного графа. Тогда стартовый граф представляет собой n изолированных вершин. На каждом шаге процесса наращивания добавляется одно ребро и количество компо- нент уменьшается на одну. На конечном (n − 1)-м шаге количество добавленных ребер станет n − 1, а количество компонент сократится до одной.

Рассмотрим два непересекающихся подграфа T₁ = (V₁, E₁) и T₂ = (V₂, E₂) графа G. Введем для них характеристику

где c(v₁;v₂) — вес ребра {v₁, v₂}, а минимум берется по всем тем ребрам {x, y} графа G, для которых v₁ ∈ V₁, v₂ ∈ V₂

Теорема 6.3. Пусть подграф-лес T, состоит из компонент T₁, T₂, ..., T_k и подчинен некоторому остову наименьшего веса. Из компонент T₂, T₃, ..., T_k выберем такую компоненту T_j, на которой ∆(T₁,T_j) минимально, причем эта величина реализуется на ребре γ∗, соединяющем некоторую вершину компоненты T₁ с некоторой вершиной компоненты T_j. Тогда подграф ”T плюс γ∗“ подчинен некоторому остову наименьшего веса.

◀Рассмотрим остовное дерево T′ наименьшего веса, содержащее T. В T′ есть цепь α, соединяющая концы ребра γ∗. Если само это ребро не входит в T′, то его добавление к графу дает цикл γ+α. В цепи α есть первое ребро γ, выходящее за пределы компоненты T₁ (начиная с того конца цепи, который находится в T₁). По условию выбора вес ребра γ не меньше веса ребра γ∗. Удаление ребра γ разрывает образовавшийся цикл и сохраняет связность T′. Следовательно, замена γ на γ∗ приводит к остовному дереву T′′, отличающемуся от T′ всего одним ребром. Поскольку c(γ∗) c(γ), вес остова T′′ не превышает вес остова T′ и является наименьшим, т.е. T′′ — остов наименьшего веса.▶

Доказанная теорема является теоретической основой нескольких алгоритмов выбора остова наименьшего веса. Отметим, что принцип выбора, сформулированный в теореме, обладает некоторой свободой: в качестве компоненты T₁ можно выбирать любую из имеющихся. Про- извольность такого выбора означает, что и конкретный алгоритм построения остова можно реализовать по-разному. Рассмотрим два таких алгоритма.

Алгоритм Краскала. В этом алгоритме минимизация выполняется по обоим компонентам T₁ и T₁. На самом деле нет нужды перебирать всевозможные пары компонент и определять на какой паре величина ∆ минимальна. Можно просто перебрать все ребра графа и среди них выбрать ребро наименьшего веса, которое, во-первых, не входит в T, а во-вторых, не образует цикла с уже имеющимися в T ребрами. Тогда это будет ребро, соединяющее какие-то две компоненты графа T.

Кратко алгоритм Краскала можно описать так.

1. Начинаем с остовного графа T без ребер.

2. Все ребра графа упорядочиваем по возрастанию веса.

3. Выбираем очередное ребро из упорядоченного списка и проверяем, образует ли оно цикл с уже отобранными. Если да, пропускаем его и повторяем пункт. Если нет, переходим к следующему пункту.

4. Проверяем, если отобрано n − 1 ребро, то процесс прекращаем. Иначе возвращаемся к предыдущему пункту.

В изложенной стратегии два узких места: сортировка ребер по возрастанию и проверка на появление циклов при добавлении очередного ребра. Первая проблема сводится к выбору эффективного алгоритма сортировки. Отметим, что полная сортировка всех ребер на самом деле не нужна. Отбираться будет n − 1 ребро, в то время как полный граф содержит гораздо больше ребер: n(n − 1)/2. Сортировку можно свести к выбору на каждом шаге наилучшего из оставшихся ребер. Эта проблема показывает, что алгоритм Краскала наиболее эффективен для графов с небольшим числом ребер (того же порядка, что и число вершин).

Вторая проблема может решаться с помощью специальной системы пометок вершин графа. Поскольку добавляемое ребро должно связывать вершины разных компонент остовного подграфа T, то и проверять надо, принадлежат ли концы ребра разным компонентам. Достаточно каждой вершине приписать специальный ранг, указывающий на компоненту, к которой относится вершина. При выборе очередного ребра отбрасываем варианты, у которых концы имеют одинаковый ранг. Если выбрано ребро, у которого концы имеют ранги r1 и r2, то надо просмотреть все вершины и поменять все ранги r₂ на r₁ (или наоборот). Тогда слияние двух компонент в одну будет отражаться в рангах вершин.

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

Алгоритм Прима. В этом алгоритме дерево T₁ фиксировано, остальные компоненты до конца остаются одиночными вершинами. Технически эту стратегию можно реализовать следующим образом. Каждой вершине x на текущем шаге соответствует метка, содержащая вершину y дерева T₁, ближайшую к x, и вес β ребра, соединяющего y с x. Если вершина x не имеет ребер, связывающих ее с T₁, тот ей приписывается специальная метка (0, ∞). На k-м шаге просматриваются все вершины, не относящиеся к T₁ и среди них выбирается вершина x_k, для которой вес β_k наименьший. Ребро, соединяющее x_k с T₁, заносится в список отобранных ребер. Затем для всех вершин x ∈/ T₁ вес β сравнивается с весом ребра {xk, x} и если последнее меньше, метка вершины x обновляется. Процедура останавливается, когда будет отобрано n−1 ребер или n вершин.