Определение сети, потока — различия между версиями
(→Определение сети) |
(→Определение потока) |
||
| Строка 10: | Строка 10: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | + | '''Потоком''' (англ. '''Flow''') <tex>f</tex> в <tex>G</tex> является действительная функция <tex>f\colon V\times V\to R</tex>, удоволетворяющая условиям: | |
1) <tex>f(u,v)=-f(v,u)</tex> (антисимметричность); | 1) <tex>f(u,v)=-f(v,u)</tex> (антисимметричность); | ||
| Строка 16: | Строка 16: | ||
3) <tex>\sum\limits_v f(u,v)=0</tex> для всех вершин <tex>u</tex>, кроме <tex>s</tex> и <tex>t</tex> (закон сохранения потока). | 3) <tex>\sum\limits_v f(u,v)=0</tex> для всех вершин <tex>u</tex>, кроме <tex>s</tex> и <tex>t</tex> (закон сохранения потока). | ||
| − | + | '''Величина''' потока <tex>f</tex> определяется как <tex>|f|=\sum\limits_{v\in V} f(s,v)</tex>. | |
}} | }} | ||
| Строка 22: | Строка 22: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
| − | + | '''Потоком''' <tex>f</tex> в сети <tex>G=(V,E,c)</tex> называется функция <tex>f\colon E\to R</tex>, удоволетворяющая условиям: | |
1) <tex>0\le f(e)\le c(e)</tex> для всех <tex>e\in E</tex>; | 1) <tex>0\le f(e)\le c(e)</tex> для всех <tex>e\in E</tex>; | ||
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>. | 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> - | + | Здесь <tex>s</tex> - '''источник''', а <tex>t</tex> - '''сток''' сети <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> называется '''пропускной способностью''' дуги <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>. | Число <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>. | ||
Версия 06:07, 22 января 2011
Определение сети
| Определение: |
| Сеть (англ. Flow network) представляет собой ориентированный граф, в котором каждое ребро имеет неотрицательную пропускную способность (англ. capacity) . Если , предполагается что . |
В транспортной сети выделяются две вершины: источник и сток .
Определение потока
| Определение: |
| Потоком (англ. Flow) в является действительная функция , удоволетворяющая условиям:
1) (антисимметричность); 2) (ограничение пропускной способности), если ребра нет, то ; 3) для всех вершин , кроме и (закон сохранения потока). Величина потока определяется как . |
Также существует альтернативное определение (по Асанову), не вводящее антисимметричность (зачастую, из-за этого с ним труднее работать):
| Определение: |
| Потоком в сети называется функция , удоволетворяющая условиям:
1) для всех ; 2) для всех , где . Здесь - источник, а - сток сети ( имеет нулевую степень захода, а имеет нулевую степень исхода); через обозначено множество вершин, к которым идут дуги из вершины ; через обозначено множество вершин, из которых идут дуги в вершину ; называется пропускной способностью дуги и неотрицательно. |
Число можно интерпретировать, например, как количество жидкости, поступающей из в по дуге . С этой точки зрения значение может быть интерпретировано как поток, втекающий в вершину , а - вытекающий из . Условие 1) называется условием ограничения по пропускной способности, а условие 2) - условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину , отличную от или , равен вытекающему из неё потоку.
Литература
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
- Асанов М. О., Баранский В. А., Расин В. В. — Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. — СПб.: Издательство "Лань", 2010. — 368 с.: ил. — (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
