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

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

В теории графов , то алгоритм Stoer-Wagner является рекурсивным алгоритмом для решения минимального разреза проблемы в неориентированных взвешенных графах с неотрицательными весами. Он был предложен Мехтильдом Стоером и Фрэнком Вагнером в 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}$

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

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

Алгоритм работает поэтапно. В MinimumCutPhase подмножество вершин графов растет, начиная с произвольной единственной вершины, пока не станет равным . На каждом шаге к множеству добавляется вершина, которая находится вне , но наиболее тесно связана с ней . Формально эту процедуру можно представить как: ^[2] добавить вершину так , чтобы , где - сумма весов всех ребер между и . Итак, в одной фазе определяется пара вершин и , и минимальный разрез . ^[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}$После одной фазы MinimumCutPhase две вершины объединяются в новую вершину, а ребра от двух вершин до оставшейся вершины заменяются ребром, взвешенным по сумме весов двух предыдущих ребер. Ребра, соединяющие объединенные узлы, удаляются. Если есть минимальный разрез разделения и , это минимальный разрез . Если нет, то минимальный срез должен иметь и на одной стороне. Следовательно, алгоритм объединит их как один узел. Кроме того, MinimumCut будет записывать и обновлять глобальный минимальный разрез после каждого MinimumCutPhase. После этапов можно определить минимальный разрез . ^[4]${\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, которые и в этой фазе. После их объединения новый граф будет таким, как показано на шаге 2. На этом этапе вес разреза равен 5, что является суммой ребер (1,2) и (1,5). Сейчас первый цикл MinimumCut завершен.${\displaystyle G}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle s}$${\displaystyle t}$

На шаге 2, начиная с узла 2, самое тяжелое ребро - (2,15), таким образом, узел 15 помещается в набор . Следующие по весу ребра - (2,3) или (15,6), мы выбираем (15,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]. ^[2]${\displaystyle O(|V||E|+|V|^{2}\log |V|)}$

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

Пример кода ^[5]

// Реализация матрицы смежности алгоритма минимального сокращения Стоера – Вагнера. // // Время выполнения: // O (| V | ^ 3) // // INPUT: // - график, построенный с помощью AddEdge () // // OUTPUT: // - (минимальное значение сокращения, узлы пополам минимальной резки)#include  <cmath>#include  <вектор>#include  <iostream>используя  пространство имен  std ;typedef  vector < int >  VI ; typedef  vector < VI >  VVI ;const  int  INF  =  1000000000 ;пара < int ,  VI >  GetMinCut ( VVI  и веса )  {  int  N  =  веса . размер ();  VI  использовал ( N ),  cut ,  best_cut ;  int  best_weight  =  -1 ; for  ( int  phase  =  N -1 ;  phase  > =  0 ;  phase - )  {  VI  w  =  веса [ 0 ];  VI  добавлен  =  использован ;  int  prev ,  last  =  0 ;  для  ( int  я  =  0 ;  я  <  фаза ;  я ++ )  {  пред  =  последний ;  последний  =  -1;  for  ( int  j  =  1 ;  j  <  N ;  j ++ )  {  если  ( ! добавлено [ j ]  &&  ( last  ==  -1  ||  w [ j ]  >  w [ last ]))  last  =  j ;  }  if  ( i  ==  фаза -1 )  {  for  ( int  j  =  0 ; j  <  N ;  j ++ )  веса [ предыдущая ] [ j ]  + =  веса [ последняя ] [ j ];  для  ( int  j  =  0 ;  j  <  N ;  j ++ )  weights [ j ] [ prev ]  =  weights [ prev ] [ j ];  использовано [ последний ]  =  истина ;  вырезать .push_back ( последний );  // эта часть дает неправильный ответ.  // EX) n = 4, 1-й шаг: prev = 1, last = 2/2-й шаг: prev = 3, last = 4  // если 2-й шаг дает mincut, разрез будет {1,2,3}, {4 } но этот код дает неправильный ответ - {1,3}, {2,4}  if  ( best_weight  ==  -1  ||  w [ last ]  <  best_weight )  {  best_cut  =  cut ;  best_weight  =  w [ последний ];  }  }  else  {  для  ( int  j  =  0 ; j  <  N ;  j ++ )  {  w [ j ]  + =  веса [ последний ] [ j ];  добавлено [ последний ]  =  истина ;  }  }  }  }  return  make_pair ( лучший_ вес ,  лучший_ вырез ); }

^{[ необходима цитата ]}

const int maxn = 550 ; const int inf = 1000000000 ; int n, r ; int edge [maxn] [maxn], dist [maxn] ; логическое значение vis [maxn], bin [maxn] ; void init () { memset ( край , 0 , sizeof ( край )); memset ( bin , false , sizeof ( bin )); } int контракт ( 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 ; for ( j = 1 ; j <= n ; j ++ ) if ( ! bin [ j ] && ! vis [ j ] && dist [ j ] > maxc ) { k = j ; maxc = dist [ j ]; } if ( k == - 1                                   ) возврат mincut ; s = t ; t = k ; mincut = maxc ; vis [ k ] = истина ; for ( j = 1 ; j <= n ; j ++ ) if ( ! bin [ j ] && ! vis [ j ]) dist [ j ] + = edge [ k                                  ] [ j ]; } возврат mincut ; }      int Stoer_Wagner () { int mincut , я , j , s , t , ans ; для ( mincut = inf , i = 1 ; i < n ; i ++ ) { ans = contract ( s , t ); bin [ t ] = истина ; если ( mincut > ans ) mincut =                                           ans ; если ( mincut == 0 ) вернуть 0 ; for ( j = 1 ; j <= n ; j ++ ) if ( ! bin [ j ]) edge [ s ] [ j ] = ( edge [ j ] [ s ] + = edge [ j ] [ t ]); } возврат mincut ; }                             

использованная литература

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

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