Информатика · объяснение и практика

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

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

Синие фигурные скобки держат между собой оранжевый квадрат.

Вузовский уровень · Все вузовские темы

В теме Графы и маршруты · Учебная карта

Главная мысль

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

Метод и условия

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

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

Проверка и типичная ошибка

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

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

Пример

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

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

От чтения к действию

А теперь — вы

Какие ёмкости суммируются в сертификате разреза?

Частые вопросы

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

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

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

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться