Редактирование: Теорема Форда-Фалкерсона

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 1: Строка 1:
 
{{Теорема
 
{{Теорема
 
|statement=
 
|statement=
Если <tex> f </tex> {{---}} некоторый [[Определение_сети,_потока|поток]] в сети <tex> G = (V, E) </tex> с источником <tex>s</tex> и стоком <tex>t</tex>, то следующие утверждения эквивалентны:
+
Если <tex> f </tex> {{---}} некоторый поток в сети <tex> G = (V, E) </tex> с источником <tex>s</tex> и стоком <tex>t</tex>, то следующие утверждения эквивалентны:
# Поток <tex> f </tex> максимален.
+
# Поток <tex> f </tex> максимален
# В <tex> G_f </tex> не существует пути <tex>s \leadsto t. </tex>
+
# В <tex> G_f </tex> не существует пути <tex>s \leadsto t</tex>
# <tex> |f| = c(S, T) </tex> для некоторого разреза <tex> (S, T) </tex> сети <tex> G. </tex>
+
# <tex> |f| = c(S, T) </tex> для некоторого разреза <tex> (S, T) </tex> сети <tex> G </tex>
 
|proof=
 
|proof=
 
<tex> (1)\Rightarrow (2)</tex>
 
<tex> (1)\Rightarrow (2)</tex>
Строка 15: Строка 15:
  
 
Рассмотрим множество <tex> S = \lbrace v \in V : \exists\, s \leadsto v \text{ in } G_f \rbrace </tex> и <tex> T = V \setminus S</tex>.  
 
Рассмотрим множество <tex> S = \lbrace v \in V : \exists\, s \leadsto v \text{ in } G_f \rbrace </tex> и <tex> T = V \setminus S</tex>.  
Разбиение <tex> \langle S, T \rangle</tex> является разрезом, так как по <tex> (2) </tex> в <tex> G_f </tex> не существует <tex> s \leadsto t</tex>.
+
Разбиение <tex> S </tex> и <tex> T </tex> является разрезом, так как не существует <tex> s \leadsto t</tex>.
 
По [[Разрез,_лемма_о_потоке_через_разрез|лемме о потоке через разрез]] <tex> f(S, T) = |f| </tex>. Также <tex> \forall u \in S, v \in T</tex> известно, что <tex>f(u, v) = c(u, v) </tex>, так как иначе вершина <tex> v </tex>  
 
По [[Разрез,_лемма_о_потоке_через_разрез|лемме о потоке через разрез]] <tex> f(S, T) = |f| </tex>. Также <tex> \forall u \in S, v \in T</tex> известно, что <tex>f(u, v) = c(u, v) </tex>, так как иначе вершина <tex> v </tex>  
 
должна была бы принадлежать множеству <tex> S </tex>. Поэтому <tex> c(S, T) = f(S, T) = |f| </tex>.
 
должна была бы принадлежать множеству <tex> S </tex>. Поэтому <tex> c(S, T) = f(S, T) = |f| </tex>.
Строка 21: Строка 21:
 
<tex> (3) \Rightarrow (1) </tex>
 
<tex> (3) \Rightarrow (1) </tex>
  
Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \leqslant c(S, T)</tex>, поэтому <tex> f </tex> максимален.
+
Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \le c(S, T)</tex>, поэтому <tex> f </tex> максимален
 
}}
 
}}
  
== См. также ==
 
* [[Определение_сети,_потока|Определение сети, потока]]
 
* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
 
  
== Источники информации ==
+
== Литература ==
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
  
[[Категория: Алгоритмы и структуры данных]]
+
== См. также ==
[[Категория: Задача о максимальном потоке ]]
+
* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]

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

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

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

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