Ниже приводится перефразированная и расширенная версия доказательства в CLRS, второе издание.
Интуиция, лежащая в основе доказательства, состоит в том, что если h - функция высоты, то мы должны иметь это на любом пути из st, высота узлов вдоль пути может уменьшаться не более чем на один шаг (поскольку функции высоты удовлетворяют свойству 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.
Надеюсь, это поможет!