Максимальный поток, Данциг.

Описание Области

подробнее…

Постановка задачи

В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна. Задача о максимальном потоке является частным случаем более трудных задач, как например задача о циркуляции.

Дано:

  1 источник – завод (склад), с которого начинается передача потока (перевозка товара).

  1 сток – магазин (склад), которым заканчивается передача потока (перевозка товара).

  Набор промежуточных вершин (складов), через которые проходит поток (перевозятся товары).

  Набор дуг (дорог), соединяющих вершины графа. Каждой дуге сопоставляется пропускная способность.

  Величина потока (объем товара) который требуется передать от источника к стоку.

Требуется:

Найти максимально возможную величину потока (объем товара) который можно передать от источника к стоку. Т.е. максимально возможный объем товара, который можно перевезти от завода до магазина.

кратко