E058. Нахождение минимального разреза. 算法 Штор-Вагнера

Источник: e-maxx.ru/algo, страница PDF 169.

Постановка задачи

Дан неориентированный взвешенный 图

с

vertexми и

рёбрами. Разрезом

называется

некоторое подмножество вершин (фактически, разрез — разбиение вершин на два множества: принадлежащие

и

все остальные). Весом разреза называется сумма весов рёбер, проходящих через разрез, т.е. таких рёбер, ровно

один конец которых принадлежит

:

где через

обозначено множество всех рёбер 图а

, а через

— вес ребра

. it is required find разрез минимального веса. Иногда эту задачу называют "глобальным минимальным разрезом" — по контрасту с задачей, когда заgiven вершины-

сток и исток, и it is required find minimum разрез

, содержащий сток и не содержащий исток. Глобальный minimum разрез равен минимуму среди разрезов минимальной стоимости по всевозможным парам исток-сток. Хотя эту задачу можно решить с помощью 算法а нахождения максимального потока (запуская его

раз

для всевозможных пар истока и стока), однако ниже описан гораздо более простой и быстрый 算法, предложенный Матильдой Штор (Mechthild Stoer) и Франком Вагнером (Frank Wagner) в 1994 г. В общем случае допускаются петли и кратные рёбра, хотя, понятно, петли абсолютно никак не влияют на результат, а все кратные рёбра можно заменить одним edgeм с их суммарным весом. Поэтому мы для простоты будем считать, что во 输入ном 图е петли и кратные рёбра отсутствуют.

Описание 算法а

Базовая идея 算法а очень проста. Будем итеративно повторять следующий процесс: находить

minimum разрез между какой-нибудь парой вершин

и

, а затем объединять эти две вершины в одну

(соединяя списки смежности). В конце концов, после

итерации, 图 сожмётся в единственную вершину и

процесс остановится. После этого ответом будет являться minimum среди всех

найденных

разрезов. Действительно, на каждой

-ой стадии найденный minimum разрез

между vertexми

и

либо окажется искомым глобальным минимальным разрезом, либо же, напротив, вершины

и

невыгодно относить

к разным множествам, поэтому мы ничего не ухудшаем, объединяя эти две вершины в одну. Таким образом, мы свели задачу к следующей: для данного 图а find minimum разрез

между какой-нибудь, произвольной, парой вершин

и

. Для решения этой задачи

был предложен следующий, тоже итеративный процесс. Вводим некоторое множество вершин

, которое

изначально содержит единственную произвольную вершину. На каждом шаге находится vertex,

наиболее сильно связанная с множеством

, т.е. vertex

, для которой следующая

величина максимальна:

(т.е. максимальна сумма весов рёбер, один конец которых

, а другой принадлежит

).

Опять же, этот процесс завершится через

итерацию, когда все вершины перейдут в множество

