Изменения
Нет описания правки
{{Определение
|definition=
<b><tex>(s,t)</tex>-разрезом</b> (англ. ''s-t cut'') <tex><\langle S,T>\rangle</tex> в сети <tex>G</tex> называется пара множеств <tex>S,T</tex>, удоволетворяющих условиям:
}}
{{Определение
|definition=
}}
{{Определение
|definition=
}}
{{Лемма
|about =
о величине потока
|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>
*1-е равенство выполняется, так как суммы не пересекаются (: <tex>f(S,V)=f(S,S)+f(S,T)</tex>);
*2-е равенство выполняется из-за антисимметричности (: <tex>f(S,S)=-f(S,S)=0</tex>);
*3-е равенство выполняется, как и 1-е, из-за непересекающихся сумм;
*4-е равенство выполняется из-за сохранения потока.
}}
закон слабой двойственности потока и разреза
|statement =
Пусть <tex><\langle S,T>\rangle</tex> - — разрез в <tex>G</tex>. Тогда <tex>f(S,T)\le leqslant 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))\ge geqslant 0}</tex>, из-за органичений ограничений пропускных способностей (<tex>f(u,v)</tex> <tex>\le leqslant c(u,v)</tex>).
}}
{{Лемма
|about =
о максимальном потоке и минимальном разрезе
|statement =
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> - — максимален, а разрез <tex><\langle S,T>\rangle</tex> - — минимален.
|proof =