308
правок
Изменения
Нет описания правки
{{Определение
|definition=
<b><tex>(s,t)</tex>-разрезом</b> (англ. '''s-t cut''') <tex>\langle S,T\rangle</tex> в сети <tex>G</tex> называется пара множеств <tex>S,T</tex>, удоволетворяющих условиям:
1) <tex>s\in S, t\in T</tex>
|definition=
Поток в разрезе <tex>\langle S,T\rangle</tex> обозначается <tex>f(S,T)</tex> и вычисляется по формуле: <tex>f(S,T)=\sum\limits_{u\in S}\sum\limits_{v\in T}f(u,v)</tex>.
}}
{{Определение
|definition=
Минимальным разрезом называется разрез с минимально возможной пропускной способностью
}}
== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
== Ссылки ==
* [http://ru.wikipedia.org/wiki/Разрез_графа Википедия: Разрез графа]
* [http://en.wikipedia.org/wiki/Cut_(graph_theory) Википедия: Разрез графа (англ.)]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Задача о максимальном потоке]]
