В алгоритмах Push Relabel для максимального потока, почему нет пути от источника s к стоку t? - PullRequest
1 голос
/ 04 февраля 2012

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

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

Почему это так?

1 Ответ

2 голосов
/ 13 февраля 2012

Ниже приводится перефразированная и расширенная версия доказательства в 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.

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

...