EssayAI
Блог
Блог
Математика и алгоритмы

Теорема Форда-Фалкерсона о максимальном потоке

8 ноября 2026Время чтения: 9 минут
#теория графов#максимальный поток#минимальный разрез#теорема Форда-Фалкерсона#дискретная математика
Теорема Форда-Фалкерсона о максимальном потоке

Как доказать, что по сети нельзя передать больше груза, чем уже передано? Одного удачного расписания недостаточно: возможно, существует более хитрое распределение. Теорема Форда-Фалкерсона даёт второй объект для проверки - разрез, отделяющий источник от стока. Если ёмкость разреза равна величине найденного потока, решение оптимально.

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

Поток и ограничения сети

Пусть дан конечный ориентированный граф G=(V,E)G=(V,E), источник ss и отличный от него сток tt. Каждому ребру приписана конечная неотрицательная пропускная способность c(u,v)c(u,v). Поток f(u,v)f(u,v) показывает, сколько проходит по ребру за единицу времени. Требуются два условия:

  1. На каждом ребре 0≤f(u,v)≤c(u,v)0\leq f(u,v)\leq c(u,v).
  2. В каждой промежуточной вершине сумма входящих потоков равна сумме исходящих.

Величина ∣f∣|f| - суммарный поток из источника минус поток, входящий в источник. По закону сохранения она равна чистому притоку в сток. Такой учёт работает и тогда, когда в источник входят рёбра или из стока выходят рёбра. Нулевой поток всегда допустим, а способности ограничивают значение сверху.

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

В сети по очереди выделяются три пути из источника в сток, по которым можно добавить 2, 2 и 1 единицу потока.

Что такое разрез

Разрез (S,T)(S,T) - разбиение вершин на две части: s∈Ss\in S, t∈Tt\in T. Его ёмкость - сумма способностей рёбер, направленных из SS в TT:

c(S,T)=∑u∈S, v∈Tc(u,v).c(S,T)=\sum_{u\in S,\,v\in T}c(u,v).

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

Для любого допустимого потока суммируем закон сохранения по вершинам SS. Внутренние рёбра взаимно сокращаются, поэтому

∣f∣=∑u∈S, v∈Tf(u,v)−∑u∈T, v∈Sf(u,v)≤c(S,T).|f|=\sum_{u\in S,\,v\in T}f(u,v)-\sum_{u\in T,\,v\in S}f(u,v)\leq c(S,T).

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

Формулировка теоремы

Для конечной сети с неотрицательными конечными способностями максимальная величина допустимого потока равна минимальной ёмкости разреза:

max⁡f∣f∣=min⁡s∈S, t∈Tc(S,T).\max_f |f|=\min_{s\in S,\,t\in T}c(S,T).

Левая часть ищет лучший способ передачи, правая - самое сильное ограничение среди разрезов. Равенство утверждает, что найдутся поток и разрез, у которых эти числа совпадают. Именно это позволяет проверять оптимальность двумя короткими свидетелями: допустимым потоком и разрезом той же ёмкости. Результат изложен в оригинальной работе Форда и Фалкерсона.

Числовой пример и сертификат оптимальности

Обозначим источник буквой И, сток - С. Внутренние вершины А и Б. Зададим пять рёбер и выберем такой поток:

РеброСпособностьПоток
И → А33
И → Б22
А → Б11
А → С22
Б → С33

На А приходит 3 и уходит 1+2=31+2=3; на Б приходит 2+1=32+1=3 и уходит 3. Ни одна способность не превышена. Из источника выходит 5 единиц, значит, поток величины 5 существует. Его можно получить по путям И → А → С, И → Б → С и И → А → Б → С, добавив соответственно 2, 2 и 1.

Поток и способности на пяти рёбрах сети: поток равен 5 и совпадает с ёмкостью разреза у источника
Поток и способности на пяти рёбрах сети: поток равен 5 и совпадает с ёмкостью разреза у источника

Возьмём S={И}S=\{\text{И}\}: из него выходят рёбра способностей 3 и 2, поэтому ёмкость разреза равна 5. Любой поток не больше 5, а наш поток равен 5. Следовательно, он максимален, а этот разрез минимален. Не нужно проверять все варианты потока: равные нижняя и верхняя оценки уже служат доказательством.

В калькуляторе способность А → С равна xx. Четыре возможные стороны источника дают ёмкости 55, 3+x3+x, 66, 3+x3+x. Минимум равен min⁡(5,3+x)\min(5,3+x): при x=0x=0 максимум равен 3, при x=1x=1 - 4, а при x≥2x\geq 2 - 5. Дальше ограничение у источника не исчезает, даже если ребро А → С усилить.

Почему возникает равенство: остаточная сеть

