141
правка
Изменения
→Поток через разрез
|definition=
Поток в разрезе <tex><S,T></tex> обозначается <tex>f(S,T)</tex> и вычисляется по формуле: <tex>f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)</tex>.
}}
{{Лемма
|statement =
Пусть <tex><S,T></tex> - разрез в <tex>G</tex>. Тогда <tex>f(S,T)=|f|</tex>.
|proof =
...
}}
{{Лемма
|about =
закон слабой двойственности потока и разреза
|statement =
Пусть <tex><S,T></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)=
\sum\limits_{u\in S}\sum\limits_{v\in T}(c(u,v)-f(u,v))>0}</tex>, из-за органичений пропускных способностей (<tex>f(u,v)\le c(u,v)</tex>).
}}
{{Лемма
|statement =
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> - максимален, а разрез <tex><S,T></tex> - минимален.
|proof =
...
}}
