403
правки
Изменения
→Оценка быстродействия
== Оценка быстродействия ==
Чтобы показать, что алгоритм завершает свою работу, найдем максимальное количество операций проталкивания и подъема. Для того докажем несколько вспомогательных лемм.
{{Лемма
|about = 4
|id = Лемма4
|statement =
Пусть <tex> G </tex> {{---}} сеть со стоком <tex> s </tex> и истоком <tex> t </tex>, и <tex> f </tex> {{---}} предпоток в <tex> G </tex>. Тогда из любой переполненной вершины <tex> u </tex> существует путь в <tex> s </tex> в остаточной сети <tex> G_f </tex>.
|proof =
Докажем лемму методом от противного.
Пусть для вершины <tex> u </tex> верно, что <tex> e(u) > 0 </tex>. Пусть также <tex> U = \{v: u \leadsto v </tex> в <tex> G_f \} </tex> и <tex> \bar{U} = V \setminus U </tex>. Предположим, что <tex> s \in \bar{U} </tex>.
Покажем, что для любой пары вершин <tex> v \in U </tex> и <tex> w \in \bar{U} </tex> верно, что <tex> f(w, v) \leqslant 0 </tex>. Если <tex> f(w, v) > 0 </tex>, то <tex> f(v, w) < 0 </tex>. Но тогда из этого утверждения следует, что <tex> c_f(v, w) = c(v, w) - f(v, w) > 0 </tex>, что не может быть верным, так как в таком случае существует путь <tex> u \leadsto v \to w </tex> в остаточной сети <tex> G_f </tex>, что противоречит выбору вершины <tex> w </tex>. Следовательно, для каждой пары вершин <tex> v \in U </tex> и <tex> w \in \bar{U} </tex> верно, что <tex> f(w, v) \leqslant 0 </tex>. Тогда верно и <tex> f(\bar{U}, U) \leqslant 0 </tex>. Следовательно <tex> e(U) = f(V, U) = f(U, U) + f(\bar{U}, U) = f(\bar{U}, U) \leqslant 0 </tex>.
Но по определению избыток потока неотрицателен, из чего следует, что для любой вершины <tex> v \in U </tex> <tex> e(v) = 0 </tex>, в том числе <tex> e(u) = 0 </tex>, что противоречит условию переполненности вершины <tex> u </tex>.
}}
== Источники ==
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке]]
