141
правка
Изменения
Нет описания правки
{{Определение
|definition=
<b><tex>(s,t)</tex>-разрезом</b> <tex><\langle S,T>\rangle</tex> в сети <tex>G</tex> называется пара множеств <tex>S,T</tex>, удоволетворяющих условиям:
1) <tex>s\in S, t\in T</tex>
{{Определение
|definition=
Пропускная способность разреза <tex><\langle S,T>\rangle</tex> обозначается <tex>c(S,T)</tex> и вычисляется по формуле: <tex>c(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}c(u,v)</tex>.
}}
{{Определение
|definition=
Поток в разрезе <tex><\langle S,T>\rangle</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><\langle S,T>\rangle</tex> - разрез в <tex>G</tex>. Тогда <tex>f(S,T)=|f|</tex>.
|proof =
<tex>f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(S\setminus s,V)+f(s,V)=f(s,V)=|f|</tex>
закон слабой двойственности потока и разреза
|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>).
Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения.
[[Файл:flows_and_cuts.png|thumb|right|Потоки и разрезы]] Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>.
}}
