403
правки
Изменения
→Корректность алгоритма
== Корректность алгоритма ==
Для доказательства корректности алгоритма докажем несколько вспомогательных лемм.
{{Лемма
|about = 1
|id = Лемма1
|statement =
Во время выполнения алгоритма <tex> pushRelabelMaxFlow </tex> никакие свойства высоты не нарушаются.
|proof =
Доказательство проведем по числу выполненных операций проталкивания и подъема.
Для начала покажем, что после выполнения операции <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> ребра являются насыщенными и не принадлежат остаточной сети.
}}
== Оценка быстродействия ==
== Источники ==
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
