Теорема Форда-Фалкерсона — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 4 участников)
Строка 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> s \leadsto t</tex>.
+
Разбиение <tex> \langle S, T \rangle</tex> является разрезом, так как по <tex> (2) </tex> в <tex> G_f </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| \le c(S, T)</tex>, поэтому <tex> f </tex> максимален
+
Так как существует разрез, такой что <tex> |f| = c(S, T) </tex>, то согласно [[Разрез,_лемма_о_потоке_через_разрез|следствию леммы о слабой двойственности потока и разреза]] <tex> |f| \leqslant 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 (рус.)
  
−
== См. также ==
+
[[Категория: Алгоритмы и структуры данных]]
−
* [[Алгоритм_Форда-Фалкерсона,_реализация_с_помощью_поиска_в_глубину|Алгоритм Форда-Фалкерсона, реализация с помощью поиска в глубину]]
+
[[Категория: Задача о максимальном потоке ]]

Текущая версия на 19:12, 4 сентября 2022

Теорема:
Если [math] f [/math] — некоторый поток в сети [math] G = (V, E) [/math] с источником [math]s[/math] и стоком [math]t[/math], то следующие утверждения эквивалентны:
  1. Поток [math] f [/math] максимален.
  2. В [math] G_f [/math] не существует пути [math]s \leadsto t. [/math]
  3. [math] |f| = c(S, T) [/math] для некоторого разреза [math] (S, T) [/math] сети [math] G. [/math]
Доказательство:
[math]\triangleright[/math]

[math] (1)\Rightarrow (2)[/math]

Докажем от противного. Предположим, что в [math] G_f [/math] существует какой-нибудь путь [math]p = s \leadsto t[/math]. Тогда рассмотрим [math] f + f_p [/math]. По лемме о сумме потоков [math] f + f_p [/math] тоже является потоком в сети [math] G [/math], и причем [math] |f + f_p| = |f| + |f_p| \gt |f| [/math], что приводит нас к противоречию, что [math] f [/math] максимальный поток.

[math] (2) \Rightarrow (3) [/math]

Рассмотрим множество [math] S = \lbrace v \in V : \exists\, s \leadsto v \text{ in } G_f \rbrace [/math] и [math] T = V \setminus S[/math]. Разбиение [math] \langle S, T \rangle[/math] является разрезом, так как по [math] (2) [/math] в [math] G_f [/math] не существует [math] s \leadsto t[/math]. По лемме о потоке через разрез [math] f(S, T) = |f| [/math]. Также [math] \forall u \in S, v \in T[/math] известно, что [math]f(u, v) = c(u, v) [/math], так как иначе вершина [math] v [/math] должна была бы принадлежать множеству [math] S [/math]. Поэтому [math] c(S, T) = f(S, T) = |f| [/math].

[math] (3) \Rightarrow (1) [/math]

Так как существует разрез, такой что [math] |f| = c(S, T) [/math], то согласно следствию леммы о слабой двойственности потока и разреза [math] |f| \leqslant c(S, T)[/math], поэтому [math] f [/math] максимален.
[math]\triangleleft[/math]

См. также

Источники информации

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Форда-Фалкерсона&oldid=84607»