Изменения

<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 = V\setminus T</tex>}}

2{{Определение|definition='''Пропускная способность разреза''' (англ. ''capacity of the cut'') <tex>\langle S,T\cup rangle</tex> обозначается <tex>c(S,T=V)</tex> 3) и вычисляется по формуле: <tex>c(S\cap ,T)=\emptysetsum\limits_{u\in S}\sum\limits_{v\in T}c(u,v)</tex>.

Пропускная способность разреза '''Поток в разрезе''' (англ. ''flow in the cut'') <tex><\langle S,T>\rangle</tex> обозначается <tex>cf(S,T)</tex> и вычисляется по формуле: <tex>cf(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}cf(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англ. ''minimum cut'')</tex>.называется разрез с минимально возможной пропускной способностью

Пусть <tex><\langle S,T>\rangle</tex> - — разрез в <tex>G</tex>. Тогда <tex>f(S,T)=|f|</tex>.

*1-е равенство выполняется, так как суммы не пересекаются (: <tex>f(S,V)=f(S,S)+f(S,T)</tex>);

*2-е равенство выполняется из-за антисимметричности (: <tex>f(S,S)=-f(S,S)=0</tex>);

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

*4-е равенство выполняется из-за сохранения потока.

Пусть <tex><\langle S,T>\rangle</tex> - — разрез в <tex>G</tex>. Тогда <tex>f(S,T)\le leqslant c(S,T)</tex>.

\sum\limits_{u\in S}\sum\limits_{v\in T}(c(u,v)-f(u,v))\ge geqslant 0}</tex>, из-за органичений ограничений пропускных способностей (<tex>f(u,v)</tex> <tex>\le leqslant c(u,v)</tex>).

Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> - — максимален, а разрез <tex><\langle S,T>\rangle</tex> - — минимален.

[[Файл:Минимальный_разрез.png|мини|справа|300x100px|Потоки и разрезы]]Из закона слабой двойственности следует, что <tex>f(S_1,T_1)\le 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)\le leqslant c(S_2,T_2)</tex>).Значит, если расположить все величины потоков и разрезов на оси OX, то у потоков с разрезами может быть максимум 1 точка пересечения. Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <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 (рус.)* [http://ru.wikipedia.org/wiki/Разрез_графа Википедия: Разрез графа]* [http://en.wikipedia.org/wiki/Cut_(graph_theory) Википедия: Разрез графа (англ.)] [[Категория:Алгоритмы и структуры данных]][[Категория:Задача о максимальном потоке]]