3. Построение остова наименьшей стоимости

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

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

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

Найти для G остовное дерево наименьшей стоимости.

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

Тогда искомая сеть будет остовным деревом наименьшей длины (стоимости).

Поскольку граф с n вершинами содержит n^n-2 различных остовных дерева, то решение этой задачи "слепым" перебором" вариантов потребовало бы чрезвычайно больших вычислений даже при относительно малых n. Однако для ее решения имеются эффективные алгоритмы.

• Алгоритм Прима;

• Алгоритм Краскала (или алгоритм Крускала);

• Алгоритм Борувки.

Первый алгоритм нахождения такого дерева - алгоритм Дж.Краскала, опубликованный в 1956 г. Развитием этого алгоритма является алгоритм Р.Прима [1961].

Идея алгоритма. Искомые ребра соединяют вершины. Поэтому возможны две стратегии построения.

1. Можно идти от вершин и для каждой из них искать минимальное ребро (как это сделано в алгоритме Прима)

2. можно для каждого ребра выяснять можно ли его включить в строящееся дерево.

Алгоритм Краскала предлагает делать это следующим образом. Во-первых, ребра графа пронумеровываем в порядке возрастания весов. Затем для каждого ребра начиная с первого проверяем соединяет или нет оно две несвязные вершины, если да, то его можно включить в остовное дерево. Ясно, что если мы имеем V вершин, то работа алгоритма начинается с V несвязных компонент графа (пока из графа все ребра исключаем). Для того, чтобы их связать необходимо найти V-1 ребро.

Другими словами, алгоритм организует процесс роста компонент связности в процессе которого он объединяются друг с другом до тех пор пока не останется одна являющаяся конечным результатом.

Приведем теорему, являющуюся обоснованием алгоритма Краскала.

Теорема [Уилсон,1977,с.69].

Пусть G - связный граф с n вершинами, и пусть каждому его ребру приписано неотрицательное действительное число m(e), называемое его мерой.

Тогда следующая процедура приводит к решению задачи о минимальном остовном графе:

(a) выберем ребро e1, обладающее в G наименьшей мерой;

(b) определим по индукции последовательность ребер e2,e3,...,en-1, выбирая на каждом шаге ребро (отличное от предыдущих) с наименьшей мерой, обладающее тем свойством, что оно не образует циклов с предыдущими ребрами ei.

Полученный подграф T графа G, ребрами которого являются e1,e2,...,en-1, и есть требуемое остовное дерево.

Алгоритм Краскала [Ахо,Хопкрофт,Ульман,1979,с.199] работает с набором VS непересекающихся множеств узлов. Каждое множество W из VS представляет связное множество узлов, образующее остовное дерево в остовном лесу, представленном набором VS. Ребра выбираются из E в порядке возрастания стоимости. Ребра (v,w) рассматриваются по очереди. Если v и w принадлежат одному и тому же множеству из VS, то ребро (v,w) исключается из рассмотрения. Если v и w принадлежат разным множествам W1 и W2 (это означает, что W1 и W2 еще не соединены), то сливаем их в одно множество и добавляем (v,w) к множеству ребер, входящих в окончательное остовное дерево. В [Ахо,Хопкрофт,Ульман, 1979,с.199] приведено описание алгоритма Краскала на псевдокоде:

T<-Ж; VS<-Ж;

Построить очередь с приоритетами Q, содержащую все ребра из E

For vОV do Добавить {v} к VS

While |VS|>1 do

begin

Выбрать в Q ребро (v,w) наименьшей стоимости

Удалить (v,w) из Q

If v и w принадлежат различным множествам W₁ и W₂ из VS

then begin

Заменить W₁ и W₂ на W₁ИW₂ в VS

Добавить (v,w) к T

end

end

Замечание 1. В монографии [Ахо,Хопкрофт,Ульман,1979,с.201-202] показано, что остовное дерево наименьшей стоимости для графа с |E| ребрами можно найти за время O(|E|*log|E|) в общем случае и O(|E|), если |E| достаточно велико по сравнению с числом узлов.

Замечание 2. В некоторых ситуациях требуется построить остов не минимального, а максимального веса. К этой задаче также применим алгоритм Краскала. Следует только всюду минимальный вес заменить максимальным.

Замечание 3 [Свами,Тхуласираман,1984,с.424]. Алгоритм Прима для определения минимального взвешенного осто-ва в связном взвешенном графе G=(V,E) формулируется так: выбрать произвольную вершину v в графе G. Среди всех ребер, входящих в v, выбрать ребро e1 с минимальным весом. Стянем e1, и пусть G' - полученный граф. Повторить эти действия для G' и продолжить до тех пор, пока не будет определено ребро en-1. Ребра e1,e2,...,en-1 образуют минимальный взвешенный остов графа G. Напомним, что под стягиванием ребра подразумевается операция удаления ребра e и отождествления его концевых вершин.

Замечание 4. С задачей об остове минимального веса тесно связана задача Штейнера [Лекции,1990,с.62-63]. Мы отметим лишь, что какие-либо эффективные алгоритмы, решающие задачу Штейнера неизвестны!

Тестовые примеры: Для каждого ребра вводите начальную, затем конечную вершины и стоимость ребра, их соединяющего:

(A)1 7 1 1 2 20 (B)1 2 9 7 4 7 (C)1 3 2 4 8 6 7 10 9 3 4 3 1 6 23 2 3 10 3 4 2 2 4 4 5 8 4 9 10 3 2 7 4 5 7 25 2 7 8 4 5 11 2 5 8 4 7 3 0 0 0 3 7 9 5 6 28 1 3 6 7 6 3 1 2 1 1 4 6 2 3 15 6 7 36 1 7 1 0 0 0 3 4 9 6 7 7 4 7 16 0 0 0 1 6 4 3 6 7 6 9 2 4 5 17 6 4 5 8 10 5 7 9 8

