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

Материал из Викиконспекты
Перейти к: навигация, поиск
НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.



Определение:
[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=83352»