Максимальный поток
Потоком в ориентированном графе называется отображение F из множества его
рёбер в какое-нибудь числовое множество такое, что для любой вершины v
верно следующее: сумма F от всевозможных рёбер с концом v равна сумме
F от всевозможных рёбер с началом v.
Традиционно значения отображения F называются токами, а определение
потока, грубо говоря, звучит как «в каждой вершине сумма входящих
токов равна сумме исходящих». Типичный пример потока — токи
в электрической цепи.
Некоторые комбинаторные задачи о распределении ресурсов (типичный пример: задача о максимальном паросочетании) сводятся к так называемой задаче о максимальном потоке. Постановка её следующая:
- на каждом ребре графа задаётся пропускная способность — действительное неотрицательное число
- в граф добавляется ребро
Eбез пропускной способности; его начало называется стоком, а конец — источником - рассматриваются только потоки с действительными неотрицательными токами, не превосходящими пропускные способности соответствующих рёбер
- требуется найти поток, максимизирующий ток на ребре
E
Часто ребро E вообще исключают из разговора, говоря вместо
«ток на E» просто «ток от источника до стока».
В таком случае сумма выходящих из источника токов
должна быть на этот самый ток больше суммы входящих в него токов.
На этот же ток сумма входящих в сток токов должна быть больше
суммы токов, выходящих из него.
Паросочетание как поток
Напомним, что паросочетанием называется набор непересекающихся рёбер в двудольном графе (говоря двудольный мы имеем в виду актуально двудольный — в котором вершины уже поделены на два класса, а рёбра бывают только вида «из одного класса в другой»).
Почти всегда на практике одной долей такого графа служит некоторый набор множеств, второй долей — объединение этих множеств, а рёбрами — принадлежности элементов множествам.
Если в двудольный граф добавить вершины A и B, из A пустить по одному
ребру в каждую вершину первой доли, из каждой вершины второй доли пустить
ребро в B, а затем каждому ребру назначить пропускную способность 1,
то целочисленный поток от A до B в таком графе эквивалентен паросочетанию
в исходном графе.
Переформулировка задачи
Решать задачу о максимальном потоке в том виде, в котором она поставлена, неудобно. Преобразуем её следующим образом: для каждой пары вершин исходного графа все рёбра, их соединяющие, объеденим в одно (произвольного направления) с нижним и верхним ограничениями на ток по нему (эти два ограничения — суммы пропускных способностей в двух возможных направлениях).
Поток в таком графе нетрудно преобразовать в поток в исходном, причём такое преобразование определено не однозначно, в отличие от «обратного». Как мы увидим позже, избавление от этой неоднозначности очень сильно упрощает задачу о максимальном потоке.
Алгоритм Форда-Фалкерсона
Перед тем как изложить алгоритм решения, договоримся об одном незначительном, но удобном упрощении: будем считать, что все токи и все пропускные способности целые. После того, как алгоритм будет изложен для целочисленных потоков, мы сделаем отдельное замечание о том, как действовать в нецелочисленном случае.
Алгоритм Форда-Фалкерсона заключается в построении последовательности потоков такой, что в каждом потоке этой последовательности (кроме начального) ток от источника к стоку строго больше, чем в предыдущем.
Начальный поток — нулевой.
Имея поток, следующий строится так: ищется простой (т.е. проходящий по каждому
ребру не более одного раза) путь от источника к стоку
в остаточном графе. Остаточный граф определён так: ребро
от вершины a до вершины b есть тогда и только тогда, когда
ток от a до b хотя бы на единицу меньше пропускной способности в
соответствующую сторону. Например, если рассмотреть граф из одного ребра
от a до b с ограничениями тока -1 и 1, то остаточный граф устроен так:
- если по ребру идёт ток -1, в остаточном есть только ребро от
aдоb - если по ребру идёт ток 1, в остаточном есть только ребро от
bдоa - если по ребру идёт ток 0, в остаточном графе есть рёбра как от
aдоb, так и отbдоa
Если путей от источника до стока в остаточном графе нет, то алгоритм завершается. Если же такой путь есть, то токи вдоль него увеличиваются на единицу.
Алгоритм Форда-Фалкерсона не постулирует конкретный способ поиска пути в остаточном графе. Например, если такой поиск происходит «в ширину», то результирующий алгоритм носит имена Эдмондса и Карпа.
В качестве оптимизации можно на каждом шаге увеличивать ток не на единицу, а на минимальную ненулевую разницу между токами потока и соответствующими пропускными способностями рёбер. Заодно такой метод действует и для нецелочисленных потоков (с одной оговоркой — можно подобрать нецелые пропускные способности, приводящие к бесконечной последовательности потоков).
Почему оно работает?
Собственно, нужно доказать, что последний поток в последовательности даёт максимально возможный ток от источника до стока.
Самая главная хитрость доказательства — взглянуть на правильный набор рёбер. Например, подойдёт такой: один конец — вершина из множества тех, до которых можно дойти от источника по рёбрам остаточного графа; другой конец — вершина не из этого множества. Все такие рёбра обладают следующим свойством: на каждом достигнута максимальная пропускная способность, причём в направлении «от источника» (это напрямую следует из определения остаточного графа).
Осталось заметить два факта (оба следуют из определения потока):
- ток от источника к стоку равен суммарной пропускной способности рассмотренных нами рёбер
- ток от источника к стоку не может превосходить эту самую суммарную пропускную способность
Значит, мы нашли поток с максимально возможным током от источника к стоку.
Практическая реализация
В главе про обходы графов мы рассматривали вариант поиска в глубину, строящий путь (а не границу множества обработанных вершин):
std::set<int> component(Graph &g, int v) {
std::vector<int> path{v};
std::set<int> visited{};
while (path.size() > 0) {
int current_vertex = path.back();
visited.insert(current_vertex);
bool found_new = false;
auto n = neighbors(g,current_vertex);
for (int i : n) {
if (visited.count(i) == 0) {
path.push_back(i);
found_new = true;
break;
}
}
if (found_new) { continue; }
path.pop_back();
}
return visited;
}
Для нужд алгоритма Форда-Фалкерсона он неплохо подходит, но его нужно модифицировать для работы с остаточным графом.
Сначала модифицируем сам тип «граф»:
using Vertex = int;
using Capacity = int;
using Graph = std::map<Vertex,std::map<Vetrex,Capacity>>;
void addEdge(Graph &g, Vertex i, Vertex j, Capacity c) {
g[i][j] += c;
g[j][i]; // помечаем, что i -- сосед j
}
using Current = int;
using Flow = std::map<Vertex,std::map<Vertex,Current>>;
std::set<Vertex> neighbors(Graph &g, Flow &f, int v) {
std::set<Vertex> res;
for (auto x : g[v]) {
// договоримся хранить ток на ребре (a,b) сразу в
// двух рёбрах так, чтобы: f[a][b] == -f[a][b]
auto current = f[v][x.first];
if (current < x.second) { res.insert(x.first); }
}
return res;
}
На а теперь — поиск пути в остаточном графе:
std::vector<Vertex>
find_residual_path(Graph &g, Flow &f, Vertex src, Vertex dst) {
std::vector<Vertex> path{src};
std::set<Vertex> visited{};
while (path.size() > 0) {
Vertex current_vertex = path.back();
// главное -- вовремя остановиться
if (current_vertex == dst) { break; }
visited.insert(current_vertex);
bool found_new = false;
auto n = neighbors(g,f,current_vertex);
for (Vertex i : n) {
if (visited.count(i) == 0) {
path.push_back(i);
found_new = true;
break;
}
}
if (found_new) { continue; }
path.pop_back();
}
return path; // теперь возвращаем путь, а не связную компоненту
}
Ну и, наконец, Форд-Фалкерсон:
Flow find_max_flow(Graph &g, Vertex src, Vertex dst) {
Flow f;
for (;;) {
auto path = find_residual_path(g, f, src, dst);
if (path.size() == 0) { break; }
for (size_t i = 1; i < path.size(); i++) {
Vertex u = path[i-1];
Vertex v = path[i];
f[u][v] += 1;
f[v][u] -= 1;
}
}
return f;
}