(кстати

говоря, этот процесс очень напоминает Prim's algorithm). Тогда, как утверждает теорема Штор-Вагнера,

если мы обозначим через

и

последние две добавленные в

вершины, то minimum разрез между vertexми

и

будет состоять из единственной вершины —

. 证明 этой теоремы будет приведено в следующем

разделе (как это часто бывает, само по себе оно никак не способствует пониманию 算法а). Таким образом, общая схема 算法а Штор-Вагнера такова. 算法 состоит из

фазы. На каждой

фазе множество

сначала полагается состоящим из какой-либо вершины; подсчитываются стартовые веса

вершин

. Затем происходит

итерация, на каждой из которых выбирается vertex

с

наибольшим значением

и добавляется в множество

, после чего пересчитываются значения

для оставшихся вершин (для чего, очевидно, надо пройтись по всем рёбрам списка смежности выбранной вершины

). После выполнения всех итераций мы запоминаем в

и

номера последних двух добавленных вершин, а в

качестве стоимости найденного минимального разреза между

и

можно взять значение

. Затем

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

с наибольшей величиной

. Если производить это за

, то, given, что всего фаз

, и по

итерации

в каждой, итоговая Asymptotic complexity 算法а получается

.

Если для нахождения вершины с наибольшей величиной

использовать Фибоначчиевы кучи

(которые позволяют увеличивать значение ключа за

в среднем и извлекать максимум за

в среднем),

то все связанные с множеством

операции на одной фазе выполнятся за

. Итоговая

Asymptotic complexity 算法а в таком случае составит

.

证明 теоремы Штор-Вагнера

Напомним 题意 этой теоремы. Если добавить в множество

по очереди все вершины, каждый раз добавляя

вершину, наиболее сильно связанную с этим множеством, то обозначим предпоследнюю добавленную вершину через

,

а последнюю — через

. Тогда minimum

-

разрез состоит из единственной вершины —

.

Для доказательства рассмотрим произвольный

-

разрез

и покажем, что его вес не может быть меньше веса

разреза, состоящего из единственной вершины

:

Для этого докажем следующий факт. Пусть

— состояние множества

непосредственно перед добавлением

вершины

. Пусть

— разрез множества

, индуцированный разрезом

(проще говоря,

равно пересечению этих двух множеств вершин). Далее, vertex

называется активной (по отношению к разрезу

), если vertex

и предыдущая добавленная в

vertex принадлежат разным частям разреза

.

Тогда, утверждается, для любой активной вершины

выполняется неравенство:

В частности,

является активной вершиной (т.к. перед ним добавлялась vertex

), и при

это

неравенство превращается в утверждение теоремы: Итак, будем доказывать неравенство, для чего воспользуемся методом математической индукции.

Для первой активной вершины

это неравенство верно (более того, оно обращается в равенство) — поскольку

все вершины

принадлежат одной части разреза, а

— другой. Пусть теперь это неравенство выполнено для всех активных вершин вплоть до некоторой вершины

, докажем его

для следующей активной вершины

. Для этого преобразуем левую часть: Во-первых, заметим, что:

— это следует из того, что когда множество

было равно

, в него была добавлена именно vertex

, а не

,

значит, она имела наибольшее значение

.

Далее, поскольку

по предположению индукции, то получаем: откуда имеем:

Теперь заметим, что vertex

и все вершины

находятся в разных частях разреза

, поэтому эта

величина

обозначает сумму весов рёбер, которые учтены в

, но ещё не были учтены

в

, откуда получаем: что и требовалось доказать.

Мы доказали соотношение

, а из него, как уже говорилось выше, следует и вся теорема.

实现

Для наиболее простой и ясной реализации (с асимптотикой

) было выбрано представление 图а в виде

матрицы смежности. Ответ хранится в переменных

и

(искомые стоимость минимального

разреза и сами вершины, содержащиеся в нём).

Для каждой вершины в 数组е

хранится, существует ли она, или она была объединена с какой-то

другой вершиной. В списке

для каждой сжатой вершины

хранятся номера исходных вершин, которые были сжаты

в эту вершину

.

算法 состоит из

фазы (цикл по переменной

). На каждой фазе сначала все вершины находятся

вне множества

, для чего 数组

заполняется нулями, и связности

всех вершин нулевые. На каждой

из

итерации находится vertex

с наибольшей величиной

. Если это итерация последняя, то ответ,

если надо, обновляется, а предпоследняя

и последняя

выбранные вершины объединяются в одну.

Если итерация не последняя, то

добавляется в множество

, после чего пересчитываются веса всех

остальных вершин. Следует заметить, что 算法 в ходе своей работы "портит" 图

, поэтому, если он ещё понадобится позже,

надо сохранять его копию перед вызовом функции.

const int MAXN = 500;

int n, g[MAXN][MAXN];

int best_cost = 1000000000;

vector<int> best_cut;

void mincut() {

vector<int> v[MAXN];

for (int i=0; i<n; ++i)

v[i].assign (1, i);

int w[MAXN];

bool exist[MAXN], in_a[MAXN];

memset (exist, true, sizeof exist);

for (int ph=0; ph<n-1; ++ph) {

memset (in_a, false, sizeof in_a);

memset (w, 0, sizeof w);

for (int it=0, prev; it<n-ph; ++it) {

int sel = -1;

for (int i=0; i<n; ++i)

if (exist[i] && !in_a[i] && (sel == -1 || w

[i] > w[sel]))

sel = i;

if (it == n-ph-1) {

if (w[sel] < best_cost)

best_cost = w[sel], best_cut = v[sel];

v[prev].insert (v[prev].end(), v[sel].begin(),

v[sel].end());

for (int i=0; i<n; ++i)

g[prev][i] = g[i][prev] += g[sel][i];

exist[sel] = false;

}

else {

in_a[sel] = true;

for (int i=0; i<n; ++i)

w[i] += g[sel][i];

prev = sel;

} } } }

References

● Mechthild Stoer, Frank Wagner. A Simple Min-Cut Algorithm [1997]

● Kurt Mehlhorn, Christian Uhrig. The minimum cut algorithm of Stoer and Wagner [1995]

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    const int MAXN = 500;
    int n, g[MAXN][MAXN];
    int best_cost = 1000000000;
    List<int> best_cut;
    void mincut() {
            List<int> v[MAXN];
            for (int i=0; i<n; ++i)
                    v[i].assign (1, i);
            int w[MAXN];
            bool[] exist = new bool[MAXN], in_a[MAXN];
            memset (exist, true, sizeof exist);
            for (int ph=0; ph<n-1; ++ph) {
                    memset (in_a, false, sizeof in_a);
                    memset (w, 0, sizeof w);
                    for (int it=0, prev; it<n-ph; ++it) {
                            int sel = -1;
                            for (int i=0; i<n; ++i)
                                    if (exist[i] && !in_a[i] && (sel == -1 || w
    [i] > w[sel]))
                                            sel = i;
                            if (it == n-ph-1) {
                                    if (w[sel] < best_cost)
                                            best_cost = w[sel],  best_cut = v[sel];
                                    v[prev].insert (v[prev].end(), v[sel].begin(),
    v[sel].end());
                                    for (int i=0; i<n; ++i)
                                            g[prev][i] = g[i][prev] += g[sel][i];
                                    exist[sel] = false;
                            }
                            else {
                                    in_a[sel] = true;
                                    for (int i=0; i<n; ++i)
                                            w[i] += g[sel][i];
                                    prev = sel;
                            }
                    }
            }
    }
}

