7.7. Максимальный поток в транспортной сети

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

теоремы 7.5 и найдем последовательность потоков имеющих величины В конечном счете мы получим поток имеющий максимальнуювеличину. Согласно теореме 7.5 это произойдет при т. е. когда один или несколько разрезов будут насыщены, это означает, что для каждой дуги и для каждой дуги Прежде чем описать алгоритм построения такой последовательности допустимых потоков, видоизменим введенный ранее граф приращений. Будем считать, что каждой дуге в сети в графе соответствуют две дуги Припишем каждой дуге длину, пользуясь следующими соотношениями:

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

Далее, через будет обозначен граф приращений (структура которого не зависит от а через функция расстояния, связанная с потоком имеющим величину

Алгоритм определения максимального потока:

1. Положим и возьмем в качестве поток, тождественно равный нулю по каждой дуге.

2. Пользуясь функцией расстояния определим кратчайшее расстояние между и, и (Это можно сделать, используя метод пометок, описанный в главе

3. Если расстояние, определенное на втором шаге, конечно, то обозначим через С любой простой путь из кратчайшей длины, и пусть обозначает

соответствующий простой поток по цепи в сети Положим и повторим шаг 2, заменяя на

4, Если кратчайшее расстояние от до равно то является максимальным потоком, и на этом алгоритм работу заканчивает.

Такая процедура имеет один серьезный недостаток, а именно, величина потока увеличивается на каждом шаге только на единицу. На практике ее можно существенно ускорить. Найдя путь С на шаге 3, можно проверить, сколько единиц потока можно пропустить по этому пути. Другими словами, мы можем определить наибольшее целое такое, при котором является допустимым потоком. Чтобы определить заметим, что для каждой дуги такой, что можно добавить не более единиц потока, не нарушая допустимости. Аналогично, если из с можно исключить не более единиц потока.

Целое число соответствует минимуму по таким приращениям потока в дугах С, и на шаге 3 алгоритма можно определять не

Упражнение 7.8. (см. скан)