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

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

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

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

Формула

\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)

Схема Разрез перед t: ёмкость 2 + 4 = 6

Оранжевые исходные дуги образуют минимальный разрез S={s,a,b}. Числа показывают ёмкости.

Обозначения

$|f|$: чистый выход потока из источника, единица потока
$S$: сторона разреза с источником, без стока, множество
$c(S,S̄)$: сумма ёмкостей исходных дуг из S наружу, единица потока
$s,t$: источник и сток, вершины

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

Рассматривается конечная ориентированная сеть с неотрицательными ёмкостями. Поток соблюдает ограничения дуг и баланс промежуточных вершин. Разрез разбивает все вершины на две части и обязательно отделяет источник от стока.

Ограничения

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

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

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

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

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

Сертификат удобно проверять отдельно от программы поиска. Достаточно списка потоков на дугах, проверки балансов и множества S. Максимум может иметь несколько разных распределений и несколько минимальных разрезов; равенство значений не требует их единственности.

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

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

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

Теорема max-flow/min-cut объединяет две постановки: провести как можно больше и отделить источник минимальной суммой ёмкостей. Остаточная сеть делает это равенство вычислительным: когда увеличение невозможно, достижимость непосредственно строит минимальный разрез.

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

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

Равенство максимального потока и минимального разреза относится к классической теории сетевых потоков и связано с методом Форда—Фалкерсона. Здесь используется конструктивное доказательство через отсутствие остаточного пути, а не утверждение о единственности оптимума.

Пример

Дуги s→a=4, s→b=3, a→b=2, a→t=2, b→t=4. Допустимый поток зададим так: s→a=3, s→b=3, a→b=1, a→t=2, b→t=4. Балансы a:3=1+2 и b:3+1=4, значение потока 6. Выберем S={s,a,b}; наружу идут a→t и b→t с общей ёмкостью 2+4=6. Поэтому поток максимален. Независимый перебор остальных разрезов даёт ёмкости: {s} — 7; {s,a} — 7; {s,b} — 8. Минимум действительно 6. В расчёт разреза включались ёмкости исходных дуг нужного направления, а не текущие остаточные значения. Дуг в источник в этой сети нет, поэтому чистый выход равен сумме двух выходящих потоков.

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

Сумма всех рёбер, пересекающих границу в обе стороны, не является ёмкостью ориентированного разреза. Значение потока — чистый выход, если в источник есть входящие дуги. Равенство с разрезом имеет смысл только после проверки допустимости потока. Один большой разрез не опровергает максимальность меньшего потока.

Практика

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

Верхняя граница

Условие. Найден допустимый поток 7 и разрез ёмкостью 9. Можно ли объявить поток максимальным?

Решение. Известно лишь 7≤максимум≤9. Равенства границ нет; нужен лучший разрез или увеличение.

Ответ. Нет, сертификат ещё не получен.

Совпавшие оценки

Условие. Допустимый поток равен 4, а исходящие дуги разреза имеют ёмкости 1 и 3. Каков максимум?

Решение. Ёмкость разреза 1+3=4, совпадает с допустимым потоком.

Ответ. Максимум 4; этот разрез минимален.

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

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

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

Информатика

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

$\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)$

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

Информатика

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

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

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

Информатика

Алгоритм Куна: увеличивающий путь паросочетания

$M_{\mathrm{new}}=M\triangle P,\qquad |M_{\mathrm{new}}|=|M|+1,\qquad T=O(|L|E)$

Алгоритм Куна ищет максимальное по числу пар паросочетание в двудольном графе. Увеличивающий путь чередует свободные и занятые рёбра; смена их принадлежности освобождает место и добавляет одну новую пару.