§ 75. Минимальный остов

Задача о минимальном остове состоит в отыскании остова минимального веса во взвешенном графе (G, w). Она считается одной из самых «легких» оптимизационных задач на графах. Решение этой задачи можно получить с помощью «жадного» алгоритма, если указать процедуру» которая по любому ациклическому множеству ребер X € EG и ребру е € EG определяет, содержит ли множество ребер X U е цикл графа G. В качестве такой процедуры можно использовать, например, поиск в глу­бину, поскольку выявление цикла в множестве X U е, где е = ab, равнозначно отысканию (a, b) -цепи в порожден­ном подграфе G(X). В процессе работы «жадного» алго­ритма эта процедура выполняется не более |Е| раз, и, следовательно, затраты времени составят O(|EG|•|G|). Для упорядочения множества EG по неубыванию весов известны алгоритмы сложности O(|EG|log|G|). Таким образом, даже бесхитростная реализация «жадной» стра­тегии поиска минимального остова приводит (независимо от способа задания графа G) к алгоритму сложности O(|EG|•|G|), т. е. к полиномиальному алгоритму. С этой точки зрения задача о минимальном остове дей­ствительно является легкой.

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

Пусть T = {( T₁, V₁,), (V₂, T₂), ...,(V_k, T_k)}-остовный лес взвешенного графа G, V_i и Т_i — множества вер­шин и ребер i-й компоненты леса Т, w(x, у)—вес ребра ху графа G. Оба алгоритма построения минимального остова опираются на следующую простую теорему.

Теорема 75.1. Пусть ребро аb имеет минимальный вес среди всех ребер, у которых ровно один конец содер­жится в VT₁. Тогда среди остовов графа G, содержащих Т U ab, найдется такой, вес которого не более веса любо­го остова, содержащего Т.

Пусть Т' — произвольный остов графа G, содержа­щий T и не содержащий ребра аb. Добавим это ребро к Т'. Полученный граф будет содержать цикл S (теоре­ма 13.1). Этот цикл включает ребро ab и по крайней ме­ре еще одно ребро а'b', у которого ровно один конец со­держится в V₁. По условию w(a, b)≤(a', b'). Следо­вательно,

С другой стороны, граф T’+ab — a’b' является остовом графа G, содержащим Т U ab.

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

Теорема сразу подсказывает следующую стратегию построения минимального остова. На первом шаге рас­смотрим остовный лес Т¹ с n=|G| компонентами. Каж­дая его компонента состоит из одной вершины, т. е. V_i¹ = {v_i}. Этот лес, очевидно, содержится в любом остове графа G. Среди ребер, инцидентных v_i , выберем ребро минимального веса v₁v_x1 и присоединим его к Т¹. Согласно теореме 75.1 существует минимальный остов, содержащий лес Т² = Т¹ U {v₁v_x1}, у которого компонента (V₁², T₁²) cодержит две вершины v₁ и v_x1 и ребро v₁v_x1k ,а остальные компоненты одновершинные. На следующем шаге будет выбрано и добавлено к Т² ребро минимального веса среди ребер, соединяющих, {v_{1 ,}v_x1} с VG\{v₁, v_h1} и т. д.

Итак, стратегия построения минимального остова совершенно ясна: на каждом шаге присоединяется ребро, минимальное по весу среди ребер, соединяющих уже построенный фрагмент минимального остова с вершинами, еще не включенными во фрагмент. Нам остается только позаботиться об экономной реализации шагов этого про­веса. С этой целью свяжем с каждой вершиной х € VG. Две метки α (х) и β(х), смысл которых заключается в следующем. Пусть проделано k шагов и (V₁^k, T₁^k) — фрагмент минимального остова, построенный к этому моменту, т. е. это компонента леса, к которой на предыдущих этапах присоединялись ребра минимального веса. Тогда

