403
правки
Изменения
→Корректность алгоритма
Для начала покажем, что после выполнения операции <tex> initialazePreflow </tex> <tex> h </tex> является функцией высоты. Для всех ребер, не инцидентных <tex> s </tex>, высота обоих концов равна нулю, что удовлетворяет условиям. Единственными ребрами <tex> (u, v) </tex>, для которых не выполняются условия, налагаемые на функцию высоты, то есть для которых <tex> h(u) > h(v) + 1 </tex>, являются ребра, у которых <tex> u = s </tex>. Но после операции <tex> initialazePreflow </tex> ребра являются насыщенными и не принадлежат остаточной сети.
Это будет базой нашей индукции.
Теперь докажем переход: если перед выполнением операции проталкивания или подъема <tex> h </tex> является функцией высоты, то и после выполнения операции она останется функцией высоты. Для этого рассмотрим проталкивание и подъем отдельно.
Покажем, что после окончания операции проталкивания утверждение верно. После выполнения операции <tex> push(u, v) </tex> в <tex> E_f </tex> может появиться ребро <tex> (v, u) </tex>, если до операции по ребру <tex> (u, v) </tex> протекал нулевой поток, или же ребро <tex> (u, v) </tex> может насытиться, и тогда оно перестанет принадлежать остаточной сети. В первом случае <tex> h(v) = h(u) - 1 < h(u) + 1 </tex>, и, следовательно, <tex> h </tex> остается функцией высоты. Во втором же случае при удалении ребра <tex> (u, v) </tex> из остаточной сети происходит лишь удаление соответствующих ограничений на высоты <tex> u </tex> и <tex> v </tex>, так что <tex> h </tex> остается функцией высоты.
}}
