Что такое увеличивающий путь?

Говоря о computing network flows, в Руководстве по проектированию алгоритмов говорится:

Традиционные алгоритмы сетевых потоков основаны на идее увеличения путей и повторного нахождения пути с положительной пропускной способностью от s к t и добавления его к поток. Можно показать, что поток через сеть оптимален тогда и только тогда, когда он не содержит увеличивающих путей.

Я не понимаю, что такое augmenting paths. Я погуглил и нашел:

, но все они ссылаются на приведенную выше цитату.

Кто-нибудь может объяснить, что такое augmenting path?

38
задан nbro 25 January 2017 в 12:37
поделиться