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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Поток через разрез)
(Поток через разрез)
Строка 24: Строка 24:
 
|definition=
 
|definition=
 
Поток в разрезе <tex><S,T></tex> обозначается <tex>f(S,T)</tex> и вычисляется по формуле: <tex>f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)</tex>.
 
Поток в разрезе <tex><S,T></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><S,T></tex> - разрез в <tex>G</tex>. Тогда <tex>f(S,T)=|f|</tex>.
 +
|proof =
 +
...
 +
}}
 +
 +
 +
{{Лемма
 +
|about =
 +
закон слабой двойственности потока и разреза
 +
|statement =
 +
Пусть <tex><S,T></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)=
 +
\sum\limits_{u\in S}\sum\limits_{v\in T}(c(u,v)-f(u,v))>0}</tex>, из-за органичений пропускных способностей (<tex>f(u,v)\le c(u,v)</tex>).
 +
 +
}}
 +
 +
 +
{{Лемма
 +
|statement =
 +
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> - максимален, а разрез <tex><S,T></tex> - минимален.
 +
|proof =
 +
...
 
}}
 
}}

Версия 15:27, 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]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]