Верхняя оценка сама по себе ещё не доказывает теорему: надо найти разрез, для которого она достигается. Для допустимого потока строят остаточную сеть. У ребра u→vu\to v прямая остаточная способность равна c(u,v)−f(u,v)c(u,v)-f(u,v), а обратная возможность v→uv\to u равна f(u,v)f(u,v). Обратный ход означает возможность уменьшить уже назначенный поток; он не требует существования отдельного исходного ребра v→uv\to u. Если такое ребро есть, его вклад в остаточную способность учитывают отдельно или суммируют.

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

Обратно, предположим, что такого пути нет. Пусть SS состоит из всех вершин, достижимых из ss в остаточной сети, а T=V∖ST=V\setminus S. Сток лежит в TT. Каждое исходное ребро из SS в TT насыщено: иначе его прямая остаточная дуга сделала бы конец достижимым. Поток по любому исходному ребру из TT в SS равен нулю: иначе обратная остаточная дуга вела бы из SS в TT.

Подставляя эти два факта в формулу чистого потока через разрез, получаем ∣f∣=c(S,T)|f|=c(S,T). Верхняя оценка сразу показывает, что поток максимален, а разрез минимален. Таким образом, отсутствие дополняющего пути, максимальность потока и наличие равного по величине разреза эквивалентны. Это рассуждение применимо и к вещественным способностям; для нахождения потока при этом важно отдельно выбрать гарантированно завершающийся алгоритм.

Зачем обратная дуга на практике

Рассмотрим другую маленькую сеть: все пять способностей на рёбрах И → А, И → Б, А → Б, А → С и Б → С равны единице. Если сначала отправить единицу по пути И → А → Б → С, оба ребра в сток выглядят не одинаково: через А → С ещё можно пройти, но попасть в А напрямую уже нельзя. Наивный поиск только по свободным исходным рёбрам остановится с потоком один.

В остаточной сети есть путь И → Б → А → С. Его среднее звено Б → А отменяет прежнюю единицу на ребре А → Б. После изменения получаются два обычных пути И → А → С и И → Б → С, каждый с потоком один. Рёбра исходного графа не изменились: обратная дуга лишь позволила пересмотреть распределение. Разрез у источника имеет ёмкость два и подтверждает оптимальность нового решения.

Как использовать теорему в задачах

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

При анализе узкого места важно различать одно найденное ограничение и все ограничения сети. Увеличение способности ребра минимального разреза не обязано увеличить максимум: может существовать другой минимальный разрез, который это ребро не пересекает. Например, в исходной сети из таблицы есть несколько разрезов ёмкости пять. Чтобы предсказать эффект изменения, нужно пересчитать ограничения, а не ориентироваться только на одну картинку.

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

Модель подходит для распределения ограниченных ресурсов, пропускной способности коммуникационных сетей и планирования перевозок при заданных ограничениях. Двудольное паросочетание также можно представить потоком с единичными способностями: подробнее о дополняющих путях рассказывает алгоритм Куна, а соответствие пар и покрытий изучает теорема Кёнига. В других задачах графов пути служат иной цели: алгоритм Беллмана-Форда ищет кратчайшие пути с учётом весов, а не распределяет поток.

Частые ошибки

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

FAQ

Разрез и максимальный поток обязательно единственны?

Нет. Разные потоки могут иметь одинаковую максимальную величину, и несколько разрезов могут иметь минимальную ёмкость. В примере при x=2x=2 минимальных разрезов три.

Нужны ли целые способности для теоремы?

Нет, равенство верно и для конечных неотрицательных вещественных способностей. Целочисленность дополнительно гарантирует существование целого оптимального потока.

Можно ли найти разрез до потока?

Да. Любой разрез даёт верхнюю оценку. Если затем построен допустимый поток той же величины, оба объекта оптимальны; знать заранее, что разрез минимален, не требуется.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Максимальный поток: алгоритм Форда-Фалкерсона

Максимальный поток: алгоритм Форда-Фалкерсона

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

8 ноября 20269 минут
Алгоритм Эдмондса-Карпа: поиск максимального потока

Алгоритм Эдмондса-Карпа: поиск максимального потока

Алгоритм Эдмондса-Карпа находит максимальный поток в сети: BFS ищет дополняющий путь, что даёт полиномиальную сложность. Разбираем идею, реализацию и оценку.

13 февраля 202610 минут
Доминирующее множество в графе: определение и примеры

Доминирующее множество в графе: определение и примеры

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

8 ноября 20268 минут
Гиперграф: что это такое и как его построить

Гиперграф: что это такое и как его построить

Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

8 ноября 20268 минут
Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях: формула, доказательство и примеры

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

8 ноября 20267 минут
Рёберный граф: построение, свойства и примеры

Рёберный граф: построение, свойства и примеры

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

8 ноября 20268 минут