Таким образом, α (х) — вес минимального по весу ребру, соединяющего вершину х с построенным фрагментом мимального остова, а β(х)—имя второй вершины это-ребра. Метки α(х) и β(х) позволяют быстро находить в каждом шаге ребро минимального веса. Кроме того, после присоединения очередной вершины v к фрагменту ветки легко подкорректировать. Для этого достаточно сравнить «старое» значение α(х) с w(v, x) и выбрать из них меньшее в качестве «нового» значения α(х).

В приводимом ниже описании алгоритма построения минимального остова помимо α(х) и β(х) использованы следующие обозначения: VT, ЕТ — множества вершин и ребер строящегося фрагмента минимального остова; N_x —окружение вершины х; |G| = п. Граф G задан матри­цей весов.

Алгоритм A3 построения минимального остова.

1. Положить ЕТ := ¢, VT := {а}, где а — любая вершина из VG. Каждой верщине х ≠ а приписать метки α(х)= w(x, а), если x €N_a, и α(x)= ∞, если x ¢ N_a, β(x) = а.

2. [отыскание вершины, «ближайшей» к фрагменту].Выбрать вершину v* € VG\VT согласно условию

3. [увеличение фрагмента]. Пусть v‘= β(v *). Изме­нить VT и ЕТ, полагая VT := VT U {v*}, ЕТ : = ET U v'v*.

4. Если |VT| = n , то конец. Ребра, находящиеся в множестве ЕТ, составляют минимальный остов.

5. Для каждой вершины v € N_v* ∩ (VG\VT) из­менить метки следующим образом. Если α(v)> w(v*, v),то α(v):= w(v*, v), β(v):= v*. Если же а(v) ≤ w(v*, v),то метку вершины v не менять. Перейти к п. 2.

Утверждение 75.2. Алгоритм A3 строит мини­мальный остов за время O(|G|²).

Так как всякий раз к ЕТ добавляется ребро, один конец которого принадлежит VT, а другой нет, то граф Т = (VT, ЕТ) на каждом шаге является деревом. После завершения работы алгоритма это дерево будет остовным, поскольку алгоритм прекращает работу только если VT = VG.

Докажем минимальность остова Т. Для этого достаточ­но доказать, что после k-го (k = 1, п— 1) выполнения п. 3 алгоритма граф Т^к = (VT^h, ET^h) содержится в неко­тором минимальном остове. Доказывать будем индукцией по k. При k = 1 наше утверждение непосредственно сле­дует из теоремы 75.1. Предположим, что оно справедливо для некоторого k > 1, т. е. граф Т^к, построенный в ре­зультате k выполнений п. 3, содержится в некотором минимальном остове. Учитывая правило выбора ребра е для присоединения к T^h, применим теорему 75.1. Полу­чим, что граф T^h+1 = Т^к U е, построенный в результате (k + 1)-го выполнения п. 3, также содержится в некото­ром минимальном остове.

Выясним теперь быстродействие алгоритма. Однократ­ное выполнение п. 2 требует времени не более O(|G|). Столько же времени достаточно для обновления меток в п. 5, а п. 3 и п. 4 выполняются за время O(1). Посколь­ку каждый из пп. 2—5 выполняется п — 1 раз, то оценка трудоемкости алгоритма — O(|G|²).

Пример 1. На рис. 75.1 изображены граф G и по­следовательность Тⁱ (I = 1, п — 1) фрагментов минималь­ного остова, получающихся после каждой итерации алго­ритма. Числа, приписанные ребрам графа G, означают

веса этих ребер. Каждой вершинех, еще не вошедшей в Тⁱ приписана пара чисел [α(x), β(x)], которыми она помечена в результате i-го выполнения п. 5 алгоритма.

