Определение сети, потока — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 25 промежуточных версий 9 участников)
Строка 4: Строка 4:
 
|id=flow_network
 
|id=flow_network
 
|definition=
 
|definition=
'''Сеть''' (англ. '''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>.
+
'''Сеть''' (англ. ''flow network'') <tex>G=(V,E)</tex> представляет собой [[Основные определения теории графов#oriented_grath|ориентированный граф]], в котором каждое [[Основные определения теории графов#def_graph_edge_1|ребро]] <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>.
+
В транспортной сети выделяются две вершины: '''исток''' <tex>s</tex> и '''сток''' <tex>t</tex>.
  
 
== Определение потока ==
 
== Определение потока ==
Строка 12: Строка 12:
 
|id=flow
 
|id=flow
 
|definition=
 
|definition=
'''Потоком''' (англ. '''flow''') <tex>f</tex> в <tex>G</tex> является действительная функция <tex>f\colon V\times V\to R</tex>, удоволетворяющая условиям:
+
'''Потоком''' (англ. ''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> (антисимметричность);
  
2) <tex>f(u,v)\le c(u,v)</tex> (ограничение пропускной способности), если ребра нет, то <tex>c(u,v)=0</tex>;
+
2) <tex>f(u,v) \leqslant c(u,v)</tex> (ограничение пропускной способности), если ребра нет, то <tex>f(u,v)=0</tex>;
  
 
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> (закон сохранения потока).
Строка 25: Строка 25:
 
|definition=
 
|definition=
 
'''Потоком''' <tex>f</tex> в сети <tex>G=(V,E,c)</tex> называется функция <tex>f\colon E\to R</tex>, удоволетворяющая условиям:
 
'''Потоком''' <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 \leqslant f(e) \leqslant 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,w)</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> s </tex> {{ --- }}  '''источник''', а <tex> t </tex> {{ --- }}  '''сток''' сети <tex>G</tex> (<tex>s</tex> имеет нулевую степень захода, а <tex>t</tex> имеет нулевую степень исхода); через <tex>v+</tex> обозначено множество вершин, к которым идут [[Основные определения теории графов#def_graph_edge_1|дуги]] из вершины <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>.
Условие 1) называется условием ограничения по пропускной способности, а условие 2) - условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину <tex>v</tex>, отличную от <tex>s</tex> или <tex>t</tex>, равен вытекающему из неё потоку.
+
Условие 1) называется условием ограничения по пропускной способности, а условие 2) {{---}} условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину <tex> v </tex>, отличную от <tex> s </tex> или <tex> t </tex>, равен вытекающему из неё потоку.
  
 
== Пример ==
 
== Пример ==
Вот пример сети с источником <tex>s</tex> и стоком <tex>t</tex>.
+
Пример сети с источником <tex>s</tex> и стоком <tex>t</tex>.
  
 
[[Файл:Flow-network.png|340px|center]]
 
[[Файл:Flow-network.png|340px|center]]
  
Первое число означает величину потока, второе - пропускную способность ребра. Отрицательные величины потока не указаны (так как они мгновенно получаются из антисимметричности: <tex>f(u,v)=-f(v,u)</tex>). Обратите внимание, что сумма входящих ребер везде (кроме источника и стока) равна сумме исходящих и на то, что в общем <tex>c(u,v) \neq c(v, u)</tex>. Кроме того, величина потока на ребре никогда не превышает пропускную способность этого ребра.
+
Первое число означает величину потока, второе {{---}} пропускную способность ребра. Отрицательные величины потока не указаны (так как они мгновенно получаются из антисимметричности: <tex>f(u,v)=-f(v,u)</tex>). Сумма входящих рёбер везде (кроме источника и стока) равна сумме исходящих и на то, что в общем <tex>c(u,v) \neq c(v, u)</tex>. Кроме того, величина потока на ребре никогда не превышает пропускную способность этого ребра.
  
Величина потока в этом примере равна 5 + 2 = 7 (считаем от вершины <tex>s</tex>).
+
Величина потока в этом примере равна <tex> 3 + 2 = 5 </tex> (считаем от вершины <tex>s</tex>).
  
 
== Источники информации ==
 
== Источники информации ==
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
 
* ''Асанов М. О., Баранский В. А., Расин В. В.'' — '''Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие.''' 2-е изд., испр. и доп. — СПб.: Издательство "Лань", 2010. — 368 с.: ил. — (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
 
* ''Асанов М. О., Баранский В. А., Расин В. В.'' — '''Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие.''' 2-е изд., испр. и доп. — СПб.: Издательство "Лань", 2010. — 368 с.: ил. — (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
* [http://ru.wikipedia.org/wiki/Транспортная_сеть Википедия: Транспортная сеть]
+
* [http://ru.wikipedia.org/wiki/Транспортная_сеть Википедия <tex>-</tex> Транспортная сеть]
* [http://en.wikipedia.org/wiki/Flow_network Wikipedia: Flow network]
+
* [http://en.wikipedia.org/wiki/Flow_network Wikipedia <tex>-</tex> Flow network]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Задача о максимальном потоке]]
 
[[Категория:Задача о максимальном потоке]]

Текущая версия на 19:22, 4 сентября 2022

Определение сети

Определение:
Сеть (англ. flow network) [math]G=(V,E)[/math] представляет собой ориентированный граф, в котором каждое ребро [math](u,v)\in E[/math] имеет положительную пропускную способность (англ. capacity) [math]c(u,v)\gt 0[/math]. Если [math](u,v)\notin E[/math], предполагается что [math]c(u,v)=0[/math].

В транспортной сети выделяются две вершины: исток [math]s[/math] и сток [math]t[/math].

Определение потока

Определение:
Потоком (англ. flow) [math]f[/math] в [math]G[/math] является действительная функция [math]f\colon V\times V\to R[/math], удоволетворяющая условиям:

1) [math]f(u,v)=-f(v,u)[/math] (антисимметричность);

2) [math]f(u,v) \leqslant c(u,v)[/math] (ограничение пропускной способности), если ребра нет, то [math]f(u,v)=0[/math];

3) [math]\sum\limits_v f(u,v)=0[/math] для всех вершин [math]u[/math], кроме [math]s[/math] и [math]t[/math] (закон сохранения потока).

Величина потока [math]f[/math] определяется как [math]|f|=\sum\limits_{v\in V} f(s,v)[/math].


Также существует альтернативное определение (по Асанову), не вводящее антисимметричность (зачастую, из-за этого с ним труднее работать):

Определение:
Потоком [math]f[/math] в сети [math]G=(V,E,c)[/math] называется функция [math]f\colon E\to R[/math], удоволетворяющая условиям:

1) [math]0 \leqslant f(e) \leqslant c(e)[/math] для всех [math]e\in E[/math];

2) [math]f(v-) = f(v+)[/math] для всех [math]v\in V, v\ne s, v\ne t[/math], где [math]f(v-)=\sum\limits_{w\in v-} f(w,v), f(v+)=\sum\limits_{w\in v+} f(v,w)[/math].

Здесь [math] s [/math]источник, а [math] t [/math]сток сети [math]G[/math] ([math]s[/math] имеет нулевую степень захода, а [math]t[/math] имеет нулевую степень исхода); через [math]v+[/math] обозначено множество вершин, к которым идут дуги из вершины [math]v[/math]; через [math]v-[/math] обозначено множество вершин, из которых идут дуги в вершину [math]v[/math]; [math]c(e)[/math] называется пропускной способностью дуги [math]e[/math] и неотрицательно.

Число [math]f(v,w)[/math] можно интерпретировать, например, как количество жидкости, поступающей из [math]v[/math] в [math]w[/math] по дуге [math](v,w)[/math]. С этой точки зрения значение [math]f(v-)[/math] может быть интерпретировано как поток, втекающий в вершину [math]v[/math], а [math] f(v+) [/math] — вытекающий из [math] v [/math]. Условие 1) называется условием ограничения по пропускной способности, а условие 2) — условием сохранения потока в вершинах; иными словами, поток, втекающий в вершину [math] v [/math], отличную от [math] s [/math] или [math] t [/math], равен вытекающему из неё потоку.

Пример

Пример сети с источником [math]s[/math] и стоком [math]t[/math].

Flow-network.png

Первое число означает величину потока, второе — пропускную способность ребра. Отрицательные величины потока не указаны (так как они мгновенно получаются из антисимметричности: [math]f(u,v)=-f(v,u)[/math]). Сумма входящих рёбер везде (кроме источника и стока) равна сумме исходящих и на то, что в общем [math]c(u,v) \neq c(v, u)[/math]. Кроме того, величина потока на ребре никогда не превышает пропускную способность этого ребра.

Величина потока в этом примере равна [math] 3 + 2 = 5 [/math] (считаем от вершины [math]s[/math]).

Источники информации

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 2-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2010. — 1296 с.: ил. — Парал. тит. англ. — ISBN 978-5-8459-0857-5 (рус.)
  • Асанов М. О., Баранский В. А., Расин В. В.Дискретная математика: Графы, матроиды, алгоритмы: Учебное пособие. 2-е изд., испр. и доп. — СПб.: Издательство "Лань", 2010. — 368 с.: ил. — (Учебники для вузов. Специальная литература). ISBN 978-5-8114-1068-2
  • Википедия [math]-[/math] Транспортная сеть
  • Wikipedia [math]-[/math] Flow network