403
правки
Изменения
→Корректность алгоритма
Теперь рассмотрим операцию подъема вершины <tex> u </tex>. По определению данной операции гарантируется, что после ее выполнения для любого ребра <tex> (u, v) \in E_f </tex> выполняется условие <tex> h(u) \leqslant h(v) + 1 </tex>, то есть все выходящие ребра удовлетворяют условиям, накладываемым на функцию высоты. Рассмотрим какое-то входящее ребро <tex> (w, u) </tex>. Так как до операции <tex> h </tex> являлась функцией высоты, то справедливо <tex> h(w) \leqslant h(u) + 1 </tex>. После подъема высота вершины <tex> u </tex> увеличивается как минимум на единицу, следовательно, после выполнения данной операции <tex> h(w) < h(u) + 1 </tex>. Таким образом, <tex> h </tex> и после выполнения операции <tex> relabel(u) </tex> остается функций высоты.
}}
{{Лемма
|about = 2
|id = Лемма 2
|statement =
Для переполненной вершины можно выполнить операцию проталкивания либо операцию подъема.
|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> можно применить эту операцию.
}}
