Остаточный путь в транспортном графе

Остаточный путь в транспортном графе

Остаточный путь в транспортной сети - путь в транспортной сети при данном потоке от истока до стока, для каждой соседней по пути пары вершин (u,v) которого c(u,v)-f(u,v) больше нуля. Используется в простом доказательстве Теоремы Форда-Фалкерсона. Если в транспортной сети при данном потоке существует остаточный путь, то поток не максимален.

Доказательство

Возьмём остаточный путь и найдём на нём ребро с минимальной разностью c(u,v)-f(u,v), а потом увеличим величину потока на всех рёбрах нашего пути на эту величину. Т.к. эта разность была минимальна, то после такой операции все величины потоков на рёбрах пути не будут превышать пропускной способности, а также поток увеличится, т.е. исходный поток не был максимален. На этом основан алгоритм нахождения максимального целочисленного потока в целочисленной транспортной сети.