Эта статья находится в разработке!
Определение разреза
| Определение: |
| [math](s,t)[/math]-разрезом [math]\lt S,T\gt [/math] в сети [math]G[/math] называется пара множеств [math]S,T[/math], удоволетворяющих условиям:
1) [math]s\in S, t\in T[/math]
2) [math]S\cup T=V[/math]
3) [math]S\cap T=\emptyset[/math] |
Поток через разрез
| Определение: |
| Пропускная способность разреза [math]\lt S,T\gt [/math] обозначается [math]c(S,T)[/math] и вычисляется по формуле: [math]c(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}c(u,v)[/math]. |
| Определение: |
| Поток в разрезе [math]\lt S,T\gt [/math] обозначается [math]f(S,T)[/math] и вычисляется по формуле: [math]f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)[/math]. |
| Лемма: |
Пусть [math]\lt S,T\gt [/math] - разрез в [math]G[/math]. Тогда [math]f(S,T)=|f|[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
... |
| [math]\triangleleft[/math] |
| Лемма (закон слабой двойственности потока и разреза): |
Пусть [math]\lt S,T\gt [/math] - разрез в [math]G[/math]. Тогда [math]f(S,T)\le c(S,T)[/math]. |
| Доказательство: |
| [math]\triangleright[/math] |
|
[math]{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))\gt 0}[/math], из-за органичений пропускных способностей ([math]f(u,v)\le c(u,v)[/math]). |
| [math]\triangleleft[/math] |
| Лемма: |
Если [math]f(S,T)=c(S,T)[/math], то поток [math]f[/math] - максимален, а разрез [math]\lt S,T\gt [/math] - минимален. |
| Доказательство: |
| [math]\triangleright[/math] |
|
... |
| [math]\triangleleft[/math] |
