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

Задача о минимальном остове состоит в отыскании остова минимального веса во взвешенном графе (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. Последний из них является минимальным остовом.