Отыскание двусвязных компонент

В этом параграфе мы рассмотрим применение поиска в глубину к выделению 2-связных компонент графа. Здесь дело обстоит не так просто, как в предыдущей за­даче. Конечно, можно было бы, удаляя поочередно вер­шины графа и каждый раз выделяя связные компоненты, найти его точки сочленения и блоки. Такой подход, од­нако, приводит к алгоритму сложности по крайней мере O(|EG|*|G|)Использование более глубоких свойств ПГ позволяет получить линейный по сложности алгоритм решения этой задачи.

В дальнейшем удобно использовать следующие терми­ны. Пусть D=(V, А)—ориентированное дерево, х, у € V. Назовем х отцом вершины у, а у — сыном верши­ны х, если дуга (х, у) принадлежит А. Будем говорить, что вершины хиу сравнимы, если одна из них достижи­ма из другой. Если при этом у достижима из х, то х — предок вершины у, а у — потомок вершины х. Подграф графа D, порожденный множеством, состоящим из верши­ны у и всех ее потомков, будем обозначать через D_v и называть поддеревом с корнем у.

Пусть в графе G проделан поиск в глубину из верши­ны v₀ и получены остовное глубинное дерево Т и множе­ство обратных ребер В.

Следующие три утверждения дают теоретическую ос­нову для разработки эффективного алгоритма выделения двусвязных компонент.

Утверждение 74.1. Если дуга (х, у) принадле­жит В, то х является потомком вершины у в Т.

Надо доказать, что вершина х принадлежит подде­реву Т_у. Предположим противное. Согласно утверждению 73.2 вершина х получает свой ПГ-номер позже, чем у. Поэтому присвоение вершине х ПГ-номера произойдет не раньше, чем будут посещены все вершины дерева Т_у и произойдет возвращение в вершину s = F(y). Но возвра­щение в s не может произойти прежде, чем все вершины множества N_y получат ПГ-номера. Поскольку х € N_y и ПГ-номера к этому моменту не имеет, то получаем противоречие.

Утверждение 74.2. Вершина vo является точкой сочленения графа G тогда и только тогда, когда она име­ет не менее двух сыновей.

Пусть v₀ — точка сочленения графа G. Ясно, что каждый блок графа, включающий вершину v₀, содержит по крайней мере одного из ее сыновей.

Пусть теперь s₁ , s₂, ..., s_k — сыновья вершины v₀. Рассмотрим поддеревья T_Si (i = 1, k). Ясно, что VG— v₀ = U VT_Si. Для доказательства несвязности графа G — v₀ достаточно показать, что в этом графе нет ребер, связывающих вершины различных T_Si. Но это сразу сле­дует из утверждения 74.1.

Будем говорить, что х — собственный предок (пото­мок) вершины у, если х — предок (потомок) у и х ≠ у.

Утверждение 74.3. Вершина v≠v₀ является точ­кой сочленения графа G тогда и только тогда, когда для некоторого сына s этой вершины не существует дуги (х, у) € В такой, что х — потомок (не обязательно соб­ственный) вершины s, а у — собственный предок вер­шины v.

Пусть v — точка сочленения графа G и G₁, G₂, ..., G_m, m ≥ 2,— блоки этого графа, содержащие верши­ну v. Пусть, далее, v' = F(v), т. е. v' — отец вершины v.Не теряя общности считаем, что вершина v' содержится в блоке G₁. Каждый из остальных блоков G_i(i = 2, m)должен, очевидно, содержать хотя бы одну вершину, яв­ляющуюся сыном вершины v. Пусть, например, s — сын
вершины v и s € G₂. Если теперь допустить существование «обратного» ребра ab (т. е. дуги (а, b)€ В) такого, что а — потомок s, а b — собственный предок вершины v,то придем к существованию в графе G простого цикла,содержащего вершины v' и s. Этот цикл образован простой (а,b)-цепью, состоящей из «прямых» ребер и «об­ратного» ребра ab. Это означает (согласно утвержде­нию 36.3), что вершины s и v' принадлежат одному бло­ку. Получили противоречие.

Докажем теперь вторую часть утверждения. Пусть вершина s является сыном вершины v, для которого выполняется условие, фигурирующее в формулировке ут­верждения. Это условие вместе с утверждением 74.1 озна­чает, что если ab—«обратное» ребро и а € Т_а, то либо b € Т_а, либо b = v. Последнее означает, что все ребра графа G, связывающие вершины множества VT_а с верши­нами VG\VT_а, инцидентны вершине v, т. е. v-—точка со­членения графа G.

