Потоки в сетях

1. Сеть, пропускная способность, поток

Раньше вес ребра означал длину или время. Теперь представим, что ребро — это труба, по которой течет жидкость (газ, нефть; в интернете — пакеты данных). У каждой трубы есть пропускная способность: больше определенного количества она пропустить не может. Как у дороги: если четырехполосная дорога превращается в трехполосную, возникает узкое горлышко, и четвертую полосу учитывать бессмысленно.

Сеть $G$ — ориентированный граф, в котором:

$V$ — множество вершин, $E$ — множество дуг;
выделены две вершины: исток $s$ (откуда поток вытекает) и сток $t$ (куда поток втекает);
остальные вершины — промежуточные;
на дугах задана функция $c (a)$ — пропускная способность дуги («ширина трубы»).

Поток — функция $f (a)$ на дугах: сколько жидкости реально течет по дуге. Ограничение:

0 \leq f (a) \leq c (a) .

Если у дуги пропускная способность 3, поток 4 по ней пустить нельзя.

2. Разрез сети

Разрез — разбиение всех вершин на два множества $S$ и $T$ так, что исток лежит в одном, сток в другом: $s \in S$ , $t \in T$ . Это не двудольность, мы просто режем граф на две части.

Дуги, пересекающие границу разреза, бывают двух видов:

попутные — идут из части с истоком в часть со стоком ( $S \to T$ );
встречные — идут обратно ( $T \to S$ ).

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

Пример: через границу идут попутные дуги с пропускными способностями $5, 6, 7$ и встречная дуга $7$ . Величина разреза: $5 + 6 + 7 = 18$ , встречная не считается.

Разрезов в сети конечное число: $s$ и $t$ зафиксированы, каждая из остальных $n - 2$ вершин лежит в одной из двух частей, всего $2^{n - 2}$ вариантов. Среди них есть разрез минимальной величины.

Основная теорема

максимальный поток = минимальный разрез

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

все попутные дуги заполнены на 100% ( $f = c$ );
все встречные дуги пусты ( $f = 0$ ).

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

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

3. Алгоритм Форда — Фалкерсона

Идея: пока можно, искать увеличивающий путь из $s$ в $t$ и пускать по нему дополнительный поток. Путь ищем обычным DFS.

Запускаем DFS из $s$ , ищем путь до $t$ по «открытым» дугам (о том, какие дуги открыты, ниже).
На пути находим узкое место, то есть минимум остаточных пропускных способностей. Ровно на эту величину увеличиваем поток вдоль всего пути.
Дуга, у которой $f = c$ , становится закрытой.
Повторяем, пока путь находится. Когда DFS больше не доходит до $t$ , поток максимален.

4. Дивергенция вершины

Для вершины $v$ считаем входящие потоки со знаком « $+$ », исходящие со знаком « $-$ ». Дивергенция $div (v)$ — их сумма.

Для любой вершины, кроме истока и стока, в идеальной модели

div (v) = 0,

то есть сколько пришло, столько и ушло.

Пример: в вершину пришло $7 + 4 = 11$ , ушло $6 + 5 = 11$ , сумма $0$ .

Из истока поток только выходит, в сток только входит, поэтому

div (s) = - div (t) .

Условие $div (v) = 0$ — главный инвариант: любое преобразование потока должно его сохранять. Именно из него получается правило движения против ребра.

5. Движение против ребра

Возьмем сеть, где все пропускные способности равны $1$ . Если выбрать неудачный первый путь, поток 1 заполнит «перемычку» и другого пути по открытым попутным дугам уже нет, хотя максимальный поток здесь равен 2. Как быть?

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

Для трубы с пропускной способностью $c$ и потоком $f$ :

Куда идем	Когда дуга «открыта»	Что делаем с потоком
вдоль дуги	$f < c$	увеличиваем, не больше чем на $c - f$
против дуги	$f > 0$	уменьшаем, не больше чем на $f$

Увеличивающий путь теперь может содержать и те и другие дуги. Узкое место — минимум из всех этих «запасов»: $c - f$ для дуг вдоль и $f$ для дуг против.

Почему инвариант не ломается

