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

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

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

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

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

Позволять - взвешенный неориентированный граф. Предположим, что . Разрез называется - вырезать, если ровно один из или же в . Минимальный разрез это тоже - сокращение называется - минимальный разрез .[3]

Этот алгоритм начинается с поиска и в , и s-t min-cut из . Для любой пары , возможны две ситуации: либо это глобальный минимальный разрез , или же и принадлежат к той же стороне глобального минимального разреза . Следовательно, глобальный min-разрез можно найти, проверив график , представляющий собой граф после слияния вершин и . Во время слияния, если и соединены ребром, тогда это ребро исчезает. Если s и t оба имеют ребра в некоторую вершину v, то вес ребра от новой вершины st до v равен .[3] Алгоритм описывается как:[2]

MinimumCutPhase        пока         добавить в  самая тесно связанная вершина хранит разрез, в котором последняя оставшаяся вершина находится сама по себе («разрез фазы»), и сжимается  путем объединения двух вершин, добавленных последнейMinimumCut    пока         MinimumCutPhase        если отрезок фазы легче, чем текущий минимальный отрезок тогда сохранить отсечку фазы как текущую минимальную отсечку

Алгоритм работает поэтапно. В MinimumCutPhase подмножество вершин графов растет, начиная с произвольной единственной вершины, пока равно . На каждом шаге вершина, которая находится вне , но наиболее тесно связаны с добавлен в набор . Формально эту процедуру можно представить как:[2] добавить вершину такой, что , куда это сумма весов всех ребер между и . Итак, за одну фазу пара вершин и , а мин резать определен.[4] После одной фазы MinimumCutPhase две вершины объединяются в новую вершину, а ребра от двух вершин до оставшейся вершины заменяются ребром, взвешенным по сумме весов двух предыдущих ребер. Ребра, соединяющие объединенные узлы, удаляются. Если есть минимальный срез разделение и , то это минимальное сокращение . Если нет, то минимальный срез должны быть и на той же стороне. Следовательно, алгоритм объединит их как один узел. Кроме того, MinimumCut будет записывать и обновлять глобальный минимальный разрез после каждого MinimumCutPhase. После фазы, минимальный разрез можно определить.[4]

Пример

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

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

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

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

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

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

Лемма 1: MinimumCutPhase возвращает минимум -срез .

Позволять быть произвольным вырезать, и быть сокращением, данным фазой. Мы должны показать, что . Обратите внимание, что один запуск MinimumCutPhase дает нам порядок всех вершин в графе (где это первый и и две вершины, добавленные последними в фазе). Мы говорим, что вершина активен, если а вершина добавлена ​​непосредственно перед находятся на противоположных сторонах разреза. Докажем лемму индукцией по множеству активных вершин. Мы определяем как набор вершин, добавленных к перед , и быть набором ребер в с обоими концами в , т.е. разрез, индуцированный . Докажем, что для каждой активной вершины ,

Позволять быть первой активной вершиной. По определению этих двух величин, и эквивалентны. просто все вершины добавляются к перед , а ребра между этими вершинами и края, которые пересекают разрез . Поэтому, как показано выше, для активных вершин и , с Добавлено в перед :

по индукции

поскольку способствует но не (а остальные ребра имеют неотрицательный вес)

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

Следовательно, разрез фазы не более тяжелый, чем .

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

В Продолжительность алгоритма MinimumCut равно добавленному времени работы прогоны MinimumCutPhase, который вызывается на графах с убывающим числом вершин и ребер.

Для MinimumCutPhase, для одного запуска требуется не более время.

Следовательно, общее время работы должно быть произведением двухфазной сложности, которая [2].[2]

Для дальнейшего улучшения важно упростить выбор следующей вершины для добавления в набор. , наиболее тесно связная вершина. Во время выполнения фазы все вершины, не входящие в находятся в очереди с приоритетом на основе ключевого поля. Ключ вершины это сумма весов ребер, соединяющих его с текущим , то есть, . Когда вершина добавлен к мы должны выполнить обновление очереди. необходимо удалить из очереди, а ключ каждой вершины не в , подключен к должен быть увеличен весом кромки , если он существует. Поскольку это делается ровно один раз для каждого ребра, в целом мы должны выполнить ExtractMax и Операции IncreaseKey. Используя Куча Фибоначчи мы можем выполнить операцию ExtractMax в амортизированное время и операция IncreaseKey в амортизированное время. Таким образом, время, необходимое нам для этого ключевого шага, который доминирует над остальной частью фазы, равно .[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. ^ а б c d е ж «Простой алгоритм Min-Cut».
  3. ^ а б «Конспект лекций по анализу алгоритмов»: глобальные минимальные сокращения » (PDF).
  4. ^ а б «Алгоритм минимального отсечения Стоера и Вагнера» (PDF).
  5. ^ «Записная книжка команды ACM Стэнфордского университета (2014–2015 гг.)». web.stanford.edu. Получено 2015-12-07.

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

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