Перейдем теперь непосредственно к разработке алго­ритма выделения блоков графа. Чтобы уяснить схему применения ПГ к решению этой задачи, обратимся к при­меру.На рис.74.1 изображен граф «с точностью до бло­ков». ПГ начинается в вершине v₀. После нескольких ша­гов придем в одну из точек сочленения графа, например, в c₂. Пусть, далее, выбирается и помечается как «прямое» ребро c₂x блока В₄. После этого дальнейшая работа ПГ вплоть до возвращения в c₂ происходит точно так, как если бы было v₀ = c₂ и блоков В₁, В₂, В₃ в графе G не было бы вовсе. Поэтому возвращение в Сг из х будет оз­начать, что пройдены все ребра блоков В₄ , В₅, В₆.,В₇ .Таким образом, возвращение в c₂ произойдет позже, чем возвращения в c₃ и c₄ из висячих блоков В₅, В₆.,В₇. Эти рассмотрения приводят к следующему важному выводу. Самое первое возвращение в точку сочленения произой­дет сразу же после завершения обхода всех ребер некото­рого висячего блока В_к. Это же справедливо и по отно­шению к дальнейшему поведению ПГ в графе, получен­ном из графа G удалением блока B_h.

Покажем, как использовать сказанное выше в пред­положении, что у нас есть способ, позволяющий при каждом возвращении из вершины v в F(v) определять, является ли F(v) точкой сочленения. С этой целью заве­дем стек S, в который будем заносить всякое ребро гра­фа G сразу после получения им пометки «прямое» или «обратное». Таким образом, все ребра добавляются в конец списка S. Пусть в нашем примере возвращение из вершины у в c₄ (см. рис. 74.1) является самым первым возвращением в точку сочленения. Тогда к моменту воз­вращения в c₄ ребра блока В₆ будут занимать все t по­следних мест в стеке S, где t — число ребер этого блока. Важно при этом, что ребро c₄ у занимает первое среди t указанных мест. Это позволяет, просматривая стек S справа налево, выделить (т. е., например, переместить з отдельный список) все ребра блока В₆. Затем эти ребра удаляются из S.

Итак, учитывая сказанное, необходимо уметь в про­цессе ПГ быстро определять возвращение в вершину, являющуюся точкой сочленения. Утверждения 74.2 и 74.3 дают соответствующие критерии, и нам надо их «алгорит­мизировать». С этой целью для каждой вершины v € VG шределим множество P(v). В это множество включим вершину v и каждого ее предка w, для которого существует «обратное» ребро xw такое, что х — потомок вершины v в остовном глубинном дереве Т. Иными словами, множество P(v) состоит из всех предков вершины v, которых можно достичь из v, проходя сначала несколько (возможно, ни одной) дуг дерева Т, а затем одну дугу множества В.

Введем теперь функцию l(v), v € VG, полагая l(v) = min ПГ(x). Например, в графе на рис. 73.1 l(l) = 1, l(2) = 1, l(3) = l,l(4) = 3, l(5) =1, l(6)=3,l(7)=3.

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

Утверждение 74.4. Вершина v≠v₀ является точкой сочленения графа G тогда и только тогда, когда су­ществует такой сын s этой вершины, что l(s)≥ ПГ(v).

Справедливость этого соотношения становится очевид­ной, если заметить следующее. Множество предков вер­шины v, достижимых из нее с использованием дуг дере­ва Т и не более одной дуги из В, состоит из предков v, достижимых таким же способом из вершин s₁, s₂ , ..., s_m и множества вершин, к которым ведут обратные ребра от вершины v.

Используя соотношение (1), функцию l можно вычис­лять попутно с выполнением обычных операций поиска в глубину. При первом посещении вершины v вместе с присвоением ПГ-номера полагаем l(v) = ПГ(v). В даль­нейшем это значение корректируется в соответствии с формулой (1) следующим образом. Всякий раз, когда происходит возвращение в вершину v из некоторого ее сына s, полагаем l(v):=min{l(s), l(v)}. Кроме того, ког­да некоторое ребро vw помечается как «обратное», пола­гаем l(v):=min{l(v), ПГ(w)}. К моменту возвращения из v в вершину x=F(v) будет вычислено истинное зна­чение l(v), которое в дальнейшем используется для кор­ректировки l(х). Существенно, что каждая из этих кор­ректировок требует только O(1) дополнительного време­ни. Поэтому ПГ вместе с вычислением функции l по-прежнему будет выполняться за время O(|EG|+|G|).

