403
правки
Изменения
→Корректность алгоритма
Предположим, что в <tex> G_f </tex> существует путь из <tex> s </tex> в <tex> t </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>. Раз <tex> p </tex> простой, то <tex> k < \left\vert V \right\vert </tex>. Поскольку <tex> h </tex> {{---}} функций высоты, то <tex> \forall i \in \{0, 1, \dots, k - 1 \} </tex> справедливо <tex> h(v_i) \leqslant h(v_{i+1}) + 1 </tex>. Следовательно, <tex> h(s) \leqslant h(t) + k </tex>. А так как по определению функции высоты <tex> h(t) = 0 </tex>, то <tex> h(s) \leqslant k < \left\vert V \right\vert </tex>, что противоречит условию функции высоты, что <tex> h(s) = \left\vert V \right\vert </tex>.
}}
{{Теорема
|statement =
Если алгоритм <tex> pushRelabelMaxFlow </tex> завершается, то вычисленный им предпоток <tex> f </tex> является максимальным потоком.
|proof =
Для доказательства покажем, что перед каждой проверкой условия в цикле while <tex> f </tex> является предпотоком.
Перед началом цикла, после завершения операции <tex> initializePreflow </tex>, <tex> f </tex> является предпотоком.
Внутри цикла выполняются лишь операции проталкивания и подъема. Операция подъема не влияет на величины потока, а лишь изменяет высоту вершины, следовательно от операции подъема не зависит, будет ли <tex> f </tex> предпотоком. Операция <tex> push(u, v) </tex> применяется, если <tex> e(u) > 0 </tex>, увеличивая поток через ребро <tex> (u, v) </tex> на величину, не превышающую избыточный поток вершины <tex> u </tex> и остаточную пропускную способность ребра <tex> (u, v) </tex>. Следовательно, если перед выполнением операции проталкивания <tex> f </tex> являлся предпотоком, то и после выполнения проталкивания <tex> f </tex> останется предпотоком.
}}
