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

Материал из Викиконспекты
Перейти к: навигация, поиск
(не показано 29 промежуточных версий 3 участников)
Строка 1: Строка 1:
−
== Определение разреза ==
 
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
<b><tex>(s,t)</tex>-разрезом</b> <tex>\langle S,T\rangle</tex> в сети <tex>G</tex> называется пара множеств <tex>S,T</tex>, удоволетворяющих условиям:
+
<b><tex>(s,t)</tex>-разрезом</b> (англ. ''s-t cut'') <tex>\langle S,T\rangle</tex> в сети <tex>G</tex> называется пара множеств <tex>S,T</tex>, удоволетворяющих условиям:
  
−
1) <tex>s\in S, t\in T</tex>
+
# <tex>s\in S, t\in T</tex>
 +
# <tex>S = V\setminus T</tex>
 +
}}
  
−
2) <tex>S\cup T=V</tex>
+
{{Определение
−
 
+
|definition=
−
3) <tex>S\cap T=\varnothing</tex>
+
'''Пропускная способность разреза''' (англ. ''capacity of the cut'') <tex>\langle S,T\rangle</tex> обозначается <tex>c(S,T)</tex> и вычисляется по формуле: <tex>c(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}c(u,v)</tex>.
 
}}
 
}}
−
 
−
== Поток через разрез ==
 
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Пропускная способность разреза <tex>\langle S,T\rangle</tex> обозначается <tex>c(S,T)</tex> и вычисляется по формуле: <tex>c(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}c(u,v)</tex>.
+
'''Поток в разрезе''' (англ. ''flow in the cut'') <tex>\langle S,T\rangle</tex> обозначается <tex>f(S,T)</tex> и вычисляется по формуле: <tex>f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)</tex>.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
Поток в разрезе <tex>\langle S,T\rangle</tex> обозначается <tex>f(S,T)</tex> и вычисляется по формуле: <tex>f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)</tex>.
+
'''Минимальным разрезом''' (англ. ''minimum cut'') называется разрез с минимально возможной пропускной способностью
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
 +
|about =
 +
о величине потока
 
|statement =
 
|statement =
−
Пусть <tex>\langle S,T\rangle</tex> - разрез в <tex>G</tex>. Тогда <tex>f(S,T)=|f|</tex>.
+
Пусть <tex>\langle S,T\rangle</tex> — разрез в <tex>G</tex>. Тогда <tex>f(S,T)=|f|</tex>.
 
|proof =
 
|proof =
 
<tex>f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(S\setminus s,V)+f(s,V)=f(s,V)=|f|</tex>
 
<tex>f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(S\setminus s,V)+f(s,V)=f(s,V)=|f|</tex>
  
−
1-е равенство выполняется, так как суммы не пересекаются (<tex>f(S,V)=f(S,S)+f(S,T)</tex>);
+
*1-е равенство выполняется, так как суммы не пересекаются: <tex>f(S,V)=f(S,S)+f(S,T)</tex>
  
−
2-е равенство выполняется из-за антисимметричности (<tex>f(S,S)=-f(S,S)=0</tex>);
+
*2-е равенство выполняется из-за антисимметричности: <tex>f(S,S)=-f(S,S)=0</tex>
  
−
3-е равенство выполняется, как и 1-е, из-за непересекающихся сумм;
+
*3-е равенство выполняется, как и 1-е, из-за непересекающихся сумм
  
−
4-е равенство выполняется из-за сохранения потока.
+
*4-е равенство выполняется из-за сохранения потока
 
}}
 
}}
  
Строка 44: Строка 45:
 
закон слабой двойственности потока и разреза
 
закон слабой двойственности потока и разреза
 
|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)\leqslant 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)=
−
\sum\limits_{u\in S}\sum\limits_{v\in T}(c(u,v)-f(u,v))\ge 0}</tex>, из-за ограничений пропускных способностей (<tex>f(u,v)\le c(u,v)</tex>).
+
\sum\limits_{u\in S}\sum\limits_{v\in T}(c(u,v)-f(u,v))\geqslant 0}</tex>, из-за ограничений пропускных способностей <tex>f(u,v) </tex> <tex>\leqslant c(u,v)</tex>.
 
}}
 
}}
  
  
 
{{Лемма
 
{{Лемма
 +
|about =
 +
о максимальном потоке и минимальном разрезе
 
|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>).
+
[[Файл:Минимальный_разрез.png|мини|справа|300x100px|Потоки и разрезы]]
 +
Из закона слабой двойственности следует, что <tex>f(S_1,T_1)\leqslant 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)\leqslant c(S_2,T_2)</tex>.
 
Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения.
 
Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения.
−
[[Файл:flows_and_cuts.png|thumb|right|Потоки и разрезы]] Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>.
+
Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>.}}
−
}}
+
 
 +
 +
[[Файл:разрезы.png|мини|слева|800x600px|Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети.]]
 +
 
 +
<br clear="all">
 +
 
 +
{|border="1" class="wikitable" style="width: 400px; height: 150px; float: слева;"
 +
|+ style="caption-side:bottom; "|''Минимальный разрез — 1 с пропускной способностью 60''
 +
 
 +
|-
 +
| '''Разрез'''|| '''"Разрезанные" ребра'''|| '''Пропускная способность'''
 +
|-
 +
 
 +
|1
 +
| (1,2),(1,3),(1,4)
 +
| 10+30+20=60
 +
 
 +
|-
 +
| 2
 +
|(1,3),(1,4),(2,3),(2,5)
 +
|30+10+40+30=110
 +
 
 +
|-
 +
|3
 +
|(2,5),(3,5),(4,5)
 +
| 30+20+20=70
 +
 
 +
|}
  
−
== Литература ==
+
== Источники информации ==
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 +
* [http://ru.wikipedia.org/wiki/Разрез_графа Википедия: Разрез графа]
 +
* [http://en.wikipedia.org/wiki/Cut_(graph_theory) Википедия: Разрез графа (англ.)]
  
−
[[Категории:Алгоритмы и структуры данных]]
+
[[Категория:Алгоритмы и структуры данных]]
−
[[Категории:Задача о максимальном потоке]]
+
[[Категория:Задача о максимальном потоке]]

Версия 18:02, 16 декабря 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 = V\setminus T[/math]


Определение:
Пропускная способность разреза (англ. capacity of the cut) [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].


Определение:
Поток в разрезе (англ. flow in the cut) [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].


Определение:
Минимальным разрезом (англ. minimum cut) называется разрез с минимально возможной пропускной способностью


Лемма (о величине потока):
Пусть [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)\leqslant 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))\geqslant 0}[/math], из-за ограничений пропускных способностей [math]f(u,v) [/math] [math]\leqslant 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)\leqslant 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)\leqslant c(S_2,T_2)[/math]. Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения.

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


Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети.


Минимальный разрез — 1 с пропускной способностью 60
Разрез "Разрезанные" ребра Пропускная способность
1 (1,2),(1,3),(1,4) 10+30+20=60
2 (1,3),(1,4),(2,3),(2,5) 30+10+40+30=110
3 (2,5),(3,5),(4,5) 30+20+20=70

Источники информации

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