693
правки
Изменения
Нет описания правки
|id = Лемма9
|statement =
Количество ненасыщающих проталкиваний при выполнение алгоритма <tex> \mathrm{pushRealbelMaxFlowpushRelabelMaxFlow}</tex> не превосходит <tex> 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) </tex>
|proof =
Пусть <tex> \Phi = \sum \limits_{u: e(u) > 0} h(u)</tex>. Так как после завершения алгоритма ни одна из вершин не является переполненной, то и величина <tex> \Phi </tex> после выполнения алгоритма должна равняться нулю.
{{Теорема
|statement =
Пусть <tex> G </tex> {{---}} сеть. Тогда любая реализация метода <tex> \mathrm{pushRealbelMaxFlowpushRelabelMaxFlow}</tex> для <tex> G </tex> завершает свою работу, и число основных операций составляет <tex> O(V^2E) </tex>
|proof =
Из [[#Лемма6|леммы <tex>6</tex>]], [[#Лемма8|леммы <tex>8</tex>]] и [[#Лемма9|леммы <tex>9</tex>]] следует, что число операций подъёма и проталкиваний не превышает <tex> 2 \cdot \left\vert V \right\vert ^2 + 2 \cdot \left\vert V \right\vert \cdot \left\vert E \right\vert + 4 \cdot \left\vert V \right\vert ^2 (\left\vert V \right\vert + \left\vert E \right\vert) = O(V^2E) </tex>. А так как количество операций ограничено, то независимо от реализации алгоритм завершит свою работу.
