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