Изменения

Если в транспортной сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> увеличение потока производиться вдоль кратчайших <tex>s \leadsto t</tex> путей в <tex>G_f</tex>. То для всех вершин <tex>v \in V[G]\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>fv</tex> {{---}} вершина, расстояние <tex>\delta'_f(s,v) от <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>v<Предположим/tex> и из предыдущего утверждения получаем, что для некоторой вершины <tex>\delta'_f (s, u) \ge \delta_f(s,u)</tex>. Предположим <tex>(u, v ) \in V[G] E_f</tex>, тогда <tex>\delta_f(s,v) \le \delta_f(s, u) + 1 \le \delta'_f(s,u) + 1 = \delta'_f(s, v)</tex>. Это противоречит <tex>\delta'_f(s,v) < \backslash {delta_f(s,t}v)</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 v</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>, кратчайшее расстояние до которой уменьшилось с увеличением потока.}} Опираясь на предшествующую лемму докажем следующую теорему, которая ограничивает сверху число итераций цикла '''while''' в алгоритме Эдмондса-Карпа. {{Теорема|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, то общее число итераций цикла '''while''' составляет <tex>O(V E)</tex>. |proof=