Разрез, лемма о потоке через разрез — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 12: Строка 12:
  
 
3) <tex>S\cap T=\emptyset</tex>
 
3) <tex>S\cap T=\emptyset</tex>
 +
}}
 +
 +
== Поток через разрез ==
 +
 +
{{Определение
 +
|definition=
 +
Поток в разрезе <tex><S,T></tex> обозначается <tex>f(S,T)</tex> и вычисляется по формуле: <tex>\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)</tex>.
 
}}
 
}}

Версия 15:08, 19 декабря 2010

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

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

Определение:
[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]f(S,T)[/math] и вычисляется по формуле: [math]\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)[/math].