мне трудно понять следующую лемму из КСПСА:В алгоритмах Push Relabel для максимального потока, почему нет пути от источника s, чтобы потопить t?
Пусть G- сеть потока, s и т быть источник и приемник узлами, Р- предварительной подачи от с до т, а ч функция высоты на G. Тогда нет пути увеличения от s до t в остаточном графе G f.
Почему это?
Следующая парафразованная и расширенная версия доказательства в 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.
Надеюсь, это поможет!