Графы и сети. Харитонова Е.В. - 34 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

33
Рис. 2.1
Для этой сети, которая представлена как нефтепровод, введем понятие
потока (количество нефти, проходящее через трубы нефтепровода). Таким об-
разом, для каждого ребра
e
имеется значение
ƒ
(
e
), которое является потоком
через конкретное ребро или трубу. Очевидно, величина потока не может пре-
высить пропускную способность трубы. Потребуем также, чтобы поток, вхо-
дящий в вершину, был равен потоку, выходящему из вершины, за исключением
вершин
a
и
z
.
Это называется
сохранением потока
. Пусть in(
υ
) – множество ребер, для
которых
υ
– конечная вершина, и out(
υ
) – множество ребер, для которых
υ
– на-
чальная вершина. Таким образом, out(
υ
) – множество ребер, выходящих из
вершины
υ
, и in(
υ
) – множество ребер, входящих в вершину
υ
. Следовательно,
имеем следующее определение.
●
Поток
в сети – это функция ƒ :
E
→
N
∪ {0} такая, что
()
(
)
(
)
() ()
()
()
()
∑∑
∈∈
ƒ=ƒ≠∈
≤
ƒ
≤∈
υυ
υυ
out ein e
e e z, a, что таких, V всех для ii
еc e 0 E, e всех для i
.
;
Допустим, имеется фиксированный поток. Пусть
()
(
)
()
∑
∈
ƒ
=
a
eaпоток
out e
,
т.е.
()
aпоток
– поток, вытекающий из источника
а
, и
()
(
)
()
∑
∈
ƒ=
z
ezпоток
in e
, т.е.
(
)
zпоток
– поток, втекающий в сток
z
. Пример по-
тока в сети, где первый элемент упорядоченной пары на каждом ребре – пропу-
скная способность, а второй – поток, демонстрирует рис. 2.2.
Рис. 2.2
Поток через каждое ребро меньше, чем его пропускная способность. Об-
ратите внимание, что для вершины
b
поток, втекающий в
b
, равен 4 и поток,
b
c
z
d
a
e
ƒ
(6, 3)
(7, 4)
(5, 3)
(7, 2)
(2, 1)
(3, 1)
(4, 2)
(4, 1)
(5, 1)
6
4
b
c
z
d
a
e
ƒ
7
5
7 2
3
4
5

Страницы