Если граф G задан матрицей весов, то всякий алго­ритм построения минимального остова в таком графе бу­дет иметь сложность не менее чем O(|G|²), поскольку он, согласно замечанию 1, должен просматривать все эле­менты матрицы весов. Следовательно, в этой ситуа­ции алгоритм A3 имеет неуменьшаемую по порядку тру­доемкость. Если же граф G задан списком ребер либо списками смежности и |EG| существенно меньше чем |G|², то быстродействие алгоритма A3 далеко от опти­мального. Другими словами, алгоритм A3 недостаточно эффективен в применении к «редким» графам, т. е. к гра­фам, слабо насыщенным ребрами.

Рассмотрим еще один алгоритм построения минималь­ного остова, ориентированный на работу именно с такими графами. Этот алгоритм (алгоритм A4), как и предыду­щий, опирается на теорему 75.1, однако более полно использует предоставляемые ею возможности. Именно, ес­ли в алгоритме A3 ребро присоединяется всякий раз к одной и той же компоненте леса, то в алгоритме A4 реб­ра присоединяются к каждой компоненте.

Пусть T = {( V₁, Т₁), ..., (V_p, T_p)} — остовный лес графа G. Назовем ребро аb минимальным по весу для компоненты (V_l ,T_l),1 ≤ l ≤ p, если a € V_l ,b¢ V_l и w(a,b)=min w(x,y). Будем говорить, что М = М(Т) - множество минимальных по весу ребер для ле­са T, если для каждого l = 1, р множество М содержит хотя бы одно минимальное по весу ребро для компонен­ты (V_l ,T_l) и, кроме того, М — минимальное по включе­нию множество, обладающее этим свойством.

Утверждение 75.3. Если М — множество мини­мальных по весу ребер для T={( V₁, Т₁), ..., (V_p, T_p)}, то граф Т' = Т + М не содержит циклов.

Доказываем от противного. Предположим, что Т со­держит цикл S, который не теряя общности будем счи­тать простым. Пусть a₁b₁ , a₂b₂ , ... , a_lb_l — ребра множе­ства S ∩ М, выписанные в той последовательности, как они расположены в цикле S. Этой последовательности соответствует последовательность компонент (V_k1, T_k1), (V_k2 , T_k2) , ..., (V_kl , T_kl) леса Т, такая, что а₁ € V_k1, b₁ € V_k2, a₂ € V_k2 , b₂ € V_k3 , ..., а_l € V_kl , b_l € V_kl.. Выберем среди ребер а_ib_i ( i = 1, l) максимальное по весу. Пусть это будет ребро а₁b₁ . Ясно, что а₁b₁ является минимальным по весу ребром по крайней мере для одной из компонент (V_kl , T_kl) или (V_k2 , T_k2). He теряя общности считаем, что ребро а₁b₁ — минимальное по весу для (V_k1, T_k1). Тогда w(а₁ , b₁)=w(а_i , b_i) и, следовательно, множество M \ а₁b₁ содержит хотя бы одно минимальное по весу ребро для каждой компоненты леса Т. Последнее противоречит минимальности множества М.

Перейдем теперь к изложению алгоритма A4.Этот алгоритм, так же, как и A3, на первой итерации имеет дело с остовным лесом графа G, состоящим из п=|G| одновершинных компонент. Каждая итерация алгоритма состоит в следующем. Вначале строится множество М минимальных по весу ребер для леса Т, полученного в результате предыдущих итераций. (Важно отметить, что сделать это можно за один просмотр элементов множества EG.). Затем с помощью поиска в глубину выделяются связные компоненты графа Т' = Т + М, который соглас­но утверждению 75.2 является лесом. После этого начи­нается следующая итерация с новым лесом Т’ имеющим, очевидно, меньше компонент, чем Т.

В приводимом ниже описании алгоритма A4 исполь­зуются следующие обозначения. Ребра графа G содержат­ся в списке Е, т. е. E(i)—пара номеров концевых вер­шил i-го ребра. Список W содержит веса ребер графа G, т. е. W(i)—вес i-го ребра. Чтобы каждый раз строить множество минимальных по весу ребер для текущего ле­са заюдин просмотр списка Е, используются списки НМР, BMP и КОМП:

