Почему в алгоритмах Push Relabel для максимального потока нет пути от источника s к приемнику t?

Ниже приводится перефразированная и расширенная версия доказательства в CLRS, Second Edition.

Интуиция, лежащая в основе доказательства, заключается в том, что если h — функция высоты, то мы должны иметь, что на любом пути от s до t высота узлов вдоль пути может уменьшаться не более чем на единицу на каждом шаге (поскольку функции высоты удовлетворяют свойство h(u) h(v) + 1, означающее, что h(v) h(u) - 1). Итак, теперь предположим, что у вас есть увеличивающий путь в остаточном графе, который идет от s к t. В этом случае, если есть увеличивающий путь, должен быть и увеличивающий простой путь из s в t, так что нам не нужно беспокоиться о циклах.

Итак, давайте подумаем, как должен выглядеть этот простой путь. Если есть |V| вершин в графе, наш простой путь должен иметь не более |V| вершин в нем, а значит, он имеет не более чем |V| - 1 ребра в нем. Поскольку существует не более |V| - 1 ребер, и высота каждого узла может уменьшаться не более чем на единицу за шаг, максимально возможное уменьшение высоты от начального узла s равно |V| - 1. Теперь мы знаем, что h является функцией высоты, а это означает, что h(s) = |V| и h(t) = 0. Но теперь у нас есть противоречие - так как мы начинаем с высоты |V| и уменьшить высоту не более чем на |V| - 1, высота в конце пути должна быть не меньше 1, а поскольку h(t) = 0, мы знаем, что этот путь не может закончиться в точке t. Это противоречие гарантирует, что наше предположение было неверным и действительно не существует увеличивающего пути от s к t.

Надеюсь это поможет!