Еще одна добавка к «стандартному» поиску в глубину связана с точками сочленения. Для обнаружения точки сочленения достаточно после каждого возвращения в вер­шину v из некоторого ее сына s сравнить величины l(s) и ПГ(v). Если окажется, что l(s) ≥ ПГ(v), то все ребра стека S, начиная с последнего и кончая sv, удаляются из этого списка. Удаленные ребра составляют один из бло­ков графа G. Согласно утверждению 74.4 неравенство l(s) ≥ ПГ(v) означает, что либо вершина v — точка со­членения, либо v = v₀ и v не является точкой сочленения. Заметим, что второй случай не требует особого рассмот­рения. В этом случае удаленные из стека S ребра соот­ветствуют единственному блоку графа, содержащему v₀. И, наконец, последняя деталь. Выделение блока графа G мы понимаем как удаление всех ребер этого блока из стека S. Можно считать, что одновременно с удалением из S каждое такое ребро заносится в некоторый другой список, причем множество ребер разных блоков разделе­ны в этом списке, например, символом 0. Процедура по­строения этого нового списка очевидна, и чтобы не за­громождать описания алгоритма, мы не приводимее в явном виде.

Сравнение l(s) с ПГ(v) производится |G| — 1 раз, и, следовательно, суммарное время, затраченное на выпол­нение сравнений, составляет O(|G|). Каждое ребро гра­фа один раз включается в стек S и один раз исключается из него. Поэтому вся работа, связанная с изменением S, выполняется за время O(|EG|). Таким образом, поиск в глубину вместе с выделением блоков будет выполняться за время O(|EG|+|G|).

Алгоритм A2 поиска в глубину с выделением двусвязных компонент.

1.ПГ(v₀):=1, l(v_o):=1, S:=¢, F(v₀):=0, T:=¢, В:= ¢, k :=1,p:= 1, Q(1):= v₀.

2.v:=Q(p).

3.Просматривая список N_v, найти такую вершину w,что ребро vw не помечено, и перейти к п. 4. Если таких вершин нет, то перейти к п. 5.

4. Если вершина w имеет ПГ-номер, то поместить реб­ро vw как «обратное», занести ребро vw в стек S, l(v): = min{l(v), ПГ(w)} [выполнена корректировка l(v)].Перейти к п. 3 и продолжить просмотр списка N_v. Иначе ребро vw пометить как «прямое», k := k + 1, ПГ(w):=k,l(w):=k, F(w):= v,p:=p + 1, Q(p):= w. Перейти к п. 2.

5. р := р — 1. Если р = 0, то конец. Иначе перейти к п. 6.

6.Пусть x = F(v). Если l(v)> ПГ(x), то перейти к п. 7. Иначе l(x):= {l(x), l(v)} [выполнена корректи­ровка 1{х)]и перейти к п. 2.

7.Удалить из стека S все ребра вплоть до xv [уда­ленные ребра составляют блок графа G]. Перейти к п. 2.

Пример. На рис. 74.2 изображен граф G и приве­дены списки смежности его вершин. Этот граф имеет че­тыре блока В₁ , В₂ , В₃ , В₄ и две точки сочленения d и х. Поиск в глубину начинается с вершины α, т. е. v_o=α. На рис. 74.3 отражена ситуация, сложившаяся непосред­ственно перед выделением блока В₄. К этому моменту шесть ребер помечены как «прямые» и одно как «обрат­ное». Прямые ребра проведены жирными линиями, а об­ратное — пунктирной. Тем и другим придана соответ­ствующая ориентация. Помеченные ребра расположены в стеке S в том порядке, в котором они получали помет­ки. Пара чисел (α, β), приписанная вершине v, имеет сле­дующий смысл: α = ПГ(v), a β — значение l(v), вычис­ленное к рассматриваемому моменту.

из вершины z в х обнаруживается, что l(z) = 5= ПГ(x). Следовательно, все ребра от tx до xz в стеке S составля­ют блок графа G. Эти ребра —tx, tz, xz — удаляются из S, и тем самым выделен блок В₄..

После этого алгоритм работает так, как если бы бло­ка В₄. в графе G не было вообще. Ключевые моменты

