Алгоритм Стоера – Вагнера - Stoer–Wagner algorithm

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

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

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

Алгоритм минимального отсечения Стоера – Вагнера

Позволять ${\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}$.^[3]

Этот алгоритм начинается с поиска ${\displaystyle s}$ и ${\displaystyle t}$ в ${\displaystyle V}$, и s-t min-cut ${\displaystyle (S,T)}$ из ${\displaystyle G}$. Для любой пары ${\displaystyle \left\{s,t\right\}}$, возможны две ситуации: либо ${\displaystyle (S,T)}$ это глобальный минимальный разрез ${\displaystyle G}$, или же ${\displaystyle s}$ и ${\displaystyle t}$ принадлежат к той же стороне глобального минимального разреза ${\displaystyle G}$. Следовательно, глобальный min-разрез можно найти, проверив график ${\displaystyle G/\left\{s,t\right\}}$, представляющий собой граф после слияния вершин ${\displaystyle s}$ и ${\displaystyle t}$. Во время слияния, если ${\displaystyle s}$ и ${\displaystyle 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\}}$    пока ${\displaystyle \ A\neq V}$        добавить в ${\displaystyle A}$ самая тесно связанная вершина хранит разрез, в котором последняя оставшаяся вершина находится сама по себе («разрез фазы»), и сжимается ${\displaystyle G}$ путем объединения двух вершин, добавленных последнейMinimumCut${\displaystyle (G,w,a)}$    пока ${\displaystyle |V|>1}$        MinimumCutPhase${\displaystyle (G,w,a)}$        если отрезок фазы легче, чем текущий минимальный отрезок тогда сохранить отсечку фазы как текущую минимальную отсечку

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

Пример

Этот раздел относится к рис. 1–6 в исходной статье^[2]

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

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

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

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

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

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

Позволять ${\displaystyle C=(X,{\overline {X}})}$ быть произвольным ${\displaystyle s{\text{-}}t}$ вырезать, и ${\displaystyle CP}$ быть сокращением, данным фазой. Мы должны показать, что ${\displaystyle W(C)\geq W(CP)}$. Обратите внимание, что один запуск MinimumCutPhase дает нам порядок всех вершин в графе (где ${\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 равно добавленному времени работы ${\displaystyle |V|-1}$ прогоны MinimumCutPhase, который вызывается на графах с убывающим числом вершин и ребер.

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

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

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

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

^{[нужна цитата ]}

const int maxn = 550;const int inf = 1000000000;int п, г;int край [макс.] [макс.], расстояние [макс.];bool vis [maxn], bin [maxn];пустота в этом() {      мемсет(край, 0, размер(край));      мемсет(мусорное ведро, ложный, размер(мусорное ведро));  }  int контракт (int & s, int & t) // Находим s, t {      мемсет(расстояние, 0, размер(расстояние));      мемсет(вис, ложный, размер(вис));    int я, j, k, mincut, maxc;      за (я = 1; я <= п; я++)      {          k = -1; maxc = -1;          за (j = 1; j <= п; j++)если (!мусорное ведро[j] && !вис[j] && расстояние[j] > maxc)          {              k = j;  maxc = расстояние[j];          }          если (k == -1) возвращаться резка;          s = т;  т = k;          резка = maxc;          вис[k] = истинный;          за (j = 1; j <= п; j++) если (!мусорное ведро[j] && !вис[j])              расстояние[j] += край[k][j];      }      возвращаться резка;  }int Stoer_Wagner () {      int mincut, я, j, s, t, ans;      за (резка = инф, я = 1; я < п; я++)      {          ответ = договор( s, т );          мусорное ведро[т] = истинный;          если (резка > ответ) резка = ответ;          если (резка == 0)возвращаться 0;          за (j = 1; j <= п; j++) если (!мусорное ведро[j])              край[s][j] = (край[j][s] += край[j][т]);      }      возвращаться резка;  }

Рекомендации

1. "Библиотека графиков повышения: Мин-вырез Стоера – Вагнера - 1.46.1". www.boost.org. Получено 2015-12-07.
2. «Простой алгоритм Min-Cut».
3. «Конспект лекций по анализу алгоритмов»: глобальные минимальные сокращения » (PDF).
4. «Алгоритм минимального отсечения Стоера и Вагнера» (PDF).
5. «Записная книжка команды ACM Стэнфордского университета (2014–2015 гг.)». web.stanford.edu. Получено 2015-12-07.

внешняя ссылка

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