Изменения

Перейти к: навигация, поиск

Метод проталкивания предпотока

2 байта убрано, 08:27, 25 сентября 2015
Оценка быстродействия
|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 =
Докажем лемму методом от противного.
Анонимный участник

Навигация