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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Поток через разрез)
(→‎Поток через разрез)
Строка 49: Строка 49:
 
закон слабой двойственности потока и разреза
 
закон слабой двойственности потока и разреза
 
|statement =
 
|statement =
−
Пусть <tex>\langle S,T\rangle</tex> - разрез в <tex>G</tex>. Тогда <tex>f(S,T)\le c(S,T)</tex>.
+
Пусть <tex>\langle S,T\rangle</tex> — разрез в <tex>G</tex>. Тогда <tex>f(S,T)\le c(S,T)</tex>.
 
|proof =
 
|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)=
 
<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)=
Строка 58: Строка 58:
 
{{Лемма
 
{{Лемма
 
|statement =
 
|statement =
−
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> - максимален, а разрез <tex>\langle S,T\rangle</tex> - минимален.
+
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> — максимален, а разрез <tex>\langle S,T\rangle</tex> — минимален.
 
|proof =
 
|proof =
 
Из закона слабой двойственности следует, что <tex>f(S_1,T_1)\le c(S_2,T_2)</tex> для любых двух разрезов <tex>\langle S_1,T_1\rangle</tex> и <tex>\langle S_2,T_2\rangle</tex> в сети <tex>G</tex> (так как <tex>f(S_1,T_1)=|f|=f(S_2,T_2)\le c(S_2,T_2)</tex>).
 
Из закона слабой двойственности следует, что <tex>f(S_1,T_1)\le c(S_2,T_2)</tex> для любых двух разрезов <tex>\langle S_1,T_1\rangle</tex> и <tex>\langle S_2,T_2\rangle</tex> в сети <tex>G</tex> (так как <tex>f(S_1,T_1)=|f|=f(S_2,T_2)\le c(S_2,T_2)</tex>).

Версия 09:55, 4 декабря 2015

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

Определение:
[math](s,t)[/math]-разрезом (англ. s-t cut) [math]\langle S,T\rangle[/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=\varnothing[/math]


Поток через разрез

Определение:
Пропускная способность разреза [math]\langle S,T\rangle[/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]\langle S,T\rangle[/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]\langle S,T\rangle[/math] - разрез в [math]G[/math]. Тогда [math]f(S,T)=|f|[/math].
Доказательство:
[math]\triangleright[/math]

[math]f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(S\setminus s,V)+f(s,V)=f(s,V)=|f|[/math]

1-е равенство выполняется, так как суммы не пересекаются ([math]f(S,V)=f(S,S)+f(S,T)[/math]);

2-е равенство выполняется из-за антисимметричности ([math]f(S,S)=-f(S,S)=0[/math]);

3-е равенство выполняется, как и 1-е, из-за непересекающихся сумм;

4-е равенство выполняется из-за сохранения потока.
[math]\triangleleft[/math]


Лемма (закон слабой двойственности потока и разреза):
Пусть [math]\langle S,T\rangle[/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))\ge 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]\langle S,T\rangle[/math] — минимален.
Доказательство:
[math]\triangleright[/math]

Из закона слабой двойственности следует, что [math]f(S_1,T_1)\le c(S_2,T_2)[/math] для любых двух разрезов [math]\langle S_1,T_1\rangle[/math] и [math]\langle S_2,T_2\rangle[/math] в сети [math]G[/math] (так как [math]f(S_1,T_1)=|f|=f(S_2,T_2)\le c(S_2,T_2)[/math]). Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения.

Потоки и разрезы
Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети [math]G[/math].
[math]\triangleleft[/math]

Литература

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Разрез,_лемма_о_потоке_через_разрез&oldid=50115»