e-maxx_algo

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

Реализация

Следует заметить, что алгоритм в ходе своей работы "портит" граф , поэтому, если он ещё понадобится позже, надо сохранять его копию перед вызовом функции.

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;

}

}

}

}

Литература

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

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

Поток минимальной стоимости, циркуляция минимальной стоимости.

Алгоритм удаления циклов отрицательного веса

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

●Ограничение пропускной способности (выполняется для любых ):

●Антисимметричность (выполняется для любых ):

●Сохранение потока (выполняется для любых , кроме , ):

Величиной потока называется величина

Стоимостью потока называется величина

Задача нахождения потока минимальной стоимости заключается в том, что по заданной величине потока требуется найти поток, обладающий минимальной стоимостью . Стоит обратить внимание на то,

что стоимости , приписанные рёбрам, отвечают за стоимость единицы потока вдоль этого ребра; иногда встречается задача, когда рёбрам сопоставляются стоимости протекания потока вдоль этого ребра (т.е. если протекает поток любой величины, то взимается эта стоимость, независимо от величины потока) — эта задача не имеет ничего общего с рассматриваемой здесь и, более того, является NP-полной.

Задача нахождения максимального потока минимальной стоимости заключается в том,

чтобы найти поток наибольшей величины, а среди всех таких — с минимальной стоимостью. В частном случае, когда веса всех рёбер одинаковы, эта задача становится эквивалентной обычной задаче о максимальном потоке.

Задача нахождения циркуляции минимальной стоимости заключается в том, чтобы найти поток нулевой величины с минимальной стоимостью. Если все стоимости неотрицательные, то, понятно, ответом будет нулевой поток ; если же есть рёбра отрицательного веса (а, точнее, циклы отрицательного веса), то даже

при нулевом потоке возможно найти поток отрицательной стоимости. Задачу нахождения циркуляции минимальной стоимости можно, разумеется, поставить и на сети без истока и стока, поскольку никакой смысловой нагрузки они не несут (впрочем, в такой граф можно добавить исток и сток в виде изолированных вершин и

получить обычную по формулировке задачу). Иногда ставится задача нахождения циркуляции максимальной стоимости

— понятно, достаточно изменить стоимости рёбер на противоположные и получим задачу нахождения циркуляции уже минимальной стоимости.

с одинаковыми пропускными способностями и стоимостями.

Остаточная сеть

пропускную способность — равную потоку вдоль прямого ребра, а стоимость — противоположную (ведь после отмены части потока мы должны соответственно уменьшить и стоимость):

Таким образом, каждому ориентированному ребру в соответствует два ориентированных ребра в остаточной сети , и у каждого ребра остаточной сети появляется дополнительная характеристика — остаточная

Кстати, при реализации это свойство позволяет не хранить остаточные пропускные способности, а просто вычислять их при необходимости для ребра.

считать, что такой ситуации в сети нет (исключительно в целях простоты и корректности описаний; на правильность идей это никак не влияет).

Критерий оптимальности по наличию циклов отрицательного веса

Теорема. Некоторый поток является оптимальным (т.е. имеет наименьшую стоимость среди всех потоков такой же величины) тогда и только тогда, когда остаточная сеть не содержит циклов отрицательного веса.

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

среди остаточных пропускных способностей рёбер этого цикла ( будет больше нуля). Но тогда можно увеличить поток вдоль каждого ребра цикла на величину , при этом никакие свойства потока не нарушатся, величина потока не изменится, однако стоимость потока уменьшится (уменьшится на стоимость цикла, умноженную на ). Таким образом, если есть цикл отрицательного веса, то не может быть оптимальным, ч.т.д.

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

рёбер, выходящих из неё. Такая организация позволяет легко находить номер обратного ребра по номеру прямого ребра — они оказываются в списке соседними, и номер одного можно получить по номеру другого

операцией "^1" (она инвертирует младший бит). Добавление ориентированного ребра в граф осуществляет функция , которая добавляет сразу прямое и обратное рёбра.

const int MAXN = 100*2; int n;

struct edge {

int v, to, u, f, c;

};

vector<edge> edges; vector<int> g[MAXN];

void add_edge (int v, int to, int cap, int cost) { edge e1 = { v, to, cap, 0, cost };

edge e2 = { to, v, 0, 0, -cost }; g[v].push_back ((int) edges.size()); edges.push_back (e1); g[to].push_back ((int) edges.size()); edges.push_back (e2);

}

