Потоки в сетях: алгоритм Форда-Фалкерсона и минимальный разрез

Из пункта А в пункт Б ведёт сеть дорог, у каждой — своя пропускная способность: сколько машин в час она выдерживает. Вопрос диспетчера звучит так: как организовать движение, чтобы через сеть проходило максимум транспорта, и где узкое место? Тот же вопрос стоит перед трубопроводами, дата-центрами и логистикой. На языке графов это задача о максимальном потоке — одна из самых красивых задач дискретной математики, с теоремой, которая находит узкое место быстрее, чем вы успеете сказать «Форда-Фалкерсона».

Сеть, поток, величина потока#

Сеть — ориентированный граф, в котором выделены две вершины: исток $s$ (откуда всё течёт) и сток $t$ (куда всё стекает), а каждое ребро несёт неотрицательное число — пропускную способность $c(e)$. Поток — это функция на рёбрах, подчинённая двум законам:

• ограниченность: поток по ребру не превосходит его пропускную способность, $0\le f(e)\le c(e)$
• сохранение: в каждой промежуточной вершине сколько вошло, столько и вышло — ${\sum }_{in}f={\sum }_{out}f$

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

Рабочий пример на весь урок — сеть из четырёх вершин и пяти рёбер: $s\to a$ с $c=10$, $s\to b$ с $c=5$, $a\to t$ с $c=5$, $a\to b$ с $c=15$, $b\to t$ с $c=10$. Нарисуйте её на бумаге: из истока два выхода, в сток два входа, и одно боковое ребро $a\to b$. Верхняя граница очевидна: из $s$ выходит не больше $10+5=15$. Сможем ли мы эти 15 реализовать — увидим.

Разрез: где сеть ломается#

Разделим вершины на две части: $S$ содержит исток, $T$ содержит сток. Разрезом называют набор рёбер, идущих из $S$ в $T$, а его пропускной способностью — сумму $c(e)$ по этим рёбрам. Смысл простой: разрежьте сеть на «источную» и «сточную» половины — весь поток обязан перебраться через разрез, поэтому

В нашей сети разрез $S=\{s\}$ имеет пропускную способность $10+5=15$; разрез $S=\{s,a\}$ — рёбра $s\to b$ (5), $a\to t$ (5) и $a\to b$ (15), итого 25. Разрезы бывают узкими и широкими, и весь фокус в том, что искать нужно самый узкий. Теорема Форда-Фалкерсона — центральный результат всей темы: максимальный поток равен пропускной способности минимального разреза. Как только вы нашли поток и разрез с одинаковой величиной — оба оптимальны, доказывать больше нечего.

Таблица подсказывает занятную деталь: минимальных разрезов здесь два — $\{s\}$ и $\{s,a,b\}$, оба с потолком 15. Это не редкость: минимальный разрез не обязан быть единственным, зато его величина всегда одна — она и равна максимальному потоку. Практический смысл узкого места тоже читается прямо: чтобы пропустить через сеть больше пятнадцати, недостаточно перекачать больше машин — нужно физически расширять одно из горлышек, скажем ребро $a\to t$.

Алгоритм Форда-Фалкерсона: прокладываем маршруты#

Алгоритм действует по-диспетчерски: пока удаётся найти путь от $s$ к $t$, по которому можно хоть что-то дополнительно протолкнуть, — проталкиваем. Такой маршрут называется дополняющим путём, а его пропускная способность — минимум по рёбрам пути (бутылочное горлышко). Хитрость, на которой держится вся корректность, — остаточная сеть: по каждому ребру мы помним, сколько осталось до предела (прямая резерв), и, главное, разрешаем отменять уже отправленный поток обратным ребром. Отмена — не бухгалтерская условность: именно она позволяет исправлять неудачные ранние решения.

Что здесь поучительно: рёбра $a\to b$ с пропускной способностью 15 так и остались недогруженными — по ним прошло всего 5. Максимум упёрся не в боковое ребро, а в два «горлышка»: $a\to t$ и пара $s\to b$ вместе с $b\to t$. Интуиция «загрузить все трубы до отказа» в сетях не работает — работает баланс целого.

Зачем нужны обратные рёбра#

Покажем на контрпримере, без чего алгоритм разваливается. Возьмём сеть: $s\to a$ (1), $s\to b$ (1), $a\to b$ (1), $a\to t$ (1), $b\to t$ (1). Максимум здесь равен 2: маршрут $s\to a\to t$ плюс маршрут $s\to b\to t$. Но жадный путь $s\to a\to b\to t$ занимает диагональ $a\to b$, и после него прямых маршрутов не остаётся: и $s\to a$, и $b\to t$ заполнены. Без отмены алгоритм застрял бы на потоке 1 — вдвое меньше оптимума.

Обратное ребро спасает: в остаточной сети у занятого $a\to b$ появляется возврат $b\to a$ с остатком 1. Путь $s\to b\to a\to t$ проходит по нему и «разворачивает» диагональ: единица потока по $a\to b$ отменяется, вместо неё отправляются $s\to a\to t$ и $s\to b\to t$. Итог — поток 2. Умение отменять решения и отличает правильный алгоритм от жадной ловушки; та же идея, кстати, нужна в задачах о паросочетаниях, куда потоки сводятся напрямую.

Скорость алгоритма и где это применяется#

Если пропускные способности целые, каждый дополняющий путь добавляет хотя бы единицу, и число итераций не больше величины потока: чистый Форд-Фалкерсон работает за $O(E\cdot |f|)$, где $E$ — число рёбер. Для разумных $|f|$ это отлично, но сеть с пропускной способностью в миллионы заставит алгоритм сделать миллион почти одинаковых шагов. Лекарство — выбирать путь поиском в ширину: алгоритм Эдмондса-Карпа гарантирует не более $O(V\cdot E)$ итераций и итоговую сложность $O(V\cdot E^2)$ — уже без капризов входных данных. Поиск в ширину и в глубину на графах разобран в уроке об обходах.

Сводимость — вторая суперсила темы. Паросочетание «кандидаты — вакансии» превращается в сеть добавлением истока, стока и рёбер единичной пропускной способности: максимальный поток = максимальное число трудоустройств. Так же решаются задачи о перевозках с промежуточными складами, о разбиении изображений на объект и фон, о выборе проектов с общими ресурсами. И проверьте себя на симуляторе ниже: поиск увеличивающего пути — это обычный поиск пути в графе, просто с двумя ограничениями на направление.

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