Алгоритм Стоера–Вагнера

Рекурсивный алгоритм в теории графов

Минимальный разрез взвешенного графа, имеющий минимальный разрез весом 4 ^[1]

В теории графов алгоритм Штоера–Вагнера — это рекурсивный алгоритм для решения задачи минимального разреза в неориентированных взвешенных графах с неотрицательными весами. Он был предложен Мехтильд Штоер и Фрэнком Вагнером в 1995 году. Основная идея этого алгоритма заключается в сжатии графа путем слияния наиболее интенсивных вершин до тех пор, пока граф не будет содержать только два объединенных набора вершин. ^[2] На каждой фазе алгоритм находит минимальный разрез для двух вершин и выбранных по своему желанию. Затем алгоритм сжимает ребро между и для поиска не - разрезов. Минимальный разрез, найденный на всех фазах, будет минимальным взвешенным разрезом графа. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$

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

Алгоритм минимального разреза Штера – Вагнера

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

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

MinimumCutPhase при добавлении к наиболее тесно связанному концу вершины ${\displaystyle (G,w,a)}$  ${\displaystyle A\gets \left\{a\right\}}$   ${\displaystyle \ A\neq V}$ ${\displaystyle A}$ сохранить разрез, в котором последняя оставшаяся вершина находится сама по себе («разрез фазы») сжать путем слияния двух вершин (s, t), добавленных последними (значение «отрезка фазы» — это значение минимального отрезка s, t). ${\displaystyle G}$MinimumCut while MinimumCutPhase если срез фазы легче текущего минимального среза , то сохранить срез фазы как текущий минимальный срез ${\displaystyle (G,w,a)}$   ${\displaystyle |V|>1}$  ${\displaystyle (G,w,a)}$ 

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

Пример

В этом разделе даны ссылки на рис. 1–6 в оригинальной статье. ^[2]

Граф на шаге 1 показывает исходный граф и случайным образом выбирает узел 2 в качестве начального узла для этого алгоритма. В MinimumCutPhase набор имеет только узел 2, самым тяжелым ребром является ребро (2,3), поэтому узел 3 добавляется в набор . Далее набор содержит узел 2 и узел 3, самым тяжелым ребром является (3,4), поэтому узел 4 добавляется в набор . Следуя этой процедуре, последние два узла — это узел 5 и узел 1, которые находятся и в этой фазе. Объединяя их в узел 1+5, новый граф становится таким, как показано на шаге 2. В этой фазе вес разреза равен 5, что является суммой ребер (1,2) и (1,5). Прямо сейчас первый цикл MinimumCut завершен. ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle s}$ ${\displaystyle t}$

На шаге 2, начиная с узла 2, самым тяжелым ребром является (2,1+5), поэтому узел 1+5 помещается в набор . Следующим самым тяжелым ребром является (2,3) или (1+5,6), мы выбираем (1+5,6), поэтому узел 6 добавляется в набор. Затем мы сравниваем ребра (2,3) и (6,7) и выбираем узел 3 для помещения в набор . Последние два узла — это узел 7 и узел 8. Поэтому объединяем ребра (7,8). Минимальный разрез равен 5, поэтому оставляем минимум равным 5. ${\displaystyle A}$ ${\displaystyle A}$

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

Доказательство правильности

Чтобы доказать правильность этого алгоритма, нам нужно доказать, что разрез, заданный MinimumCutPhase, на самом деле является минимальным разрезом графа, где s и t — две вершины, добавленные последними в фазе. Поэтому ниже показана лемма: ${\displaystyle s{\text{-}}t}$

Лемма 1 : MinimumCutPhase возвращает минимальный разрез . ${\displaystyle s{\text{-}}t}$ ${\displaystyle G}$

Пусть будет произвольным разрезом, а будет разрезом, заданным фазой. Мы должны показать, что . Заметим, что один запуск MinimumCutPhase дает нам упорядочение всех вершин в графе (где — первая, а и — две вершины, добавленные последними в фазе). Мы говорим, что вершина активна, если и вершина, добавленная непосредственно перед этим, находятся на противоположных сторонах разреза. Мы докажем лемму индукцией по множеству активных вершин. Мы определяем как множество вершин, добавленных к до , и как множество ребер в с обоими их концами в , т. е. — разрез, индуцированный . Мы доказываем, для каждой активной вершины , ${\displaystyle C=(X,{\overline {X}})}$ ${\displaystyle s{\text{-}}t}$ ${\displaystyle CP}$ ${\displaystyle W(C)\geq W(CP)}$ ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle A_{v}}$ ${\displaystyle A}$ ${\displaystyle v}$ ${\displaystyle C_{v}}$ ${\displaystyle C}$ ${\displaystyle A_{v}\cup \{v\}}$ ${\displaystyle C_{v}\subseteq C}$ ${\displaystyle A_{v}\cup \{v\}}$ ${\displaystyle 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}}}$ ${\displaystyle A}$ ${\displaystyle v_{0}}$ ${\displaystyle v_{0}}$ ${\displaystyle C}$ ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle A}$ ${\displaystyle 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})}$

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

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