Пусть путь входит в вершину $v$ по одной дуге и выходит по другой. Любое изменение на этих двух дугах оставляет баланс прежним:

пришли вдоль дуги ( $+ x$ к притоку), ушли вдоль дуги ( $+ x$ к оттоку): приток и отток выросли поровну;
пришли вдоль дуги ( $+ x$ к притоку), ушли против дуги, которая входит в $v$ ( $- x$ к притоку): приток вырос на $x$ и тут же уменьшился на $x$ , баланс не изменился;
остальные комбинации разбираются так же.

Образно: у вершины был один вход и один выход, мы заменили один из них другим. Вершине все равно, по какой именно дуге пришло и по какой ушло, главное, что сколько вошло, столько и вышло. Поэтому $div (v) = 0$ сохраняется для всех вершин вдоль пути.

Связь с «обратными ребрами»

В учебниках обычно пишут иначе: если по дуге $u \to v$ пустили поток $f$ , то в остаточной сети появляется обратное ребро $v \to u$ с пропускной способностью $f$ . Идти по нему — то же самое, что уменьшать поток на исходной дуге. Преподаватель специально объясняет через дивергенцию, потому что понятие «обратного ребра» на первом знакомстве только путает. Но если вы встретите его в книге или от нейросети, знайте: за ним стоит ровно эта простая идея.

6. Асимптотика

Вещественные пропускные способности

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

работаем в основном с целыми пропускными способностями;
для вещественных вводят $ε$ : если приращение меньше $ε$ , останавливаемся.

Худший случай

DFS находит какой-то путь, и ничего, кроме того, что он найдет путь, если тот существует, не гарантируется.

Возьмем 4 вершины $s, a, b, t$ и дуги $s \to a$ , $s \to b$ , $a \to t$ , $b \to t$ с пропускной способностью $10^{6}$ , а также перемычку $a \leftrightarrow b$ с пропускной способностью $1$ .

Первый путь $s \to a \to b \to t$ дает приращение 1 (узкое место — перемычка).
Второй путь $s \to b \to a \to t$ идет против перемычки и тоже дает всего 1.
Дальше пути «качаются» через перемычку туда-обратно, каждый раз добавляя по единице.

Всего будет порядка $2 \cdot 10^{6}$ итераций, хотя в графе 4 вершины. Если пути выбирать неосторожно, число итераций ограничено только величиной максимального потока:

O ((V + E) \cdot F_{max}) \approx O (E \cdot F_{max}),

где $F_{max}$ — величина максимального потока, а слагаемое $V$ отбрасывают, потому что обычно $V < E$ . Если пропускные способности порядка $10^{9}$ , это совсем плохо. Если же они небольшие (порядка 100) и ребер порядка тысячи, можно не переживать.

7. Сравнение алгоритмов

Алгоритм	Как ищем увеличивающий путь	Асимптотика
Форд — Фалкерсон	DFS	$O (E \cdot F_{max})$
Эдмондс — Карп	BFS, то есть кратчайший по числу ребер путь	$O (V \cdot E^{2})$
Диниц	строит слоистую сеть и DFS-ом проталкивает поток по ней	идея объединяет DFS и BFS, оценка не зависит от $F_{max}$

Эдмондс — Карп выбирает путь с наименьшим числом дуг. То есть идет сортировка по удаленности от истока.

Алгоритм Диница разберем на следующей лекции вместе с кодом:

BFS от истока строит слоистую сеть: слои определяются удаленностью вершины от $s$ ;
вдоль слоистой сети DFS аккуратно проталкивает поток, пока это возможно;
затем слоистая сеть строится заново, и все повторяется, пока $t$ достижим.

Известная оценка для Диница (на лекции ее не выводили, показываем для справки): $O (V^{2} E)$ .

Потоки в сетях ​

1. Сеть, пропускная способность, поток ​

2. Разрез сети ​

Основная теорема ​

3. Алгоритм Форда — Фалкерсона ​

4. Дивергенция вершины ​

5. Движение против ребра ​

Почему инвариант не ломается ​

Связь с «обратными ребрами» ​

6. Асимптотика ​

Вещественные пропускные способности ​

Худший случай ​

7. Сравнение алгоритмов ​