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

Question

Мне сложно понять следующую лемму из CLRS:

Пусть G - сеть потоков, s и t - узлы источника и приемника, f - предварительный поток из s в t, а h - функция высоты на G. Тогда в остаточном графе G_f нет пути увеличения от s до t.,

Почему это?

Answer 1

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

Интуиция за доказательством состоит в том, что если 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.

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