В основной программе после чтения графа идёт бесконечный цикл, внутри которого выполняется алгоритм Форда-Беллмана, и если он обнаруживает цикл отрицательной стоимости, то вдоль этого цикла увеличивается поток. Поскольку остаточная сеть может представлять собой несвязный граф, то алгоритм Форда-Беллмана запускается из каждой не достигнутой ещё вершины. В целях оптимизации алгоритм использует очередь (текущая очередь и новая очередь ), чтобы не перебирать на каждой стадии все рёбра. Вдоль обнаруженного цикла каждый раз проталкивается ровно единица потока, хотя, понятно, в целях оптимизации величину потока можно определять как минимум остаточных пропускных способностей.

const int INF = 1000000000;

for (;;) {

bool found = false;

vector<int> d (n, INF); vector<int> par (n, -1); for (int i=0; i<n; ++i)

if (d[i] == INF) { d[i] = 0;

vector<int> q, nq; q.push_back (i);

for (int it=0; it<n && q.size(); ++it) { nq.clear();

sort (q.begin(), q.end());

q.erase (unique (q.begin(), q.end()), q.end()); for (size_t j=0; j<q.size(); ++j) {

int v = q[j];

for (size_t k=0; k<g[v].size(); ++k) { int id = g[v][k];

if (edges[id].f < edges[id].u) if (d[v] + edges[id].

c < d[edges[id].to]) {

d[edges[id].

to] = d[v] + edges[id].c;

par[edges

[id].to] = v;

nq.

push_back (edges[id].to);

}

}

}

swap (q, nq);

}

if (q.size()) {

int leaf = q[0]; vector<int> path;

for (int v=leaf; v!=-1; v=par[v])

if (find (path.begin(), path.end(),

v) == path.end())

path.push_back (v);

else {

path.erase (path.begin(),

find (path.begin(), path.end(), v));

break;

}

for (size_t j=0; j<path.size(); ++j) {

int to = path[j], v = path[(j+1)%

path.size()];

for (size_t k=0; k<g[v].size(); ++k)

if (edges[ g[v][k] ].to == to) { int id = g[v][k]; edges[id].f += 1; edges[id^1].f -= 1;

}

}

found = true;

}

}

if (!found) break;

}

Литература

●Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ [2005]

●Ravindra Ahuja, Thomas Magnanti, James Orlin. Network flows [1993]

●Andrew Goldberg, Robert Tarjan. Finding Minimum-Cost Circulations by Cancelling Negative Cycles [1989]

Алгоритм Диница

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

Требуется найти в этой сети поток из истока в сток максимальной величины.

Немного истории

Этот алгоритм был опубликован советским (израильским) учёным Ефимом Диницем (Yefim Dinic, иногда пишется как "Dinitz") в 1970 г., т.е. даже на два года раньше опубликования алгоритма Эдмондса-Карпа (впрочем, оба алгоритма были независимо открыты в 1968 г.).

Кроме того, следует отметить, что некоторые упрощения алгоритма были произведены Шимоном Ивеном (Shimon Even) и его учеником Алоном Итаи (Alon Itai) в 1979 г. Именно благодаря им алгоритм получил свой современный облик: они применили к идее Диница концепцию блокирующих потоков Александра Карзанова (Alexander Karzanov, 1974 г.), а также переформулировали алгоритм к той комбинации обхода в ширину и в глубину, в которой сейчас этот алгоритм и излагается везде.

Развитие идей по отношению к потоковым алгоритмам крайне интересно рассматривать, учитывая "железный занавес" тех лет, разделявший СССР и Запад. Видно, как иногда похожие идеи появлялись почти одновременно (как в случае алгоритма Диница и алгоритма Эдмондса-Карпа), правда, имея при этом разную эффективность (алгоритм Диница на один порядок быстрее); иногда же, наоборот, появление идеи по одну сторону "занавеса" опережало аналогичный ход по другую сторону более чем на десятилетие (как алгоритм Карзанова проталкивания в 1974 г. и алгоритм Гольдберга (Goldberg) проталкивания в 1985 г.).

Необходимые определения

Введём три необходимых определения (каждое из них является независимым от остальных), которые затем будут использоваться в алгоритме Диница.

каждому ребру с пропускной способностью и потоком соответствуют два ребра:

● с пропускной способностью

● с пропускной способностью

Стоит отметить, что при таком определении в остаточной сети могут появляться кратные рёбра: если в исходной сети было как ребро , так и .

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

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

Блокирующий поток не обязательно максимален. Теорема Форда-Фалкерсона говорит о том, что поток будет максимальным тогда и только тогда, когда в остаточной сети не найдётся пути; в блокирующем же потоке ничего не утверждается о существовании пути по рёбрам, появляющимся в остаточной сети.

Слоистая сеть для данной сети строится следующим образом. Сначала определяются длины кратчайших путей

может превосходить единицы, следует из свойства кратчайших расстояний). Таким образом, удаляются все рёбра, расположенные целиком внутри уровней, а также рёбра, ведущие назад, к предыдущим уровням.

