Описание Области
подробнее…
Постановка задачи
В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна. Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.
Дано:
• 1 источник – завод (склад), с которого начинается передача потока (перевозка товара).
• 1 сток – магазин (склад), которым заканчивается передача потока (перевозка товара).
• Набор промежуточных вершин (складов), через которые проходит поток (перевозятся товары).
• Набор дуг (дорог), соединяющих вершины графа. Каждой дуге сопоставляется пропускная способность.
• Величина потока (объем товара) который требуется передать от источника к стоку.
Требуется:
Найти максимально возможную величину потока (объем товара) который можно передать от источника к стоку. Т.е. максимально возможный объем товара, который можно перевезти от завода до магазина.
кратко