ВУЗ:
Составители:
80
С понятием транспортной сети связано понятие потока. Пусть х
– произвольная вершина сети. Обозначим через U
x
-
множество дуг,
заходящих в x, а через U
x
+
- выходящих из х. Потоком по транспорт-
ной сети называют функцию
ϕ
(u), удовлетворяющую следующим ус-
ловиям
0
≤ϕ
(u)
≤
c(u), u
∈
U
x
, U
x
=U
x
-
∪
U
x
+
; (2.8)
0)()( =−
∑∑
∈∈ CuBu
uu
ϕ
ϕ
, x
≠
x
0
, x
≠
z. B=U
x
-
, C= U
x
+
(2.9)
Физический смысл функции
ϕ
(u) - это количество вещества,
протекающего в единицу времени по дуге u=(x,y) от х к y. Это коли-
чество согласно (2.8) не может превышать пропускной способности
дуги с(u). Согласно (2.9) в каждой вершине х, отличной х
0 и z, коли-
чество протекающего вещества равно количеству вытекающего. Это
означает, что поток из х
0 в точности равен потоку, выходящему в z
−+
∈∈
====
∑∑
zxz
CuBu
UCUBuu ;)()(
ϕϕϕ
. Величину
ϕ
(z) называют величи-
ной потока транспортной сети.
К анализу транспортных сетей сво-
дятся многие задачи, возникающие при планировании поставок, рас-
пределении товаров по потребителям, задачи теории надёжности и
т.п. Приведем типичный пример транспортной сети (рис. 2.51). Циф-
ры в разрывах дуг - пропуск-
ная способность дуги. Стрелки
указывают направление пото-
ков; если их нет, то поток ра-
вен
нулю. Цифры около стре-
лок – это величины потоков.
Введём понятие разреза
транспортной сети. Пусть
А
⊂
Х, удовлетворяет условиям x
0
∉
A, z
∈
A. Через U
A
-
и через U
A
+
обо-
значим, соответственно, множество дуг, заходящих в A и выходящих
А
Рис. 2.51
4
-
3
+
+
2
2
1
3
1
0
0
3
1
x
0
x
1
x
4
x
2
x
3
z
1
6
2
1
3
3
1
2
5
Страницы
- « первая
- ‹ предыдущая
- …
- 82
- 83
- 84
- 85
- 86
- …
- следующая ›
- последняя »