В заключение отметим, что поиск в глубину оказывается полезным и при отыскании 3-связных компонент графа. Известен основанный на поиске в глубину алгоритм, решающий эту задачу за время O(|EG|+|G|).

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

Задача о минимальном остове состоит в отыскании остова минимального веса во взвешенном графе (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, найдется такой, вес которого не более веса любо­го остова, содержащего Т.

С другой стороны, граф 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} и т. д.

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

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

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

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

2.

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, означают

Если граф 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|).

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

Кратчайшие пути

Пусть G=(V, A)—ориентированный взвешенный граф. Задача о кратчайшем пути состоит в отыскании пу­ти минимального веса, соединяющего заданные началь­ную и конечную вершины графа G при условии, что хо­тя бы один такой путь существует. Начальную и конеч­ную вершины обозначим соответственно через s и t; (s, t)-путь минимального веса будем называть кратчай­шим (s, t)-путем.

Вначале рассмотрим случай, когда веса всех дуг гра­фа неотрицательны, т. е. w(e) ≥ 0 для каждой дуги е € А. В этом случае решение задачи о кратчайшем пути явля­ется существенно менее трудоемким, чем в общем случае. Первый эффективный алгоритм построения кратчайшего пути в графе с неотрицательными весами дуг предложил Е. Дийкстра в 1959 г.

На каждой итерации этого алгоритма всякая вершина и графа G имеет метку l(v), которая может быть посто­янной либо временной. В первом случае l(v) — вес кратчайшего (s, v)-пути. Если же метка l(v) временная, то l(v)—вес кратчайшего (s, v)-пути, проходящего только через вершины с постоянными метками. Таким образом, временная метка l(v) является оценкой сверху для веса кратчайшего (s, v) -пути, и став на некоторой итерации постоянной, она остается такой до конца работы алгорит­ма. Кроме l(v), с каждой вершиной v графа G, за исклю­чением s, связывается еще одна метка— θ(v). На каждой итерации θ(v) является номером вершины, предшествую­щей v в (s, v) -пути, имеющем минимальный вес среди всех (s, v) -путей, проходящих через вершины, получив­шие к данному моменту постоянные метки. После того как вершина t получила постоянную метку, с помощью меток θ(v) легко указать последовательность вершин, со­ставляющих кратчайший (s, t)-путь.

Перед началом первой итерации алгоритма вершина s имеет постоянную метку l(s)=0, а метки l всех осталь­ных вершин равны ∞ и эти метки временные. Общая итерация алгоритма состоит в следующем. Пусть р — вершина, получившая постоянную метку l(р) на преды­дущей итерации. Просматриваем все вершины v € Г(р), имеющие временные метки, с целью уменьшения (если это возможно) этих меток. Метка l(v) вершины Г(p) заменяется на l(p)+w(p, v), если оказалось, что l(v)>l(p)+ w(p, v). В этом случае говорим, что вершина v получила свою метку l из вершины p, и полагаем θ(v) = p. Если же l(v) ≤ l(p)+ w(p, v), то метки θ и l вер­шины v не изменяются на данной итерации. Алгоритм заканчивает работу, когда метка l(t) становится постоян­ной. Как уже говорилось выше, l(t)—вес кратчайшего (s, t)-пути, который будем обозначать через Р*. Этот

где для любой вершины v € VG.

Будем считать, что граф G задан матрицей весов ли­бо списками смежности.

Алгоритм A5 Дийкстры поиска кратчайшего пути.

1. Положить l(s): = 0 и считать эту метку постоян­ной. Положить l(v):=∞ для всех v € VG,

v≠s, и считать эти метки временными. Положить р := s.

2.

3. Пусть V’ — множество вершин с временными мет­ками l. Найти вершину v*, такую что

Считать метку l(v*) постоянной меткой вершины v*.

4. p:=v*. Если p = t, то перейти к п. 5 [l(t)—вес кратчайшего пути]. Иначе перейти к п. 2.

5. P*:=(s, ..., θ³(t), θ²(t), θ(t), t) [P*- кратчай­ший путь]. Конец.

Прежде чем перейти к обоснованию алгоритма, сде­лаем три полезных замечания.

Замечание 1. Как легко видеть, алгоритм A5 применим к смешанным и, в частности, к неориентиро­ванным графам. Для этого достаточно каждое неориенти­рованное ребро uv графа, имеющее вес w(u, v), рассмат­ривать как пару дуг (и, v) и (v, и) того же веса.

