6.4. Пример

Мы хотим найти оптимально-максимальный поток от вершины к вершине в графе на рис. 11.18, где первое число у дуги

Рис. 11.18. Граф из примера 6.4. Первая пометка — пропускная способность дуги, вторая — выигрыш дуги.

(кликните для просмотра скана)

Рис. 11.19. г. Оптимальный поток. — насыщенные дуги.

является ее пропускной способностью, а второе — ее выигрышем.

Начиная с находим первый активный цикл с аугментальным маршрутом Циркуляция потока входной поток дуги по этому маршруту, как показано на рис. 11.18, дает максимальный допустимый поток со значением и для этого значения получающийся поток показан (подчеркнутыми числами) на рис. 11.19а, причем дуга насыщена. Пропускная способность самого цикла не уменьшается до нуля, и поэтому при следующей итерации, когда алгоритм кратчайшей цепи (действующий от всех других вершин графа к вершине помечает вершину из цикл снова становится активным с новой аугментальной цепью Посылая поток по циклу и передавая его по аугментальной цепи к как показано на рис. 11.19а, получаем поток, изображенный на рис. 11.196 подчеркнутыми числами.

Рис. 11.19д. Оптимально-максимальный поток. — насыщенные дуги.

Новый активный цикл определяется на шаге 2, и циркуляция потока по этому циклу, как показано на рис. 11.19(6), дает поток, изображенный подчеркнутыми числами на рис. 11.19(b). Наконец, определяется активный цикл и его дезактивация с помощью циркуляции потока приводит к потоку, изображенному на рис. Последний будет оптимальным потоком, так как больше не удается обнаружить никаких активных циклов.

Аугментальный маршрут (от с максимальным выигрышем есть с пропускной способностью Как только этот маршрут будет насыщен (дуга уже насыщена), аугментальным маршрутом со следующим наибольшим выигрышем будет и он после насыщения даст поток на рис. 11.19д. Этот поток будет требуемым оптимально-максимальным потоком, так как больше нельзя найти никаких аугментальных цепей (от ).