Что такое максимальный поток в сети и из каких частей он состоит (исток, сток, остаточная сеть)?

Question

Готовлюсь к олимпиадам, вижу задачи «найти максимальный поток», но плохо понимаю саму модель. Что такое сеть, исток и сток, пропускные способности? И что за «остаточная сеть», про которую всё время говорят при объяснении Форда-Фалкерсона? Можно строго, но понятно.

Матвей Крылов · Accepted Answer

Сеть — это ориентированный граф, где у каждого ребра $(u,v)$ есть пропускная способность $c(u,v) \ge 0$. Выделены две вершины: исток $s$ (откуда «течёт») и сток $t$ (куда «втекает»). Поток — это функция $f(u,v)$, удовлетворяющая трём условиям: 1. Ограничение пропускной способности: $0 \le f(u,v) \le c(u,v)$. 2. Антисимметрия (в одной из формулировок): $f(u,v) = -f(v,u)$. 3. Сохранение потока: для любой вершины кроме $s$ и $t$ сумма входящего потока равна сумме исходящего. Величина потока — это суммарный поток, выходящий из истока (он же равен втекающему в сток). Остаточная сеть — ключевая иде…

Диана Герасимова · Answer

Добавлю практическую деталь, на которой все спотыкаются при первой реализации. Обратные рёбра удобно хранить парами в одном массиве рёбер: ребро с индексом $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;. Это и есть обновление остаточной сети. Обратное ребро стартует с нулевой пропускной — но по мере пуска прямого потока его остаток растёт, и его можно использовать для отката.

Что такое максимальный поток в сети и из каких частей он состоит (исток, сток, остаточная сеть)?

2 ответа

Ваш ответ