Замечание 2. Если п. 4 модифицировать так, чтобы алгоритм заканчивал работу только после получения всеми вершинами постоянных меток, то он будет строить кратчайшие пути из s в каждую из остальных вершин. Если к тому же вместе с превращением метки вершины v* в постоянную (п. 3 алгоритма) заносить дугу (θ(v*), (v*) в множество А*, то после окончания работы алгоритма граф D=(VG, А*) будет корневым ориентированным остовным деревом. Это дерево называют деревом ратчайших путей из s графа G. Для любой вершины v € VG единственный (s, v)-путь в дереве D является кратчайшим (s, v) -путем в графе G.

Замечание 3. Алгоритм A5, модифицированный так, как указано в замечании 2, можно рассматривать как алгоритм построения дерева D кратчайших путей из вершины s графа G. С этой точки зрения алгоритм A5 аналогичен алгоритму A3 построения минимального остова. Действительно, построение дерева D состоит в последовательном увеличении уже построенного фрагмента путемдобавления некоторой дуги, «выходящей» из этого рагмента. При этом метки l и θ играют такую же роль, как и метки α и β в алгоритме A3.

Утверждение 76.1. Алгоритм A5 строит в графе кратчайший (s, t)-путь за время O(|G|²). Заметим вначале, что метка вершины v (l(v)≠∞) равна весу (s, v)-пути, который построен алгоритмом к тому моменту. Он определяется метками θ, имеющимися в заданный момент. Поэтому для доказательства оптимальности (s, t)-пути, соответствующего постоянной мет­ке l(t), достаточно доказать, что постоянная метка l(v) каждой вершины v равна весу кратчайшего (s, v)-пути. Это утверждение будем доказывать по индукции. Пусть вершина v получила свою постоянную метку на k-й ите­рации, т. е. после k-говыполнения п. 3. При k = 1 спра­ведливость утверждения очевидна. Предположим, что оно верно для вершин, получивших свои постоянные метки на итерациях 2, 3, ..., k — 1. Обозначим через Р° (s, v)-путь, построенный алгоритмом в результате k итераций, а через Р* — кратчайший (s, v)-путь. По условию w(P°)= l(v). Пусть V1 и V2 — множества вершин, име­ющих соответственно постоянные и временные метки пе­ред началом k-йитерации. Рассмотрим две возможные ситуации:

т. е. Р° — кратчайший (s, v) -путь.

Таким образом, и в случае б) верно неравенство w(P⁰) ≤ w(P*), т. е. Р° — кратчайший (s, v)-путь.

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

построение пути с помощью меток θ можно осуществить, потратив не более O(|G|) операций. Таким образом, вцелом время построения кратчайшего (s, t) -пути не превосходят O(|G|²).

Пример 1. На рис. 76.1 изображены пятькопий G_k(k — 1,5) графа G, каждая из которых отражает ситуа­цию, сложившуюся после очередной итерации алгоритма. Около каждой дуги написан ее вес. Вершинам копии G_k (k = 1, 5) приписаны метки, полученные ими в результате выполнения первых k итераций. Некоторые дуги обведены жирными линиями, т. е. отмечены. Добавление такой дуги (а, b) при переходе от G_k к G_k+1 означает, что вершина b получила свою метку l(b) из а и эта мет­ка стала постоянной на (k+1)-йитерации. Вершина t в нашем примере получает постоянную метку последней, и отмеченные дуги Gs образуют дерево кратчайших пу­тей из s.

При решении многих задач возникает необходимость отыскания в невзвешенном графе (s, t)-пути с минималь­ным количеством дуг. Такой путь, очевидно, можно най­ти с помощью алгоритма Дийкстры. Для этого достаточ­но присвоить всем дугам графа G веса, равные 1, и при­менить алгоритм A5. Проследим работу алгоритма в этой ситуации, обращая особое внимание на последователь­ность, в которой вершины графа G получают постоянные метки. Очевидно, что вначале постоянные метки l=1 получат все вершины множества Г (s). Затем метка l = 2 будет присвоена концам дуг, выходящих из Г (s). Вооб­ще, постоянную метку l=k получают еще не помечен­ные вершины, являющиеся концами дуг, исходящих из вершин с метками l= k - 1. Этот процесс обхода (и при­своения меток) вершин графа называют поиском в ши­рину в графе (на интуитивном уровне поиск в ширину описан в § 9). По окончании поиска в ширину метка l(х) вершины х равна минимальному числу дуг в (s, x)-пути. Как и ранее, сам этот путь определяется метками θ. Осуществление поиска в ширину с помощью алгорит­ма Дийкстры связано, как мы знаем, с вычислительными затратами O(|G|²).

