Изменения

Перейти к: навигация, поиск
Нет описания правки
{{Лемма
|about=
о представлении потоков
|statement=
Пусть <tex> f </tex> и <tex> g </tex> - потоки в сети <tex> G </tex>. Тогда <tex> g </tex> можно представить как сумму <tex> f + f'</tex>, где <tex>f'</tex> {{---}} поток в остаточной сети <tex>G_f</tex>.
|proof=
Рассмотрим произвольное ребро<tex> (u, v) </tex> из <tex> f' = g - f </tex>. Если <tex> g(u, v) \geq f(u, v) </tex>, то <tex> f'(u, v) = g(u, v) - f(u, v) \leq c(u, v) - f(u, v) = C_f(u, v) </tex>. Если <tex> g(u, v) \le f(u, v) </tex>, то <tex> g(v, u) - f(v, u) = f(u, v) - g(u, v) \leq f(u, v) = C_f(v, u). </tex>. Таким образом поток через каждое ребро не превосходит пропускной способности остаточной сети.
Антисимметричность и закон сохранения потока проверяются аналогично [[Лемма о сложении потоков|лемме о сложении потоков]].
}}
 
{{Теорема
|statement=
Анонимный участник

Навигация