Алгоритм Штёр — Вагнера

Алгоритм Штёр — Вагнера — это рекурсивный алгоритм для решения задачи о наименьшем разрезе в неориентированных взвешенных графах с ненулевыми весами. Алгоритм предложили Мехтхильда Штёр и Франк Вагнер в 1995. Главная идея этого алгоритма заключается в стягивании графа путём слияния наиболее интенсивных вершин, пока граф не будет содержать всего две комбинированные (результат объединения) вершины^[2]. На каждой фазе алгоритм минимальный s-t разрез для каких-либо двух вершин s и t. Затем алгоритм стягивает ребро между s и t для поиска не содержащего ребра s-t разреза. Наименьший разрез, найденный на всех фазах, и будет минимальным взвешенным разрезом графа.

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

Для вершин ${\displaystyle s,t\in V}$ s-t разрез — это разрез, разделяющий вершины s и t. Минимальный s-t разрез — это s-t разрез с минимальным весом.

Пусть ${\displaystyle G=(V,E,w)}$ будет взвешенным неориентированным графом. Пусть ${\displaystyle (S,T)}$ будет глобальным минимальным разрезом графа G. Предположим, что ${\displaystyle s,t\in V}$. Если в точности одна из вершин s или t принадлежит S, то ${\displaystyle (S,T)}$ также является минимальным s-t разрезом графа G^[3]:95.

Этот алгоритм начинает с поиска минимального s-t разреза ${\displaystyle (S,T)}$ графа G для двух вершин ${\displaystyle \left\{s,t\right\}\in V}$. Для пары вершин ${\displaystyle \left\{s,t\right\}}$ есть две различные ситуации — ${\displaystyle (S,T)}$ является глобальным минимальным разрезом графа G, или они принадлежат одной и той же части глобального минимального разреза графа G. Поэтому глобальный минимальный разрез может быть найден путём проверки графа ${\displaystyle G/\left\{s,t\right\}}$, который является графом после слияния вершин s и t. Во время слияния, если s и t связаны ребром, ребро исчезает. Если и s, и t имеют ребро к некоторой вершине v, то вес ребра из новой вершины st в v равно ${\displaystyle w(s,v)+w(t,v)}$^[3]. Алгоритм описывается следующим образом ^[2]:

• MinimumCutPhase${\displaystyle (G,w,a)}$

   ${\displaystyle A\gets \left\{a\right\}}$
   while ${\displaystyle \ A\neq V}$
       добавляем в A наиболее связанную вершину
   запоминаем cut-of-the-phase 
   и уменьшаем G путём слияния двух вершин, добавленных последними

• MinimumCut${\displaystyle (G,w,a)}$

   while ${\displaystyle |V|>1}$
       MinimumCutPhase${\displaystyle (G,w,a)}$
       if cut-of-the-phase легче, чем текущий наименьший разрез
       then запоминаем cut-of-the-phase как текущий наименьший разрез

Алгоритм работает в несколько фаз. В фазе MinimumCutPhase подмножество A вершин графа растёт, начиная с произвольной отдельной вершины, пока A не станет равным V. На каждом шаге не принадлежащая A вершина, но наиболее тесно связанная с A, добавляется в множество A. Эта процедура может быть формально записана как^[2]: добавляем вершину ${\displaystyle z\notin A}$, такую, что ${\displaystyle w(A,z)=\max\{w(A,y\mid y\notin A)\}}$, где ${\displaystyle w(A,y)}$ является суммой весов всех рёбер между A и y. Таким образом, в отдельной фазе, пара вершин s и t и минимальный s-t разрез C определён^[4]. После одной фазы MinimumCutPhase две вершины сливаются в новую вершину, а рёбра из двух вершин в оставшиеся вершины заменяются ребром с суммой весов предыдущих двух рёбер. Рёбра, соединяющие узлы, удаляются. Если существует наименьший разрез графа G, отделяющий s и t, C является наименьшим разрезом графа G. Если нет, то наименьший разрез графа G должен иметь s и t на одной и той же стороне. Поэтому алгоритм сольёт их в один узел. Кроме того, MinimumCut записывает и обновляет глобальный наименьший разрез после каждого вызова MinimumCutPhase. После ${\displaystyle n-1}$ фаз наименьший разрез будет обнаружен ^[4].

Граф на шаге 1 представляет исходный граф G, а случайно выбранный узел 2 служит стартовым узлом для этого алгоритма. На фазе MinimumCutPhase, множество A содержит лишь узел 2, самое тяжёлое ребро которого — ребро (2,3), так что добавляем узел 3 в A. Теперь множество A содержит узлы 2 и 3, а самым тяжёлым ребром является (3,4), так что в множество A добавляем узел 4. Следуя этой процедуре, последними войдут узел 5 и 1, которые будут вершинами s и t на этой фазе. После их слияния (в узел 15) получим новый граф для шага 2. В этой фазе вес разреза равен 5, что есть сумма весов рёбер (1,2) и (1,5). Первый цикл MinimumCut выполнен.

