Информатика / Алгоритмы и анализ данных

Метод Форда—Фалкерсона: увеличивающий путь потока

Метод Форда—Фалкерсона увеличивает поток по пути в остаточной сети. Прямые остаточные рёбра дают свободную ёмкость, а обратные позволяют отменить часть прежнего решения и перенаправить поток.

Опубликовано: 26 октября 2026 г.Обновлено: 26 октября 2026 г.

Формула

\delta=\min_{e\in P}c_f(e),\quad |f_{\mathrm{new}}|=|f|+\delta,\quad c_f(u,v)=c(u,v)-f(u,v)

Схема После двух увеличений: поток 2

Подписи — поток/ёмкость исходных дуг. По a→b поток отменён; четыре внешние дуги несут по единице.

Обозначения

$f$: допустимый поток, единица потока
$c$: неотрицательная ёмкость исходного ребра, единица потока
$cf$: доступная остаточная ёмкость, включая обратные дуги, единица потока
$P$: путь s→t по положительным остаточным ёмкостям, путь
$δ$: минимальная остаточная ёмкость пути, единица потока

Условия применения

Сеть конечна, источник и сток различны, ёмкости неотрицательны. Начальный поток допустим и сохраняет баланс в промежуточных вершинах. Для гарантии завершения произвольного выбора путей достаточно целых ёмкостей и целого начального потока.

Ограничения

Время зависит от выбора путей; при целых ёмкостях оценка O(E|f*|) псевдополиномиальна. Для произвольных иррациональных ёмкостей неудачный выбор может не завершиться. При вещественной арифметике нужен явный контроль точности и остаточных ёмкостей.

Подробное объяснение

В допустимом потоке каждое ребро не превышает ёмкость, а промежуточная вершина отдаёт столько же, сколько получает. Если в остаточной сети найден путь от s к t, по нему можно провести дополнительный поток δ, равный самой узкой остаточной дуге.

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

На прямых дугах пути поток увеличивают, на обратных уменьшают на одно и то же δ. Внутренние балансы сохраняются, а значение потока возрастает на δ. Как минимум одна остаточная дуга выбранного пути насыщается.

Когда положительного остаточного пути нет, достижимые из s вершины задают разрез, ёмкость которого равна текущему потоку. Это сертификат максимальности. Само правило Форда—Фалкерсона не задаёт, каким поиском выбирать путь: DFS и BFS дают разные оценки времени.

Как пользоваться формулой

Начните с нулевого допустимого потока и создайте для каждой исходной дуги прямую остаточную и обратную отменяющую дугу.
Найдите путь от источника к стоку только по положительным остаточным ёмкостям; запомните направление каждой дуги.
Возьмите минимум ёмкостей пути и увеличьте прямые потоки либо уменьшите обратные на эту одну величину.
Повторяйте поиск до отсутствия пути, затем проверьте ограничения, баланс вершин и равенство потока найденному разрезу.

Историческая справка

Метод Форда—Фалкерсона относится к развитию оптимизации потоков в сетях. Его ключевая идея — не закреплять прежнее распределение навсегда: остаточная сеть допускает отмену и перераспределение потока. Благодаря этому последовательные локальные увеличения могут приводить к глобально максимальному значению.

В алгоритмических изложениях XX–XXI веков метод отделяют от конкретной стратегии поиска пути. Материалы Princeton показывают реализацию потока вместе с остаточными рёбрами, а современные разборы различают общий метод и BFS-вариант Эдмондса—Карпа. Различие существенно для доказательства времени и завершения. Теорема о максимальном потоке и минимальном разрезе даёт завершённому расчёту проверяемый сертификат: сумма ёмкостей разреза совпадает с найденным значением.

Историческая линия формулы

Название связано с Фордом и Фалкерсоном и обозначает увеличение потока по остаточным путям. Выбор пути не фиксирован этим общим методом. BFS-стратегия относится к варианту Эдмондса—Карпа и имеет отдельную оценку сложности, независимую от численных ёмкостей.

Пример

Все пять дуг имеют ёмкость 1: s→a, a→b, b→t, s→b, a→t. Сначала выберем путь s→a→b→t и проведём 1. Прямые дуги этого пути насыщены, но результат ещё не максимален. В остаточной сети появился обратный переход b→a, отменяющий поток по a→b. Второй путь s→b→a→t допускает ещё 1. После него f(s,a)=1, f(a,t)=1, f(s,b)=1, f(b,t)=1, f(a,b)=0. Значение потока 2. Баланс в a и b выполнен; сумма ёмкостей исходящих из s дуг также 2, поэтому больше провести нельзя. Пример показывает необходимость обратной остаточной дуги, которой не было в исходном графе.

Частая ошибка

Нельзя искать следующий путь только среди свободных исходных дуг, забыв обратные. Остаточную дугу не следует путать с физическим каналом. На всех дугах одного увеличения используют один минимум δ. Насыщение первого найденного пути не доказывает максимальность, пока остаётся другой остаточный путь.

Практика

Задачи с решением

Узкое место

Условие. Остаточные ёмкости пути s→a→t равны 5 и 2. На сколько увеличится поток?

Решение. δ=min(5,2)=2. Новые остаточные ёмкости прямых дуг равны 3 и 0.

Ответ. На 2.

Обратная дуга

Условие. По исходной дуге a→b уже течёт 3. В увеличивающем пути прошли b→a с δ=2. Каков новый поток a→b?

Решение. Обратный переход отменяет 2 единицы: 3−2=1.

Ответ. 1.

Дополнительные источники

https://algs4.cs.princeton.edu/64maxflow/
https://cp-algorithms.com/graph/edmonds_karp.html

Связанные формулы

Информатика

Алгоритм Эдмондса—Карпа: поток с поиском в ширину

$P=\operatorname{BFS}(G_f,s,t),\quad\delta=\min_{e\in P}c_f(e),\quad T=O(VE^2)$

Алгоритм Эдмондса—Карпа выбирает увеличивающий путь с минимальным числом остаточных дуг при помощи BFS. Эта стратегия превращает общий метод увеличения потока в алгоритм с оценкой времени O(VE²).

Информатика

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

$\max_f |f|=\min_{s\in S,\ t\notin S}c(S,V\setminus S),\quad c(S,\bar S)=\sum_{u\in S,\ v\notin S}c(u,v)$

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

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

Поиск в ширину, или BFS, находит минимальное число переходов от стартовой вершины в невзвешенном графе. Очередь обрабатывает вершины слоями, поэтому первое открытие уже задаёт кратчайшее расстояние.