53
правки
Изменения
Нет описания правки
{{Лемма
|statement=
Если в сети <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> не убывает после каждого увеличения потока.
|proof=
Предположим противное, пусть существует вершина <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>v</tex> и из предыдущего утверждения получаем, что <tex>\delta'_f (s, u) \ge \delta_f(s,u)</tex>.
|statement=Пусть для некоторой сети <tex>G(V,E)</tex> с источником <tex>s</tex> и стоком <tex>t</tex> выполняется алгоритм Эдмондса-Карпа, то общее число итераций цикла '''while''' составляет <tex>O(V E)</tex>.
|proof=
Рассмотрим множество ребер <tex>(u,v)</tex> остаточной сети <tex>G_f</tex>, принадлежащих увеличивающему пути <tex>p</tex>, таких что <tex>c_f(p) = c_f(u,v)</tex>. Назовем данные ребра критическими. Покажем, что каждое из <tex>|E|</tex> ребер может становиться критическим не более, чем <tex>|V| - 1</tex> раз. Заметим, что после увеличения потока вдоль пути <tex>p</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> исчезает из сети.
}}
