Что такое максимальный поток в сети и из каких частей он состоит (исток, сток, остаточная сеть)?
Готовлюсь к олимпиадам, вижу задачи «найти максимальный поток», но плохо понимаю саму модель. Что такое сеть, исток и сток, пропускные способности? И что за «остаточная сеть», про которую всё время говорят при объяснении Форда-Фалкерсона? Можно строго, но понятно.
2 ответа
Сеть — это ориентированный граф, где у каждого ребра $(u,v)$ есть пропускная способность $c(u,v) \ge 0$. Выделены две вершины: исток $s$ (откуда «течёт») и сток $t$ (куда «втекает»). Поток — это функция $f(u,v)$, удовлетворяющая трём условиям:
- Ограничение пропускной способности: $0 \le f(u,v) \le c(u,v)$.
- Антисимметрия (в одной из формулировок): $f(u,v) = -f(v,u)$.
- Сохранение потока: для любой вершины кроме $s$ и $t$ сумма входящего потока равна сумме исходящего.
Величина потока — это суммарный поток, выходящий из истока (он же равен втекающему в сток).
Остаточная сеть — ключевая идея. Для текущего потока $f$ остаточная пропускная способность ребра — это $c_f(u,v) = c(u,v) - f(u,v)$, то есть «сколько ещё можно пустить». Важно: если по ребру $(u,v)$ уже течёт $f$, то в остаточной сети появляется обратное ребро $(v,u)$ с пропускной способностью $f(u,v)$ — оно позволяет «отменить» (откатить) часть ранее пущенного потока. Именно поэтому жадность без обратных рёбер не работает, а с ними — даёт оптимум.
Алгоритмы (Форд-Фалкерсон, Эдмондс-Карп, Диниц) ищут увеличивающий путь $s \to t$ в остаточной сети и пускают по нему поток, пока такие пути есть. Когда путей нет — поток максимален.
Добавлю практическую деталь, на которой все спотыкаются при первой реализации. Обратные рёбра удобно хранить парами в одном массиве рёбер: ребро с индексом $i$ и его обратное с индексом $i \oplus 1$ (XOR с единицей). Тогда edges[i^1] — это всегда «обратное» к edges[i]. При добавлении ребра сразу кладём два:
struct Edge { int to, cap; };
vector<Edge> e;
vector<vector<int>> g; // g[v] — индексы рёбер из v
void add_edge(int u, int v, int cap) {
g[u].push_back(e.size()); e.push_back({v, cap});
g[v].push_back(e.size()); e.push_back({u, 0}); // обратное, cap=0
}
Когда пускаем $\Delta$ по ребру $i$: e[i].cap -= d; e[i^1].cap += d;. Это и есть обновление остаточной сети. Обратное ребро стартует с нулевой пропускной — но по мере пуска прямого потока его остаток растёт, и его можно использовать для отката.