Таким образом, срез фазы не превышает . ${\displaystyle C}$

Сложность времени

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

Для MinimumCutPhase на один запуск требуется максимум время. ${\displaystyle O(|E|+|V|\log |V|)}$

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

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

Пример кода

Ниже представлена ​​краткая реализация алгоритма Штера–Вагнера на языке C++ . ^[5]

// Реализация матрицы смежности алгоритма минимального разреза Стоера–Вагнера. // // Время выполнения: // O(|V|^3)#include <bits/stdc++.h> с использованием пространства имен std ;   pair < ​​int , vector < int >> globalMinCut ( vector < vector < int >> mat ) { pair < ​​int , vector < int >> best = { INT_MAX , {}}; int n = mat . size (); vector < vector < int >> co ( n );                 для ( int i = 0 ; i < n ; i ++ ) co [ i ] = { i };            for ( int ph = 1 ; ph < n ; ph ++ ) { vector < int > w = mat [ 0 ]; size_t s = 0 , t = 0 ; for ( int it = 0 ; it < n - ph ; it ++ ) { // O(V^2) -> O(E log V) с априорной очередью w [ t ] = INT_MIN ; s = t , t = max_element ( w . begin (), w . end ()) - w . begin (); for ( int i = 0 ; i < n ; i ++ ) w [ i ] += mat [ t ][ i ]; } best = min ( best , { w [ t ] - mat [ t ][ t ], co [ t ]}); co [ s ]. вставить ( co [ s ]. конец (), co [ t ]. начало (), co [ t ]. конец ()); для ( int i = 0 ; i < n ; i ++ ) mat [ s ][ i ] += mat [ t ][ i ]; для ( int i = 0 ; i < n ; i ++ ) mat [ i ][ s ] = mat                                                                                            [ s ][ i ]; мат [ 0 ][ t ] = INT_MIN ; }     вернуть лучшее ; } 

^{[ необходима ссылка ]}

const int maxn = 550 ; const int inf = 1000000000 ; int n , r ; int edge [ maxn ][ maxn ], dist [ maxn ]; bool vis [ maxn ], bin [ maxn ];              void init () { memset ( edge , 0 , sizeof ( edge )); memset ( bin , false , sizeof ( edge )); }       int contract ( int & s , int & t ) // Найти s, t { memset ( dist , 0 , sizeof ( dist )); memset ( vis , false , sizeof ( vis )); int i , j , k , mincut , maxc ;                    для ( i = 1 ; i <= n ; i ++ ) { k = -1 ; maxc = -1 ; для ( j = 1 ; j <= n ; j ++ ) если ( ! bin [ j ] && ! vis [ j ] && dist [ j ] > maxc ) { k = j ; maxc = dist [ j ]; } если ( k == -1 ) вернуть mincut ; s = t ; t = k ; mincut = maxc ; vis [ k ] = true ; для ( j = 1 ; j <= n ; j ++ ) если ( ! bin [ j ] && ! vis [ j ]) dist [ j ] += edge [ k ][ j ]; }                                                                         возвратить мин. вырезку ; }  int Stoer_Wagner () { int mincut , i , j , s , t , ans ;            для ( mincut = inf , i = 1 ; i < n ; i ++ ) { ans = contract ( s , t ); bin [ t ] = true ; если ( mincut > ans ) mincut = ans ; если ( mincut == 0 ) вернуть 0 ; для ( j = 1 ; j <= n ; j ++ ) если ( ! bin [ j ]) edge [ s ][ j ] = ( edge [ j ][ s ] += edge [ j ][ t ]); }                                                  возвратить мин. вырезку ; } 

Ссылки

1. "Boost Graph Library: Stoer–Wagner Min-Cut - 1.46.1". www.boost.org . Получено 2015-12-07 .
2. «Простой алгоритм минимального разреза».
3. "Конспект лекций по анализу алгоритмов": Глобальные минимальные разрезы" (PDF) .
4. "Алгоритм минимального разреза Стоера и Вагнера" ​​(PDF) .
5. "Библиотека шаблонов конкурса алгоритмов KTH". github.com . Получено 17.11.2021 .

Внешние ссылки

• StoerWagnerMinCut.java — библиотека Java, реализующая алгоритм Стоера–Вагнера