Изменения

Перейти к: навигация, поиск
Нет описания правки
о представлении потоков
|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> f'(v, u) = g(v, u) - f(v, u) = f(u, v) - g(u, v) \leq f(u, v) = C_f(v, u) </tex>. Таким образом поток через каждое ребро не превосходит пропускной способности остаточной сети.
Анонимный участник

Навигация