Вводите вершины графа: (A) 1 2 3 4 5 6 7 0 (B) 1 2 3 4 5 6 7 0

Ребра остовного дерева наименьшей стоимости: (A) (1 7) (3 4) (2 7) (3 7) (4 5) (1 6) (B) (1 7) (3 4) (7 6) (6 4) (2 7) (4 5) (C) (1 2) (6 9) (1 3) (9 10) (4 7) (5 8) (2 4) (8 10) (4 8)

Отметим, что пример (A) заимствован из [Ахо,Хопкрофт,Ульман,1979, с.200-201], пример (B) заимствован из [Липский,1988,с.198], а пример (C) заимствован из [Лекции,1990,с.341].

Пример

Изображение	Описание
	Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбирается ребро AD (выделено на рисунке).
	Теперь наименьший вес, равный 5, имеет ребро CE. Так добавление CE не образует цикла, то выбираем его в качестве второго ребра.
	Аналогично выбираем ребро DF, вес которого равен 6.
	Следующие ребра — AB и BE с весом 7. Произвольно выбирается ребро AB, выделенное на рисунке. Ребро BD выделено красным, так уже существует путь (зеленый) между B и D, поэтому, если бы это ребро было выбрано, то образовался бы цикл ABD.
	Аналогичным образом выбирается ребро BE, вес которого равен 7. На этом этапе красным выделено гораздо больше ребер: BC, потому что оно создаст цикл BCE, DE, потому что оно создаст цикл DEBA, и FE, потому что оно сформирует цикл FEBAD.
	Алгоритм завершается добавлением ребра EG с весом 9. Минимальное остовное дерево построено.

Алгоритм Прима  — алгоритм построения минимального остовного дерева взвешенного связного неориентированного графа. Алгоритм впервые был открыт в 1930 году чешским математиком Войцехом Ярником, позже переоткрыт Робертом Примом в 1957 году, и, независимо от них, Э. Дейкстрой в 1959 году.

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

Вход: Связный неориентированный граф  .

Выход: Множество T рёбер минимального остовного дерева

Изображение	Множество выбранных вершин U	Ребро (u,v)	Множество невыбранных вершин V \ U	Описание
	{}		{A,B,C,D,E,F,G}	Исходный взвешенный граф. Числа возле ребер показывают их веса, которые можно рассматривать как расстояния между вершинами.
	{D}	(D,A) = 5 V (D,B) = 9 (D,E) = 15 (D,F) = 6	{A,B,C,E,F,G}	В качестве начальной произвольно выбирается вершина D. Каждая из вершин A, B,E and F соединина с D единственным ребром. Вершина A — ближайшая к D, и выбирается как вторая вершина вместе с ребром AD.
	{A,D}	(D,B) = 9 (D,E) = 15 (D,F) = 6 V (A,B) = 7	{B,C,E,F,G}	Следующая вершина — ближайшая к любой из выбранных вершин D или A. Bудалена от D на 9 и от A — на 7. Расстояние до E равно 15, а до F — 6. F является ближайшей вершиной, поэтому она включается в дерево F вместе с ребром DF.
	{A,D,F}	(D,B) = 9 (D,E) = 15 (A,B) = 7 V (F,E) = 8 (F,G) = 11	{B,C,E,G}	Аналогичным образом выбирается вершина B, удаленная от A на 7.
	{A,B,D,F}	(B,C) = 8 (B,E) = 7 V (D,B) = 9 cycle (D,E) = 15 (F,E) = 8 (F,G) = 11	{C,E,G}	В этом случае есть возможность выбрать либо C, либо E, либо G. C удалена от B на 8, E удалена от B на 7, а G удалена от F на 11. E — ближайшая вершина, поэтому выбирается E и ребро BE.
	{A,B,D,E,F}	(B,C) = 8 (D,B) = 9 цикл (D,E) = 15 цикл (E,C) = 5 V (E,G) = 9 (F,E) = 8 цикл (F,G) = 11	{C,G}	Здесь доступны только вершины C и G. Расстояние от E до C равно 5, а до G — 9. Выбирается вершина C и ребро EC.
	{A,B,C,D,E,F}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (E,G) = 9 V (F,E) = 8 цикл (F,G) = 11	{G}	Единственная оставшаяся вершина — G. Расстояние от F до нее равно 11, от E — 9. E ближе, поэтому выбирается вершина G и ребро EG.
	{A,B,C,D,E,F,G}	(B,C) = 8 цикл (D,B) = 9 цикл (D,E) = 15 цикл (F,E) = 8 цикл (F,G) = 11 цикл	{}	Выбраны все вершины, минимальное остовное дерево построено (выделено зеленым). В этом случае его вес равен 39.

Алгори́тм Бору́вки — это алгоритм нахождения минимального остовного дерева в графе.

Впервые был опубликован в 1926 году Отакаром Борувкой в качестве метода нахождения оптимальной электрической сети в Моравии. Несколько раз был переоткрыт, например Флореком, Перкалом и Соллином. Последний, кроме того, был единственным западным ученым из этого списка, и поэтому алгоритм часто называют алгоритмом Соллина, особенно в литературе по параллельным вычислениям.

Алгоритм:

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

В псевдокоде, алгоритм можно описать так:

1. Изначально, пусть   — пустое множество ребер (представляющее собой остовный лес, в который каждая вершина входит в качестве отдельного дерева).

2. Пока   не является деревом (что эквивалентно условию: пока число рёбер в   меньше, чем  , где   — число вершин в графе):

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

Добавим все найденные рёбра в множество  .

3. Полученное множество рёбер   является минимальным остовным деревом входного графа.