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

По ориентированной сети пропускных способностей найти поток из источника в сток и проверить его значение ёмкостью разреза.

Ваш пример

Дроби вводите как 1/3, десятичные числа — 0.5 или 0,5. Таблицы: числа через пробел, строки с новой строки. Формулы не выполняются.

Разбор примера

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

Проверяемый расчёт
ОткудаКудаПотокЁмкость
1233
1322
2311
2422
3433
  1. Пути увеличения: 3.
  2. Сток недостижим в остаточной сети.
  3. Ёмкость разреза точно равна значению потока; баланс промежуточных вершин проверен.

Метод и условия расчёта

В остаточной сети ищем кратчайший по числу рёбер увеличивающий путь.

После остановки достижимые из источника вершины задают разрез; его ёмкость должна совпасть со значением потока.

Теория к методу

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

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

Пример: В сети s→a ёмкости 3, s→b ёмкости 2, a→b ёмкости 1, a→t ёмкости 2, b→t ёмкости 3 поток достигает пяти.

Разрез, отделяющий только источник, имеет ёмкость 3+2=5. Поток той же величины допустим, поэтому верхняя и нижняя границы совпадают и максимум доказан.

Вопросы по теме

Можно вводить обратные дуги?

Да. Остаточная сеть хранит отмену потока вместе с исходной ёмкостью обратного направления.

Сумма потоков всех дуг — значение?

Нет. Значение — чистый исходящий поток источника; суммирование всех дуг многократно считает проход через промежуточные вершины.

Графы и маршруты: объяснения, примеры и практика

Основа объяснения

Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.