Редактирование: Разрез, лемма о потоке через разрез

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 +
== Определение разреза ==
  
 
{{Определение
 
{{Определение
Строка 7: Строка 8:
 
# <tex>S = V\setminus T</tex>
 
# <tex>S = V\setminus T</tex>
 
}}
 
}}
 +
 +
== Поток через разрез ==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|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>.
+
'''Пропускная способность разреза''' <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=
'''Поток в разрезе''' (англ. ''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>.
+
'''Поток в разрезе''' <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=
'''Минимальным разрезом''' (англ. ''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>.
Строка 53: Строка 54:
  
 
{{Лемма
 
{{Лемма
|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> — минимален.
Строка 61: Строка 60:
 
Из закона слабой двойственности следует, что <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>.
 
Из закона слабой двойственности следует, что <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 точка пересечения.
Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>.}}
+
Очевидно, что эта точка определяет максимальный поток среди всех потоков и минимальный разрез среди всех разрезов сети <tex>G</tex>.  
 
+
[[Файл:разрезы.png|мини|слева|500x200px| Среди всех разрезов сети разрез с минимальной пропускной способностью определяет максимальный поток в сети. ]][[Файл:таблица.png|мини|слева|500x200px|Минимальны разрез — 1 с пропускной способностью 60.]]
+
}}
[[Файл:разрезы.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
 
 
 
|}
 
  
 
== Источники информации ==
 
== Источники информации ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: