403
правки
Изменения
→Корректность алгоритма
|proof =
Рассмотрим вершину <tex> u </tex>, для которой <tex> e(u) > 0 </tex>. Для любого ребра <tex> (u, v) \in E_f </tex> справедливо <tex> h(u) \leqslant h(v) + 1 </tex> по свойствам функции высоты. Если к вершине <tex> u </tex> применима операция проталкивания, то лемма доказана. Иначе, для всех ребер <tex> (u, v) \in E_f </tex> выполняется соотношение <tex> h(u) < h(v) + 1 </tex>. Следовательно, <tex> h(u) \leqslant h(v) </tex>. Но тогда данная вершина удовлетворяет условиям операции подъема, следовательно, к вершине <tex> u </tex> можно применить эту операцию.
}}
{{Лемма
|about = 3
|id = Лемма 3
|statement =
Пусть <tex> G </tex> {{---}} сеть с истоком <tex> s </tex> и стоком <tex> t </tex>. <tex> f </tex> и <tex> h </tex> {{---}} предпоток и функция высоты соответственно. Тогда в остаточной сети <tex> G_f </tex> нет пути из <tex> s </tex> в <tex> t </tex>.
|proof =
Докажем от противного.
Предположим, что в <tex> G_f </tex> существует путь <tex> p = \left \langle v_0, v_1, \dots, v_k \right \rangle </tex>, где <tex> v_0 = s </tex> и <tex> v_k = t </tex>.
}}
