Изменения

Перейти к: навигация, поиск

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

485 байт добавлено, 18:02, 16 декабря 2015
Нет описания правки
== Определение разреза ==
{{Определение
# <tex>S = V\setminus T</tex>
}}
 
== Поток через разрез ==
{{Определение
|definition=
'''Пропускная способность разреза''' (англ. ''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=
'''Поток в разрезе''' (англ. ''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=
'''Минимальным разрезом''' (англ. ''minimum cut'') называется разрез с минимально возможной пропускной способностью
}}
{{Лемма
|about =
о величине потока
|statement =
Пусть <tex>\langle S,T\rangle</tex> — разрез в <tex>G</tex>. Тогда <tex>f(S,T)=|f|</tex>.
{{Лемма
|about =
о максимальном потоке и минимальном разрезе
|statement =
Если <tex>f(S,T)=c(S,T)</tex>, то поток <tex>f</tex> — максимален, а разрез <tex>\langle S,T\rangle</tex> — минимален.
Из закона слабой двойственности следует, что <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 точка пересечения.
Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>. }}  [[Файл:разрезы.png|мини|слева|500x200px800x600px| Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети. ]][[Файл <br clear="all"> {|border="1" class="wikitable" style="width: 400px; height: 150px; float:таблица.png|мини|слева;" |500x200px+ 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 }|}
== Источники информации ==
Анонимный участник

Навигация