Изменения
→Поток через разрез
закон слабой двойственности потока и разреза
|statement =
Пусть <tex>\langle S,T\rangle</tex> - — разрез в <tex>G</tex>. Тогда <tex>f(S,T)\le c(S,T)</tex>.
|proof =
<tex>{c(S,T)-f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}c(u,v)-\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)=
{{Лемма
|statement =
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> - — максимален, а разрез <tex>\langle S,T\rangle</tex> - — минимален.
|proof =
Из закона слабой двойственности следует, что <tex>f(S_1,T_1)\le c(S_2,T_2)</tex> для любых двух разрезов <tex>\langle S_1,T_1\rangle</tex> и <tex>\langle S_2,T_2\rangle</tex> в сети <tex>G</tex> (так как <tex>f(S_1,T_1)=|f|=f(S_2,T_2)\le c(S_2,T_2)</tex>).