const int MAXN = 500;
int n, g[MAXN][MAXN];
int best_cost = 1000000000;
vector<int> best_cut;
void mincut() {
        vector<int> v[MAXN];
        for (int i=0; i<n; ++i)
                v[i].assign (1, i);
        int w[MAXN];
        bool exist[MAXN], in_a[MAXN];
        memset (exist, true, sizeof exist);
        for (int ph=0; ph<n-1; ++ph) {
                memset (in_a, false, sizeof in_a);
                memset (w, 0, sizeof w);
                for (int it=0, prev; it<n-ph; ++it) {
                        int sel = -1;
                        for (int i=0; i<n; ++i)
                                if (exist[i] && !in_a[i] && (sel == -1 || w
[i] > w[sel]))
                                        sel = i;
                        if (it == n-ph-1) {
                                if (w[sel] < best_cost)
                                        best_cost = w[sel],  best_cut = v[sel];
                                v[prev].insert (v[prev].end(), v[sel].begin(),
v[sel].end());
                                for (int i=0; i<n; ++i)
                                        g[prev][i] = g[i][prev] += g[sel][i];
                                exist[sel] = false;
                        }
                        else {
                                in_a[sel] = true;
                                for (int i=0; i<n; ++i)
                                        w[i] += g[sel][i];
                                prev = sel;
                        }
                }
        }
}

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    const int MAXN = 500;
    int n, g[MAXN][MAXN];
    int best_cost = 1000000000;
    ArrayList<Integer> best_cut;
    void mincut() {
            ArrayList<Integer> v[MAXN];
            for (int i=0; i<n; ++i)
                    v[i].assign (1, i);
            int w[MAXN];
            boolean exist[MAXN], in_a[MAXN];
            memset (exist, true, sizeof exist);
            for (int ph=0; ph<n-1; ++ph) {
                    memset (in_a, false, sizeof in_a);
                    memset (w, 0, sizeof w);
                    for (int it=0, prev; it<n-ph; ++it) {
                            int sel = -1;
                            for (int i=0; i<n; ++i)
                                    if (exist[i] && !in_a[i] && (sel == -1 || w
    [i] > w[sel]))
                                            sel = i;
                            if (it == n-ph-1) {
                                    if (w[sel] < best_cost)
                                            best_cost = w[sel],  best_cut = v[sel];
                                    v[prev].insert (v[prev].end(), v[sel].begin(),
    v[sel].end());
                                    for (int i=0; i<n; ++i)
                                            g[prev][i] = g[i][prev] += g[sel][i];
                                    exist[sel] = false;
                            }
                            else {
                                    in_a[sel] = true;
                                    for (int i=0; i<n; ++i)
                                            w[i] += g[sel][i];
                                    prev = sel;
                            }
                    }
            }
    }
}