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

UptoLike

ВУЗ: 

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

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

Рубрика: 

36
СЛЕДСТВИЕ 2.2.1. Если
(
)
(
)
T S,C fal
=
υ
для некоторого потока
ƒ
, а
a
-
z
сечения (
S, T
), то
ƒ
– максимальный поток, а
C
– минимальное сечение.
СЛЕДСТВИЕ 2.2.2. Для некоторого потока
ƒ
и
a
-
z
сечения (
S
,
T
) ра-
венство
() ( )
T S,C fal =
υ
имеет место тогда и только тогда, когда
ƒ(е) = с(e)
для
всех
e
∈ (
S, T
) и ƒ(
e
) = 0 для всех
e
∈ (
T, S
).
Опишем способы определения максимального потока сети. Рассмотрим
сеть, изображенную на рис. 2.3.
Рис. 2.3
Максимальный поток (не обязательно единственный) легко найти способом,
проиллюстрированным на рис. 2.4.
Рис. 2.4.
В данном случае известно, что поток максимальный, потому что величи-
на потока, выходящего и
а
, не может превысить сумму пропускных способно-
стей ребер, выходящих из
а
.
Рассмотрим сеть, изображенную на рис. 2.5.
Рис. 2.5.
6
4
b
c
z
d
a
e
ƒ
7
5
7
2
3
4
5
b
c
z
d
a
e
ƒ
(6, 5)
(7, 7)
(5, 5)
(7, 2)
(2, 2)
(3, 0)
(4, 4)
(4, 4)
(5, 4)
b c
z a
d
e
(3, 3)
(8, 6)
(9, 6)
(5, 3)
(7, 7)
(4, 4)
(7, 7)
(5, 3)

Страницы