Теорема Форда-Фалкерсона

Теорема:

Если [math] f [/math] — некоторый поток в сети [math] G = (V, E) [/math] с источником [math]s[/math] и стоком [math]t[/math], то следующие утверждения эквивалентны: Поток [math] f [/math] максимален. В [math] G_f [/math] не существует пути [math]s \leadsto t. [/math] [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 (рус.)