Разрез, лемма о потоке через разрез

Эта статья находится в разработке!

Определение разреза

Определение:

[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].