Рассмотрим алгоритм A6, осуществляющий поиск в ширину за время O(|EG|). В этом алгоритме метки l и θ играют ту же роль, что и в предыдущем, с той, одна­ко, разницей, что метки l не делятся на временные и постоянные. Как только вершина х получает метку l(х)≠∞, эта метка сразу становится постоянной (т. е. окончательной). За счет этого, в частности, достигается экономия времени вычислений по сравнению с алгорит­мом Дийкстры.

Особую роль в алгоритме A6 играет список Q. Каж­дая вершина графа один раз заносится в этот список иодин раз из него вычеркивается. При этом вычеркива­ется все время первая (на данный момент) вершина этого списка, а только что добавленная вершина всегда является последней в списке, т. е. Q — очередь. Вначале в Q находится единственная вершина s, l(s)=0, а все остальные вершины меток не имеют. Общая итерация состоит в следующем. Выбирается первая вершина х в списке Q. Каждой непомеченной вершине у €Г(х) при­сваиваются метки l(у)= l(х)+ 1 и θ(y)=x, после чего вершина у становится последней в списке Q, а вершина х удаляется из Q. Алгоритм прекращает работу, как только в Q не останется ни одной вершины. При этом вершины, достижимые из s, будут иметь метки, а недо­стижимые — нет. Для быстрого выполнения операций вы­черкивания и включения элементов в Q используются переменные указатели р и q — адреса первой ипослед­ней занятых ячеек списка Q соответственно.

Будем считать, что граф G задан списками смежно­сти и N_v — список, содержащий концы всех дуг, исхо­дящих из вершины v.Алгоритм A6 поиска в ширину.

1. Q (1):=s, p:=1, q:=1, l(s):=0.

2. х := Q(p), m := |Г(х)|I [выбрана первая вершина х очереди Q].

[Пп. 3—5 — присвоение меток непомеченным верши­нам из Т(х)].

3. k:=1.

4. Если вершина у = N_x(k) имеет метку, то перейти к п. 5. Иначе l(y):= 1(х)+ 1, θ(y):=x, q:=q+1,Q(q):=y [вершина у помечена и включена в очередь Q]и перейти к п. 5.

5. Если k= т, то перейти к п. 6, иначе k:=k + 1 и перейти к п. 4.

6. р := р + 1 [вершина х исключена из Q].

7. Если р> q, то конец [Q = ¢, т. е. все вершины,достижимые из s, получили метки], иначе перейти к п. 2.

Утверждение 76.2. Алгоритм A6 присваивает метки l и θ всем вершинам графа, достижимым из вер­шины s за время O(|EG|). При этом (s, ..., θ³(x), θ²(x), θ(x), х) — (s, х)-путь с минимальным числом дуг, а l(х)— число дуг в этом пути.

Основные вычислительные затраты связаны с вы­полнением п. 3 алгоритма. Суммарное время выполнения этого пункта составляет , поскольку каждый из списков N_v просматривается в точ­ности один раз. Затраты на выполнение других пунктов, очевидно, не превосходят этой величины.

Выше отмечалось, что результаты алгоритма A6 (т. е. метки l и θ) те же, что и в алгоритме Дийкстры, если каждой дуге графа G приписать вес, равный 1. Поэтому справедливость второго утверждения следует из утвер­ждения 76.1.

Замечание 4. Иногда требуется искать пути из вершин множества X € VG во все остальные вершины. Для решения этой задачи достаточно слегка модифици­ровать алгоритм A6 изменив в нем п. 1. Именно, в спи­сок Q следует поместить все вершины множества X и положить l(х)=0 для каждой вершины х € Х. На мо­дифицированный таким образом алгоритм A6 будем ссы­латься как на поиск в ширину из множества X.

