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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 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> S </tex> и <tex> T </tex> является разрезом, так как не существует <tex> s \leadsto t</tex>.
+
Разбиение <tex> \langle S, T \rangle</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>.

Версия 10:42, 22 декабря 2010

Теорема:
Если [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] 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| \le c(S, T)[/math], поэтому [math] f [/math] максимален
[math]\triangleleft[/math]


Литература

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)

См. также