Материал из Викиконспекты
| Теорема: |
Если [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 (рус.)
