Изменения

Если в сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> увеличение потока производиться вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>. То для всех вершин <tex>v \in V\backslash\{s,t\}</tex> длина кратчайшего пути <tex>\delta_f(s, v)</tex> в остаточной сети <tex>G_f</tex> не убывает после каждого увеличения потока.

Предположим противное, пусть существует вершина <tex>v \in V \backslash \{s,t\}</tex>, что после какого-то увеличения потока длина кратчайшего пути из <tex>s</tex> в <tex>v</tex> уменьшилась. Обозначим потоки до и после увеличения соответственно за <tex>f</tex> и <tex>f'</tex>. Пусть <tex>v</tex> {{---}} вершина, расстояние <tex>\delta'_f(s,v)</tex> от <tex>s</tex> до которой минимально</tex> и уменьшилось с увеличением потока. Имеем <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>. Рассмотрим путь <tex>p = s \leadsto u \rightarrow v</tex>, являющийся кратчайшим от <tex>s</tex> к <tex>v</tex> в <tex>G'_f</tex>. Тогда верно, что <tex>\delta'_f(s, u) = \delta'_f(s,v) - 1</tex>.

Пусть <tex>(u,v) \notin E_f</tex>, но известно, что <tex>(u,v) \in E_f'</tex>. Появление ребра <tex>(u,v)</tex> после увеличения потока означает увеличение потока по обратному ребру <tex>(v, u)</tex>. Увеличение потока производится вдоль кратчайшего пути, поэтому кратчайший путь из <tex>s</tex> в <tex>u</tex> вдоль которого происходило увеличения выглядит как <tex>s \leadsto v \rightarrow vu</tex>, из чего получаем <tex>\delta_f(s, v) = \delta_f(s, u) - 1 \le \delta'_f(s, u) - 1 = \delta'(s, v) - 2</tex>. Данное утверждение противоречит <tex>\delta'_f(s,v) < \delta_f(s,v)</tex>. Итак мы пришли к противоречию с существованием вершины <tex>v</tex>, кратчайшее расстояние до которой уменьшилось с увеличением потока.

Рассмотрим две вершины <tex>u</tex> и <tex>v</tex> принадлежащие <tex>V</tex>, соединенные некоторым ребром из <tex>E</tex>. Увеличение производиться вдоль кратчайших путей, поэтому если ребро <tex>(u,v)</tex> становиться критическим в первый раз, верно, что <tex>\delta_f(s,v) = \delta_f(s,u) + 1</tex>. После увеличения потока ребро <tex>(u, v)</tex> исчезает из сети. Оно не появится в другом увеличивающем пути до тех, пор пока не будет уменьшен по обратному ребру <tex>(v, u, v)</tex>. Это может произойти только в том случае, если ребро <tex>(v, u, v)</tex> встретится на некотором увеличивающем пути. Пусть в момент перед увеличением поток в сети <tex>G</tex> составлял <tex>f'</tex>, то поскольку увеличение проищводиться производиться вдоль кратчайших путей, верно: <tex>\delta'_f(s,u) = \delta'_f(s, v) + 1</tex>. Согласно [[#lemma1|лемме]] <tex>\delta_f(s,v) \le \delta'_f(s,v)</tex>, откуда <tex>\delta'_f(s,u) = \delta'(s,v) + 1 \ge \delta_f(s,v) + 1 = \delta_f(s,u) + 2</tex>.

Итак в промежутке промежуток времени между тем, когда ребро <tex>(u,v)</tex> становится критическим в первый раз, до момента, когда оно становится критическим в следующий раз, расстояние от <tex>s</tex> до <tex>u</tex> увеличивается минимум на <tex>2</tex>. Расстояние <tex>\delta(s,u)</tex> в начальный момент времени больше либо равно <tex>0</tex>. Среди промежуточных вершин на кратчайшем пути <tex>s \leadsto u</tex> не могут находиться <tex>s</tex>, <tex>u</tex> или <tex>t</tex>. Следовательно к тому моменту, когда вершина <tex>u</tex> станет недостижимой из источника расстояние до нее не превысит <tex>|V| - 2</tex>. Получаем, что ребро <tex>(u, v)</tex> могло стать критическим не более <tex>(|V| -2)/2 = |V|/2 - 1</tex> раз. Поскольку в графе не более <tex>O(E)</tex> пар вершин, между которыми могут существовать ребра в остаточной сети, то общее количество критических ребер в ходе выполнения алгоритма Эдмондса-Карпа равно <tex>O(V E)</tex>.

Поскольку Так как каждый увеличивающий путь, содержит по крайней мере одно критическое ребро, следовательно число кратчайших путей составляет <tex>O(V E)</tex>. На каждой итерации цикла '''while''' рассматривается ровно один увеличивающий путь, а так как только поскольку в случае отсутствия такого пути не существует выполнение цикла прерваетсяпрерывается, то число итераций цикла '''while''' также составляет <tex>O(V E)</tex>.