Калькулятор максимального потока и минимального разреза
Найдите максимальный поток в транспортной сети из истока в сток. Калькулятор использует метод Форда — Фалкерсона с поиском увеличивающих путей в ширину (алгоритм Эдмондса — Карпа), показывает каждый увеличивающий путь, поток и остаточную пропускную способность каждой дуги, минимальный разрез, равный максимальному потоку, и рисунок сети.
Подписи дуг — «поток / пропускная способность». Зелёные дуги несут поток, красные пунктирные — дуги минимального разреза. Голубые вершины лежат на стороне истока.
Рисунок строится для сетей до 60 вершин.
Увеличивающие пути
Поток по дугам
Задача о максимальном потоке
Транспортная сеть — ориентированный граф, у каждой дуги которого есть пропускная способность: сколько единиц груза, воды, данных или машин она может пропустить за единицу времени. В сети выделены исток s, откуда поток выходит, и сток t, куда он приходит. Поток должен удовлетворять двум условиям: по каждой дуге идёт не больше её пропускной способности, а в каждую промежуточную вершину входит столько же, сколько выходит. Требуется найти наибольшую величину потока из s в t.
Метод Форда — Фалкерсона
Начинают с нулевого потока и строят остаточную сеть: у дуги u → v остаётся пропускная способность c − f, а в обратную сторону появляется дуга v → u с пропускной способностью f — по ней поток можно «отменить». Затем ищут увеличивающий путь из s в t по дугам с положительной остаточной способностью, пропускают по нему поток, равный наименьшей остаточной способности на пути, и повторяют, пока такие пути есть.
Если искать увеличивающий путь обходом в ширину (кратчайший по числу дуг), получается алгоритм Эдмондса — Карпа. Он гарантированно завершается за O(n · m²) операций при любых, в том числе дробных, пропускных способностях. Именно этот вариант использует калькулятор.
Минимальный разрез
Разрез делит вершины на две части: S с истоком и T со стоком. Пропускная способность разреза — сумма пропускных способностей дуг, идущих из S в T. Любой поток не больше пропускной способности любого разреза, а по теореме Форда — Фалкерсона максимальный поток равен минимальному разрезу. Когда увеличивающих путей больше нет, множество S — это вершины, достижимые из истока в остаточной сети, а дуги из S в T и образуют минимальный разрез. Все они насыщены — загружены полностью. Это «узкое место» сети: чтобы увеличить поток, нужно расширять именно эти дуги.
Где применяется
Потоки в сетях описывают транспортные и трубопроводные системы, пропускную способность компьютерных сетей и электросетей. К задаче о максимальном потоке сводятся задача о назначениях и паросочетаниях в двудольном графе (например, распределение работ между исполнителями), задачи о непересекающихся путях, сегментация изображений и составление расписаний.
Пример
В сети из примера 6 вершин и 9 дуг. Максимальный поток из S в T равен 23. Минимальный разрез: S = {S, A, B, D}, T = {C, T}, в него входят дуги A → C (12), D → C (7) и D → T (4), сумма 12 + 7 + 4 = 23. Дуги разреза полностью загружены, и больше 23 единиц из S в T пропустить нельзя.
Неориентированная сеть
Если выбрать неориентированную сеть, каждое ребро сможет пропускать поток в любую сторону, но не больше своей пропускной способности. В таблице потоков направление указывается стрелкой.
Комментарии и вопросы