37
правок
Изменения
м
== Источники информации ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е изд. — М.:Издательский дом "Вильямс", 2010. — 1296 C.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
правки
|statement=
Если <tex> f </tex> {{---}} некоторый [[Определение_сети,_потока|поток]] в сети <tex> G = (V, E) </tex> с источником <tex>s</tex> и стоком <tex>t</tex>, то следующие утверждения эквивалентны:
# Поток <tex> f </tex> максимален.# В <tex> G_f </tex> не существует пути <tex>s \leadsto t. </tex># <tex> |f| = c(S, T) </tex> для некоторого разреза <tex> (S, T) </tex> сети <tex> G . </tex>
|proof=
<tex> (1)\Rightarrow (2)</tex>
<tex> (3) \Rightarrow (1) </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 (рус.)
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о максимальном потоке ]]
