Условие задачи
Как послать максимальное количество грузов из начального пункта 1 в конечный пункт 8, если пропускная способность путей между пунктами транспортной сети (4) ограничена (табл. 1)?
Таблица 1 – Исходные данные к задаче о максимальном потоке
Рисунок 4 – Транспортная сеть к задаче о максимальном потоке
Ответ
Очевидно, что максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 1, а именно, 1 единицу в пункт 2, 2 единицы в пункт 3 и 3 единицы в пункт 4 (рис. 5).
Потяни
