Целочисленная транспортная сеть

Целочисленная транспортная сеть

Целочисленная транспортная сеть - транспортная сеть, все пропускные способности ребер которой - целые числа (возможно 0). Для целочисленной транспортной сети очевидно, что в ней существует максимальный поток, являющийся целочисленным. Это доказывается алгоритмом, основанном на остаточный путь в транспортной сети.

Алгоритм

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