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

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

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

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

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

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

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

MinimumCutPhase$(G,w,a)$
    $A\gets \left\{a\right\}$
    while $\ A\neq V$
        add to $A$ the most tightly connected vertex
    end
    store the cut in which the last remaining vertex is by itself (the "cut-of-the-phase") 
    shrink $G$ by merging the two vertices (s, t) added last (the value of "cut-of-the-phase" is the value of minimum s, t cut.)

MinimumCut$(G,w,a)$
    while $|V|>1$
        MinimumCutPhase$(G,w,a)$
        if the cut-of-the-phase is lighter than the current minimum cut
            then store the cut-of-the-phase as the current minimum cut

Алгоритм работает поэтапно. В MinimalCutPhase подмножество $A$ вершин графов растет, начиная с произвольной одиночной вершины, до тех пор, пока $A$ равно $V$. На каждом шаге вершина, находящаяся за пределами $A$, но наиболее тесно связан с $A$ добавляется в набор $A$. Формально эту процедуру можно представить так: добавить вершину $z\notin A$ такой, что $w(A,z)=\max\{w(A,y)\mid y\notin A\}$, где $w(A,y)$ представляет собой сумму весов всех ребер между $A$ и $y$. Итак, за одну фазу пара вершин $s$ и $t$ , и минута $s{\text{-}}t$ резать $C$ определяется. После одного этапа МинимальногоCutPhase две вершины объединяются в новую вершину, а ребра от двух вершин до оставшейся вершины заменяются ребром, взвешенным по сумме весов двух предыдущих ребер. Ребра, соединяющие объединенные узлы, удаляются. Если существует минимальный разрез $G$ разделяющий $s$ и $t$, $C$ это минимальный разрез $G$. Если нет, то минимальный разрез $G$ должен иметь $s$ и $t$ на той же стороне. Следовательно, алгоритм объединит их в один узел. Кроме того, «Минимальный разрез» будет записывать и обновлять глобальный минимальный разрез после каждой «Минимальной фазы разреза». После $n-1$ фаз, минимальный разрез . можно определить

Пример

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

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

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

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

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

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

Лемма 1 : МинимумCutPhase возвращает минимум. $s{\text{-}}t$-вырезка $G$.

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

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

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

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

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

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

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

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

Поэтому срез фазы не более чем такой же тяжелый, как $C$.

Временная сложность

Время работы алгоритма «МинимумКут» равно добавленному времени работы алгоритма « МинимумКут». $|V|-1$ запускаетминимальнуюCutPhase , которая вызывается на графах с уменьшающимся количеством вершин и ребер.

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

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

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

Пример кода

Ниже приведена краткая на C++ . реализация алгоритма Штера – Вагнера

// Adjacency matrix implementation of Stoer–Wagner min cut algorithm.
//
// Running time:
//     O(|V|^3)

#include <bits/stdc++.h>
using namespace 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);

    for (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) with prio. queue
            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].insert(co[s].end(), co[t].begin(), co[t].end());
        for (int i = 0; i < n; i++) mat[s][i] += mat[t][i];
        for (int i = 0; i < n; i++) mat[i][s] = mat[s][i];
        mat[0][t] = INT_MIN;
    }

    return best;
}

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(bin));
}

int contract( int &s, int &t )          // Find s,t
{
    memset(dist, 0, sizeof(dist));
    memset(vis, false, sizeof(vis));
    int i, j, k, mincut, maxc;

    for (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) return mincut;
        s = t;  t = k;
        mincut = maxc;
        vis[k] = true;
        for (j = 1; j <= n; j++) if (!bin[j] && !vis[j])  
            dist[j] += edge[k][j];
    }

    return mincut;  
}

int Stoer_Wagner()  
{  
    int mincut, i, j, s, t, ans;  

    for (mincut = inf, i = 1; i < n; i++)  
    {  
        ans = contract(s, t);
        bin[t] = true;
        if (mincut > ans) mincut = ans;
        if (mincut == 0) return 0;
        for (j = 1; j <= n; j++) if (!bin[j])
            edge[s][j] = (edge[j][s] += edge[j][t]);
    }

    return mincut;
}

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

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