Максимальный поток и сертификат минимального разреза
По ориентированной сети пропускных способностей найти поток из источника в сток и проверить его значение ёмкостью разреза.
Ваш пример
Разбор примера
Максимальный поток = 5; разрез = 5
| Откуда | Куда | Поток | Ёмкость |
|---|---|---|---|
| 1 | 2 | 3 | 3 |
| 1 | 3 | 2 | 2 |
| 2 | 3 | 1 | 1 |
| 2 | 4 | 2 | 2 |
| 3 | 4 | 3 | 3 |
- Пути увеличения: 3.
- Сток недостижим в остаточной сети.
- Ёмкость разреза точно равна значению потока; баланс промежуточных вершин проверен.
Метод и условия расчёта
В остаточной сети ищем кратчайший по числу рёбер увеличивающий путь.
После остановки достижимые из источника вершины задают разрез; его ёмкость должна совпасть со значением потока.
Теория к методу
Допустимый поток соблюдает ёмкости и баланс промежуточных вершин. Для доказательства его максимальности после остановки строят разрез по остаточной достижимости: если ёмкость разреза равна значению потока, улучшение невозможно.
Начните с нулевого потока. Остаточная сеть показывает, сколько ещё можно добавить по каждому направлению и сколько уже отправленного можно отменить в обратном. Увеличивающий путь соединяет источник со стоком только по положительным остаточным ёмкостям. В выбранном варианте путь ищется в ширину, то есть по минимальному числу дуг. Добавляемая величина равна наименьшей остаточной ёмкости на этом пути.
Пример: В сети s→a ёмкости 3, s→b ёмкости 2, a→b ёмкости 1, a→t ёмкости 2, b→t ёмкости 3 поток достигает пяти.
Разрез, отделяющий только источник, имеет ёмкость 3+2=5. Поток той же величины допустим, поэтому верхняя и нижняя границы совпадают и максимум доказан.
Вопросы по теме
Можно вводить обратные дуги?
Да. Остаточная сеть хранит отмену потока вместе с исходной ёмкостью обратного направления.
Сумма потоков всех дуг — значение?
Нет. Значение — чистый исходящий поток источника; суммирование всех дуг многократно считает проход через промежуточные вершины.
Графы и маршруты: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.