Изменения

'''Сеть''' (англ. ''flow network'') <btex>СетьюG=(V,E)</btex> называется взвешенный представляет собой [[Основные определения теории графов#oriented_grath|ориентированный граф ]], в котором каждое [[Основные определения теории графов#def_graph_edge_1|ребро]] <tex>G=(Vu,v)\in E</tex> имеет положительную '''пропускную способность''' (англ. ''capacity'') <tex>c(u,v)>0</tex>. Если <tex>(u,cv)\notin E</tex>, где предполагается что <tex>c\colon E\to R(u,v)=0</tex> - весовая функция.

'''Потоком''' (англ. ''flow'') <btex>Транспортная сетьf</btex> (flow network) в <tex>G=(</tex> является действительная функция <tex>f\colon V\times V,E)\to R</tex> представляет собой ориентированный граф, в котором каждое ребро удоволетворяющая условиям:1) <tex>f(u,v)\in E=-f(v,u)</tex> имеет неотрицательную <b>пропускную способность</b> (capacityантисимметричность); 2) <tex>f(u,v) \leqslant c(u,v)>0</tex>. Если (ограничение пропускной способности), если ребра нет, то <tex>f(u,v)\notin E=0</tex>, предполагается что ; 3) <tex>c\sum\limits_v f(u,v)=0</tex>. В транспортной сети выделяются две вершины: для всех вершин <btex>источникu</btex> , кроме <tex>s</tex> и <btex>стокt</btex> (закон сохранения потока).'''Величина''' потока <tex>f</tex> определяется как <tex>t|f|=\sum\limits_{v\in V} f(s,v)</tex>.

<b>'''Потоком</b> ''' <tex>f</tex> в сети <tex>G=(V,E,c)</tex> называется функция <tex>f\colon E\to R</tex>, удоволетворяющая условиям:1) <tex>f_{uv}=-f_{vu}0 \leqslant f(e) \leqslant c(e)</tex> для всех <tex>e\in E</tex> (антисимметричность);

2) <tex>f_f(v-) = f(v+)</tex> для всех <tex>v\in V, v\ne s, v\ne t</tex>, где <tex>f(v-)=\sum\limits_{uvw\in v-}f(w,v), f(v+)=\sum\le c_limits_{uvw\in v+}f(v,w)</tex>.Здесь <tex> s </tex> (подчинение пропускным способностям) {{ --- }} '''источник''', если ребра нет, то а <tex> t </tex>c_ {{uv--- }}=0 '''сток''' сети <tex>G</tex> (<tex>s</tex> имеет нулевую степень захода, а <tex>t</tex>имеет нулевую степень исхода);3) через <tex>\sum\limits_v f_{uv}=0v+</tex> для всех обозначено множество вершин , к которым идут [[Основные определения теории графов#def_graph_edge_1|дуги]] из вершины <tex>uv</tex>, кроме ; через <tex>sv-</tex> и обозначено множество вершин, из которых идут дуги в вершину <tex>tv</tex> ; <tex>c(закон сохранения потокаe)</tex> называется '''пропускной способностью''' дуги <tex>e</tex> и неотрицательно.

Альтернативное определение (по Асанову):{{Определение|definition== Пример ==Пример сети с источником <btex>Потокомs</btex> и стоком <tex>ft</tex> в сети . [[Файл:Flow-network.png|340px|center]] Первое число означает величину потока, второе {{---}} пропускную способность ребра. Отрицательные величины потока не указаны (так как они мгновенно получаются из антисимметричности: <tex>Gf(u,v)=-f(V,Ev,cu)</tex> называется функция ). Сумма входящих рёбер везде (кроме источника и стока) равна сумме исходящих и на то, что в общем <tex>fc(u,v) \colon E\to Rneq c(v, u)</tex>. Кроме того, удоволетворяющая условиям:величина потока на ребре никогда не превышает пропускную способность этого ребра. 1) Величина потока в этом примере равна <tex> 3 + 2 = 5 </tex> (считаем от вершины <tex>s</tex>0\le f). == Источники информации ==* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (eрус.)\le c* ''Асанов М. О., Баранский В. А., Расин В. В.'' — '''Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие.''' 2-е изд., испр. и доп. — СПб.: Издательство "Лань", 2010. — 368 с.: ил. — (eУчебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2* [http://ru.wikipedia.org/wiki/Транспортная_сеть Википедия <tex>-</tex> для всех Транспортная сеть]* [http://en.wikipedia.org/wiki/Flow_network Wikipedia <tex>e\in E-</tex>;Flow network]

2) <tex>f(v-) = f(v+)</tex> для всех <tex>v\in V, v\ne s, v\ne t</tex>, где <tex>f(v-)=\sum\limits_{w\in v-} f(w,v), f(v+)=\sum\limits_{w\in v+} f(v,u)</tex>.Здесь <tex>s</tex> - <b>источник</b>, а <tex>t</tex> - <b>сток</b> сети <tex>G</tex> (<tex>s</tex> имеет нулевую степень захода, а <tex>t</tex> имеет нулевую степень исхода); через <tex>v+</tex> обозначено множество вершин, к которым идут дуги из вершины <tex>v</tex>; через <tex>v-</tex> обозначено множество вершин, из которых идут дуги в вершину <tex>v</tex>; <tex>c(e)</tex> называется <b>пропускной способностью</b> дуги <tex>e</tex> [[Категория:Алгоритмы и неотрицательно.}}Число <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>, равен вытекающему из неё потоку.[[Категория:Задача о максимальном потоке]]