Изменения
→Оценка быстродействия: перепутали сток и исток
|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 =
Докажем лемму методом от противного.