На шаге 2, начав с узла 2, самым тяжёлым ребром оказывается (2,15), так что узел 15 добавляется в множество A. Следующим самым тяжёлым ребром является (2,3) или (15,6), мы выбираем (15,6), так что узел 6 добавляется в множество. Теперь мы сравниваем рёбра (2,3) и (6,7) и выбираем узел 3 для включения в множество A. Последними двумя узлами будут 7 и 8. Поэтому стягиваем ребро (7,8). Наименьший разрез равен 5, так что он остаётся минимальным.

Следующие шаги повторяют те же самые операции по стягиванию графа, пока не останется только одно ребро. Глобальный наименьший разрез имеет ребро (2,3) и ребро (6,7), которое обнаружено на шаге 5.

Для доказательства корректности алгоритма нам нужно доказать, что MinimumCutPhase даёт фактический минимальный s-t разрез графа, где s и t две вершины, добавлены последними на фазе. Ниже приведена лемма:

Лемма 1: MinimumCutPhase возвращает минимальный s-t разрез графа G.

Мы докажем лемму по индукции по множеству активных вершин. Пусть ${\displaystyle C=(X,{\overline {X}})}$ будет произвольным s-t разрезом, а CP будет разрезом для фазы. Мы должны показать, что ${\displaystyle W(C)\geqslant W(CP)}$. Заметим, что один прогон MinimumCutPhase даёт перестановку всех вершин в графе (где a является первой вершиной, а s и t двумя последними вершинами, добавленными на этой фазе). Мы говорим, что вершина v активна, если ${\displaystyle v\in X}$, вершины перед v в порядке включения вершин, полученном процедурой MinimumCutPhase, входят в ${\displaystyle {\overline {X}}}$, или наоборот. Мы определяем ${\displaystyle A_{v}}$ как множество вершин, добавленных к A до v, а ${\displaystyle C_{v}}$ будет разрезом множества ${\displaystyle A_{v}\cup \{v\}}$, порождённым разрезом C. Для всех активных вершин v

${\displaystyle w(A_{v},v)\leq w(C_{v})}$

Пусть ${\displaystyle v_{0}}$ будет первой активной вершиной. По определению этих двух величин ${\displaystyle w(A_{v_{0}},v_{0})}$ и ${\displaystyle w(C_{v_{0}})}$ эквивалентны. ${\displaystyle A_{v_{0}}}$ — это просто все вершины, добавленные к A до ${\displaystyle v_{0}}$, а рёбра между этими вершинами и ${\displaystyle v_{0}}$, которые пересекают разрез C. Поэтому, как показано выше, для активных вершин u и v (v добавлена в A до u) выполняется

${\displaystyle w(A_{u},u)=w(A_{v},u)+w(A_{u}-A_{v},u)}$

${\displaystyle w(A_{u},u)\leq w(C_{v})+w(A_{u}-A_{v},u)}$ по индкуции, ${\displaystyle w(A_{v},u)\leq w(A_{v},v)\leq w(C_{v})}$

${\displaystyle w(A_{u},u)\leq w(C_{u})}$, поскольку ${\displaystyle w(A_{u}-A_{v},u)}$ даёт вклад в ${\displaystyle w(C_{u})}$, но не в ${\displaystyle w(C_{v})}$ (и другие рёбра имеют неотрицательные веса)

Тогда, поскольку t всегда является активной вершиной, поскольку последний разрез фазы разделяет s от t по определению для любой активной вершины t

${\displaystyle w(A_{t},t)\leq w(C_{t})=w(C)}$

Таким образом, разрез на фазе не превосходит веса C.

Временная сложность алгоритма MinimumCut равна суммарному времени ${\displaystyle |V|-1}$ прогонов процедуры MinimumCutPhase, которая вызывается на графе с убывающим числом вершин и рёбер.

Один прогон процедуры MinimumCutPhase требует не более ${\displaystyle O(|E|+|V|\log |V|)}$ времени.

Поэтому полное время должно быть произведением двух фаз, что есть ${\displaystyle O(|V||E|+|V|^{2}\log |V|)}$^[2].

Для дальнейшего улучшения следует сделать простым выбор следующей вершины для добавления в множество A, то есть наиболее сильно связанной вершины. При выполнении фазы все вершины, которые не находятся в A, размещаются в очереди с приоритетом, основанной на поле ключа. Ключ вершины V — сумма весов рёбер, соединяющих её с текущим множеством A, то есть ${\displaystyle w(A,v)}$. Когда вершина v добавляется в множество A, нам следует обновить очередь. Вершину v следует удалить из очереди, а ключи всех вершин w не из A, связанных с v, необходимо увеличить на вес ребра vw, если таковое существует. Поскольку это делается в точности один раз для любого ребра, всего нам придётся осуществить ${\displaystyle |V|}$ операций ExtractMax и ${\displaystyle |E|}$ операций IncreaseKey. При использовании фибоначчиевой кучи мы можем осуществить операцию ExtractMax за амортизированное время ${\displaystyle O(\log |V|)}$, а операцию IncreaseKey за амортизированное время ${\displaystyle O(1)}$^[5]. Таким образом, время, которое нам нужно для выполнения этого ключевого шага фазы, который доминирует над остальной частью, равно ${\displaystyle O(|E|+|V|\log |V|)}$^[2].