141
правка
Изменения
Нет описания правки
{{Определение
|definition=
<b>Сетью</b> называется взвешенный ориентированный граф <tex>G=(V,E,c)</tex>, где <tex>c\colon E\to R</tex> - весовая функция.}} {{Определение|definition=<b>Транспортная сетьСеть</b> (flow network) <tex>G=(V,E)</tex> представляет собой ориентированный граф, в котором каждое ребро <tex>(u,v)\in E</tex> имеет неотрицательную <b>пропускную способность</b> (capacity) <tex>c(u,v)>0</tex>. Если <tex>(u,v)\notin E</tex>, предполагается что <tex>c(u,v)=0</tex>. В транспортной сети выделяются две вершины: <b>источник</b> <tex>s</tex> и <b>сток</b> <tex>t</tex>.
}}
В транспортной сети выделяются две вершины: <b>источник</b> <tex>s</tex> и <b>сток</b> <tex>t</tex>.
== Определение потока ==
}}
{{Определение
|definition=
Число <tex>f(v,w)</tex> можно интерпретировать, например, как количество жидкости, поступающей из <tex>v</tex> в <tex>w</tex> по дуге <tex>(v,w)</tex>. С этой точки зрения значение <tex>f(v-)</tex> может быть интерпретировано как поток, втекающий в вершину <tex>v</tex>, а <tex>f(v+)</tex> - вытекающий из <tex>v</tex>.
Условие 1) называется условием ограничения по пропускной способности, а условие 2) - условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину <tex>v</tex>, отличную от <tex>s</tex> или <tex>t</tex>, равен вытекающему из неё потоку.
== Литература ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
* ''Асанов М. О., Баранский В. А., Расин В. В.'' — '''Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие.''' 2-е изд., испр. и доп. — СПб.: Издательство "Лань", 2010. — 368 с.: ил. — (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