НМР (i)—номер минимального по весу ребра для i-й компоненты текущего леса;

BMP (i)—вес этого ребра;

КОМП (j)— номер компоненты текущего леса, содер­жащей вершину j.

Пусть, далее, ЕТ — множество ребер текущего леса Т, а р — число его компонент; Е1 — множество мини­мальных по весу ребер для текущего леса Т.

Алгоритм A4 построения минимального остова.

1. ЕТ:=¢, КОМП(i):=i, ВМР(i):=∞ для i = 1,n , р:= п. [Пп. 2—8 —построение множества Е1 минимальных по весу ребер для леса Т].

2. k:=1.

3. Пусть E(k) = uv; i:=КОМП(u), j:=КОМП(v) [i и j — номера компонент леса, содержащих вершины и и v соответственно].

4. Если i≠ j, то перейти к п. 5, иначе перейти к п. 7.

5. Если w(u, v)= W(k) < BMP (j), то BMP (j): = w(u, v), HMP(j):=k.

6. Если w(u, v)=W{k)<BMP(i), то ВМР(i): =w(u, v), HMP(i):=k.

7. Если k = |EG|, то перейти к п. 8. Иначе k := k +1 и перейти к п. 3. [К моменту выполнения п. 8 первые р элементов НМР содержат номера ребер, составляющих множество минимальных по весу ребер для Т.]

8. Просмотреть первые р элементов массива НМР и сформировать множество Е1 минимальных по весу ребер для леса Т.

9.ET:=ET U Ei [ЕТ — множество ребер «нового» леса Т'].

10. Выделить с помощью алгоритма поиска в глуби­ну связные компоненты графа Т' = Т + E1 [обновлен список КОМП, получено новое значение р].

11. Если р = 1, то конец [ЕТ — множество ребер ми­нимального остова]. Иначе перейти к п. 2.

Утверждение 75.4. Алгоритм A4 строит мини­мальный остов за время O(|EG| log |G|).

Нетрудно убедиться, что после каждого выполне­ния п. 8 множество E1 является множеством минималь­ных по весу ребер для леса Т, рассматриваемого в этот момент. Поэтому согласно утверждению 75.2 граф Т' = Т + Е1 снова является остовным лесом. Это означает,

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

Выясним теперь быстродействие алгоритма A4. Для однократного выполнения каждого из пп. 3—6 достаточ­но времени O(1) и, следовательно, построение Е1 осу­ществляется за время O(|EG|). Таких же затрат доста­точно и для однократного выполнения пп. 8—11. Таким образом, затраты на переход от Т к Т' = Т + Е1 (т. е. на выполнение одной итерации) составляют O(|EG|) опера­ций. Оценим теперь число итераций алгоритма. Посколь­ку одно ребро может быть минимальным по весу не бо­лее чем для двух компонент леса Т, то на каждой итера­ции |Е₁| ≥ р(Т)/2.А так как Т + Е_х — лес,то р(Т+ Е1< <р(Т)/2, т. е. на каждой итерации число компонент уменьшается по крайней мере вдвое. Это означает, что число итераций алгоритма не превосходит log |G|, следо­вательно, он строит минимальный остов за время O(|EG|log|G|).

Пример 2. Применим алгоритм A4 к графу, изо­браженному на рис. 75.2. На первой итерации будет най­дено множество Е1 = { а₁a₂ ,а₁a₃ ,а₄ a₇ ,а₅ a₈ ,а₆ a₉ ,а₉ a₁₀ } ми­нимальных по весу ребер для леса, имеющего одновер­шинные компоненты. Остовные леса, полученные в ре­зультате выполнения 1-й, 2-й и 3-й итераций, изображе­ны на рис. 75.3. Последний из них является минимальным остовом.