Перейдем теперь к рассмотрению общей ситуации, Будем считать, что в графе G допускаются дуги отрица­тельного веса. Предлагаемый ниже алгоритм A7 строит в таком графе кратчайшие пути между всеми парами вершин графа при условии, что в графе нет отрицатель­ных контуров (контуров отрицательного веса). Если же такой контур в графе имеется, то алгоритм сообщает об этом и прекращает работу, оставляя задачу отыскания кратчайшего пути нерешенной (см. ниже замечание 6). Будем считать, что граф G, |G|=n, задан матрицей весов W = |W_ij|, т. е. W_ij = w(i, j), если (i, j) € AG, и Wij=∞ в противном случае. Кроме того, полагаем W_u = 0 для всех i=l, 2, ..., п. Алгоритм основан на следующих соображениях. Пусть i, j, k — три любые вер­шины графа G, и мы хотим получить (i,j)-путь, крат­чайший среди (i,j)-путей, не содержащих внутренних вершин, отличных от k. Очевидно, что для этого доста­точно выбрать меньшую из двух величин W_ij и W_ij+ W_kj, которая и будет весом такого (i,j)-пути. Если зафиксировать k и проделать эту операцию (назовем ее t-операцией, примененной к индексу k) для всех пар (i, j), то получим матрицу W = ||W’_ij||. У которой W’_ij= min {Wij, Wik + Wkj}. Оказывается (это будет позднее доказано), имея матрицу W^s весов кратчайших путей, проходящих только через вершины множества S € VG, можно получить такую же матрицу для путей, проходя­щих через множество S U {m}, m¢ S. Для этого достаточно применить t-операцию к индексу т ивсем эле­ментам матрицы W^s. Именно в этом и состоит итерация алгоритма A7, который, начиная с W° = W, строит та­кую последовательность матриц W°, W¹, ..., Wⁿ, что W^m получается из W^m-1 применением t-операции к индексу ти матрице W^m-1. Если в графе G нет отрицательных контуров, то элемент W_ij^m матрицы W^m при каждом травен весу кратчайшего (i, j)- пути, все внутренние вер­шины которого принадлежат множеству {1, 2, ..., т}. Таким образом, последняя из этих матриц, Wⁿ, содержит веса кратчайших путей между всеми парами вершин графа. Для того чтобы после окончания работы алгорит­ма иметь возможность быстро найти кратчайший путь между любой парой вершин, будем на k-йитерации вме­сте с матрицей W^k строить матрицу Р^k = | |P_ij||. Вначале полагаем P_ij⁰ = i(i,j= 1, п). Далее, на k-йитерации по­лагаем P_ij^k= P_ij^k-1если W_ij^k = W_ij^k-1 и P_ij^k= P_kj^k-1, если W_ij^k = W_ik^k-1 + W_kj^k-1. Таким образом, P_ij^k —номер верши­ны, предшествующей вершине j в текущем (i, j)- пути, т. е. в кратчайшем (i, j)- пути, все внутренние вершины которого содержатся в множестве (1, 2, ..., k). Матрица Р^п = || P_ijⁿ || играет ту же роль, что и метки θ в пре­дыдущих алгоритмах A5 и A6. С помощью этой матри­цы кратчайший (i, j)- путь L(i, j) определяется следу­ющим образом: L(i, j) = (i, ..., j₃, j₂, j₁, j), где j₁ = P_ijⁿ, j₂ = P_ij1ⁿ, j₃ = P_ij2ⁿ

Алгоритм A7 отыскания кратчайших путей между всеми парами вершин.

1. W⁰:=W, k:=1, P°:= ||P_ij⁰|| где P_ij⁰=i если Wij ≠ ∞, и P_ij⁰ =0 в противном случае.

2. Выполнить для всех (i, j)=1,n если W_ij^k-1< W_ik^k-1 + W_kj^k-1, то W_ij^k = W_ij^k-1 , P_ij^k= P_ij^k-1. Иначе W_ij^k := W_ik^k-1 + W_kj^k-1, P_ij^k := P_kj^k-1 .

3. Если для некоторого l, 1≤ l ≤ n, то конец [в графе имеется отрицательный контур]. Иначе перейти к п. 4.

4. k:=k+1. Если k = n +1, то конец [Wⁿ= || W_ijⁿ || —матрица весов кратчайших путей, определяемых с по­ мощью матрицы Р^п = || P_ijⁿ ||].

Замечание 5. Алгоритм будет применим к сме­шанным графам, если каждое неориентированное ребро заменить на две дуги того же веса (см. замечание 2).При этом следует учесть, что неориентированное ребро отрицательного веса сразу приводит к отрицательному контуру.

