Изменения

Алгоритм Форда — -Фалкерсона — алгоритм, решающий задачу нахождения максимального потока в транспортной сети.

Заметим, что после шага 1, как и после шага 5, остаточные способности рёбер <mathtex>e_1</mathtex>, <mathtex>e_2</mathtex> и <mathtex>e_3</mathtex> имеют форму <mathtex>r^n</mathtex>, <mathtex>r^{n+1}</mathtex> and и <mathtex>0</mathtex>, соответственно, для какого-то натурального <mathtex>n</mathtex>. Это значит, что мы можем использовать увеличивающие пути <mathtex>p_1</mathtex>, <mathtex>p_2</mathtex>, <mathtex>p_1</mathtex> и <mathtex>p_3</mathtex> бесконечно много раз, и остаточные пропускные способности этих рёбер всегда будут в той же форме.Полный поток после шага 5 равен <mathtex>1 + 2(r^1 + r^2)</mathtex>. За бесконечное время полный поток сойдётся к <mathtex>\textstyle 1 + 2\sum_{i=1}^\infty r^i = 3 + 2r</mathtex>, тогда как максимальный поток равен <mathtex>2M + 1</mathtex>. Таким образом, алгоритм не только работает бесконечно долго, но даже и не сходится к оптимальному решению.