2.5.4. Динамический поток

Задачи о поиске максимального динамического потока в сети возникают в тех случаях, когда для каждой дуги сети (i,j)определено время передачи единицы потока изiвjt_ij, а также пропускная способностьC_ij– количество единиц потока, которые могут передаваться по данной дуге одновременно.

Пример 1. Туристическое агентство обеспечивает доставку клиентов из Москвы в Лас-Пальмас, используя как прямые авиарейсы, так и транзитные. Известно расписание регулярных рейсов крупнейших авиакомпаний. Какое максимальное количество туристов может быть доставлено в пункт назначения в течение недели?

Рассмотрим один из наиболее простых случаев задачи о динамическом потоке. Все исходные данные по-прежнему предполагаются целочисленными, время tтакже является дискретным, времяt_ijпередачи единицы потока по дуге(i,j) не зависит от момента начала передачи и является постоянным. Таким образом, если пропускная способность дуги равнаC_ij,то в каждый из моментов времениt=0,1,2,…по ней можно отправлятьC_ijединиц потока изiвj , которые будут прибывать вjв моментыt_ij,1+ t_ij, 2+ t_ij,….

В этом случае задача вполне аналогична рассмотренной ранее задаче о поиске потока минимальной стоимости при неотрицательных стоимостях передачи потока по дугам. В самом деле, минимальное возможное время передачи потока из sвtравно нулю. За нулевое время поток может быть передан изsвt, если есть увеличивающая цепь, состоящая из дуг, для которых времяt_ij. Для всех узлов, для которых таких цепей нет, следует увеличить на единицу временные метки, аналогичные стоимостным меткам в предыдущем алгоритме, затем попытаться найти поток за новое время , и так далее. Следовательно, с помощью алгоритма Форда и Фалкерсона можно решить и задачу о поиске максимального динамического потока. Для этого в алгоритме стоимостиa_ijдолжны быть заменены временемt_ij. Меткиp(i)будут означать максимальное время передачи единицы потока в узелi. Иначе будет выглядеть и конечный результат работы алгоритма.

Рис. 2.23

Пример 2. Для графа на рис. 2.23 (первое число на дуге – время, второе – пропускная способность) найти максимальный динамический поток из узла s=1в узелt=4за времяT=0,1,2, … .

В первой таблице приведены результаты работы алгоритма. Первая увеличивающая цепь появляется на четвертой итерации, когда p(4)=4. Это означает, что за время, меньшее четырех единиц, ни одна единица потока не может быть передана из1в4, за время4может быть передана одна единица потока по пути1,2,3,4,для этого ее надо отправить из начальной вершины 1 в момент времениt=0.

Далее, при p(4)=5появляется еще одна увеличивающая цепь1,3,4, по ней может быть передано 2 единицы потока, время передачи по этой цепи 3+2=5. При этом по пути1,2,3,4одна единица потока может быть отправлена в моментt=0и в моментt=1, потому что время передачи по этому пути равно 1+1+2=4. Таким образом, суммарная величина потока, который может быть передан по сети за времяT=5, равна 1+1+2=4 единицам. Дальнейшие результаты приведены во второй таблице.

Максимальный поток в сети получается при p(4)=9, насыщенный разрез определяется множеством вершинX={1,3}

На десятой итерации алгоритма при p(1)=7увеличивающая цепь содержит обратную дугу. По такой цепи поток передаваться, конечно, не может, а увеличение потока в сети вдоль нее означает, что какое-то количество единиц потока, ранее передававшихся по возвратной дуге, теперь будут передаваться по какой-то другой дуге. Поэтому при записи решения во второй таблице приT=7и далеее приводятся пути, по которым реально происходит передача потока, в данном случае –1,3,4(3 единицы) и1,2,4(4 единицы).