Очевидно, слоистая сеть ациклична. Кроме того, любой путь в слоистой сети является кратчайшим путём

в исходной сети.

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

Примечание. Термин "слоистая сеть" в русскоязычной литературе не употребляется; обычно эта конструкция называется просто "вспомогательным графом". Впрочем, на английском языке обычно используется термин

"layered network".

Алгоритм

Схема алгоритма

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

Найденный блокирующий поток прибавляется к текущему потоку, и на этом очередная итерация заканчивается.

Этот алгоритм схож с алгоритмом Эдмондса-Карпа, но основное отличие можно понимать так: на каждой итерации поток увеличивается не вдоль одного кратчайшего пути, а вдоль целого набора таких путей (ведь именно такими путями и являются пути в блокирующем потоке слоистой сети).

Корректность алгоритма

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

В самом деле, предположим, что в какой-то момент в слоистой сети, построенной для остаточной сети, не удалось найти блокирующий поток. Это означает, что сток вообще не достижим в слоистой сети из истока . Но поскольку слоистая сеть содержит в себе все кратчайшие пути из истока в остаточной сети, это в свою очередь означает, что в остаточной сети нет пути из истока в сток. Следовательно, применяя теорему ФордаФалкерсона, получаем, что текущий поток в самом деле максимален.

Оценка числа фаз

Покажем, что алгоритм Диница всегда выполняет менее фаз. Для этого докажем две леммы:

Лемма 1. Кратчайшее расстояние от истока до каждой вершины не уменьшается с выполнением каждой итерации, т.е.

где нижний индекс обозначает номер фазы, перед которой взяты значения этих переменных.

Доказательство. Зафиксируем произвольную фазу и произвольную вершину и рассмотрим любой кратчайший путь в сети (напомним, так мы обозначаем остаточную сеть, взятую перед

выполнением -ой фазы). Очевидно, длина пути равна .

предыдущими неравенствами, получаем:

Теперь мы можем применять те же самые рассуждения ко всему оставшемуся пути до (т.е. что каждое инвертированное ребро добавляет к как минимум два), и в итоге получим требуемое неравенство.

Лемма 2. Расстояние между истоком и стоком строго увеличивается после каждой фазы алгоритма, т.е.:

где штрихом помечено значение, полученное на следующей фазе алгоритма.

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

должна сохраниться неизменной. Однако остаточная сеть на следующей фазе содержит только рёбра остаточной сети перед выполнением текущей фазы, либо обратные к ним. Таким образом, пришли к противоречию: нашёлся путь, который не содержит насыщенных рёбер, и имеет ту же длину, что и кратчайший путь. Этот путь должен был быть "заблокирован" блокирующим потоком, чего не произошло, в чём и заключается противоречие, что и требовалось доказать.

Эту лемму интуитивно можно понимать следующим образом: на -ой фазе алгоритм Диница выявляет и насыщает все пути длины .

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

Поиск блокирующего потока

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

Мы рассмотрим три возможных варианта реализации поиска блокирующего потока:

поиска одного блокирующего потока составит .

●Аналогично предыдущей идее, однако удалять в процессе обхода в глубину из графа все "лишние" рёбра, т.е. рёбра, вдоль которых не получится дойти до стока.

Это очень легко реализовать: достаточно удалять ребро после того, как мы просмотрели его в обходе в глубину (кроме того случая, когда мы прошли вдоль ребра и нашли путь до стока). С точки зрения реализации, надо просто поддерживать в списке смежности каждой вершины указатель на первое неудалённое ребро, и увеличивать этот указать в цикле внутри обхода в глубину.

Оценим асимптотику этого решения. Каждый обход в глубину завершается либо насыщением как минимум одного ребра (если этот обход достиг стока), либо продвижением вперёд как минимум одного указателя (в противном

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

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

целый порядок эффективностей алгоритма Диница и Эдмондса-Карпа (который ищет один увеличивающий путь за ).

Этот способ решения является по-прежнему простым для реализации, но достаточно эффективным, и потому наиболее часто применяется на практике.

●Можно применить специальные структуры данных — динамические деревья Слетора (Sleator) и Тарьяна (Tarjan)). Тогда каждый блокирующий поток можно найти за время .

Асимптотика

Единичные сети

Единичной называется такая сеть, в которой все пропускные способности равны 0 либо 1, и у любой вершины либо входящее, либо исходящее ребро единственно.

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

Докажем, что на единичных сетях алгоритм Диница даже в простой реализации (которая на произвольных графах отрабатывает за ) работает за время , достигая на задаче поиска

наибольшего паросочетания наилучший из известных алгоритмов — алгоритм Хопкрофта-Карпа. Чтобы доказать