Рис. 18

Перейдем к новой сети, отличающейся от заданной только тем, что пропускные способности всех дуг пути

Aq -* А{ -* Ал. -> А5 уменьшены на 6 (рис. 18а).

Рис. 18а

2-й шаг. Обратившись к рисунку 18а, выберем путь Aq-*А{->А2-*> Ал -> А5.

Наименьшую пропускную способность на этом пути имеет дуга AqA\ -1 (поток величины 7, построенный по результатам двух сделанных шагов, показан на рис. 19).

Уменьшая пропускную способность каждой дуги выбранного на этом шаге пути на 1, переходим к новой сети (рис. 19а).

Рис. 19а

3-й шаг. Обратившись к рисунку 19а, выбираем путь А, -> А2 -> А3 -> А5,

наименьшую пропускную способность которого - 2 - определяет дуга А2А3 (на рис. 20 показан поток величины 9, построенный по результатам трех сделанных шагов).

Переходим к новой сети (рис. 20а).

4-й шаг. Обратившись к рисунку 20а, выберем путь

А0А2ААА5.

Наименьшая пропускная способность - 1 - определяется дугой А2Аа. (на рис. 21 показан поток величины 10, построенный по результатам четырех сделанных шагов).