Замечание 6. Алгоритм «отказывается» строить кратчайшие пути, когда в графе G имеются отрицатель­ные контуры. В этом случае задача отыскания кратчай­шего пути между двумя вершинами (или между всеми парами вершин) остается корректной, но становится очень трудной. Можно показать, что она не менее труд­на, чем, например, задача о коммивояжере.

Перейдем теперь к обоснованию алгоритма A7 и оцен­ке его трудоемкости.

Утверждение 76.3. Пусть взвешенный ориенти­рованный мулътиграф L имеет эйлерову цепь, соединя­ющую вершины а и b. Если в L нет отрицательных кон­туров, то в нем имеется такой (а, b)-путъ Р, что

w(L) ≥ w(P).

Поэтому вершины а и b принадлежат одной его сла­бой компоненте L", и последняя содержит эйлерову (а, b)-цепь. Продолжая подобным образом, получим тре­буемый (а, b)-путь.

Утверждение 76.4. Если в графе нет отрицатель­ных контуров, то при всех k, i, j = 1, п. W_ij^k — вес крат­чайшего (i, j)-пути, все внутренние вершины которого содержатся в множестве {1, 2, ..., k}.

Доказываем индукцией по k. При k = 1 справедли­вость утверждения очевидна. Предположим, что оно справедливо для 2, 3, ..., k— 1, и рассмотрим W_ij^k. Пусть Р° — кратчайший (i,j)-путь, все внутренние вершины которого принадлежат множеству {1, 2, ..., k}. Если Р° не включает вершину k, то W_ij^k = W_ij^k-1 и, согласно пред­положению индукции, w(P°) = W_ij^k-1 = W_ij^k. Допустим теперь, что Р° содержит вершину k. Обозначим через P₁⁰ и P₂⁰ части пути Р° от i до k и от k до j соответственно. Предположим, что один из этих путей, например P₁⁰, не является кратчайшим, и пусть Р' — кратчайший (i, k)-путь, все вершины которого содержатся в множестве {1, 2, ..., к - 1}. Рассмотрим мультиграф L, получаю­щийся из графа Р' U P₂⁰ заменой каждой дуги, входя­щей одновременно в Р' и P₂⁰, двумя экземплярами этой дуги. Очевидно, что L не содержит отрицательных кон­туров. Поэтому, согласно утверждению 76.3, L содержит такой (i, j)-путь Р, что w(L) ≥ w(P) и, следовательно, w(P°) = w(P₁⁰) + w(P₂⁰) > w(P') + w (P₂⁰) = w(L) ≥ w(P). Это неравенство противоречит минимальности Р°.

Теорема 76.5. Время работы алгоритма A7 не пре­восходит O(|G|³). Если граф G не содержит отрицатель­ных контуров, то W_ijⁿ — вес кратчайшего (i, j)-пути в графе G для всех i, j = 1, п, п=|G|. Если же такие контуры в графе имеются, то существуют такие числа т. иl,что W_ll^m <0.

Справедливость первого утверждения теоремы оче­видна, поскольку каждая из не более чем |G| итераций выполняется за время O|G|².

Второе утверждение теоремы непосредственно следует из утверждения 76.4.

Допустим теперь, что граф G содержит отрицательные контуры. Пусть m — такой наименьший индекс, что для некоторой вершины l в графе G имеется отрицательный контур S, содержащий только l и некоторые вершины множества (1, 2, ..., m). Ясно, что контур S включает вершину т. Тогда при любых i,j = 1, п число W_ij^m-1 равно весу кратчайшего (i, j)-пути, все внутренние вер­шины которого принадлежат множеству {1, 2, ..., m—1}. Доказательство этого факта дословно повторяет доказа­тельство утверждения 76.4. Контуру S соответствуют (l, m)-путь P₁ и (т, 1)-путь P₂, такие, что P₁U P₂ = S. Поскольку внутренние вершины путей P₁ и P₂ принадлежат множеству {1, 2, ..., m-1}, то w(P₁)≥ W_ml^m-1 , w(P₂) ≥W_lm^m-1. Следовательно, W_ml^m-1 + W_lm^m-1≤ w (Р₁) + w(P₂) = w(S), т. е. W_ll^m = min {0, W_ml^m-1 + W_lm^m-1}< 0.

Найдем, например, с помощью матрицы Р⁴ кратчайший (2 1)-путь: P₂₁⁴ = 4, P₂₄⁴ = 3, P