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

UptoLike

ВУЗ: 

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

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

Рубрика: 

37
Кажется, что у этой сети максимальный поток, потому что не существует
ориентированного пути, по которому можно увеличить поток. Заметим, однако,
что сеть на рис. 2.6 имеет больший поток, и, фактически, он максимальный.
Рис. 2.6
Следует обратить внимание, что если поток из источника равен сумме
пропускных способностей ребер, выходящих из источника, или поток, втекаю-
щий в сток, равен сумме пропускных способностей ребер, входящих в сток, то
поток максимальный. Однако, поток может быть максимальным и без удовле-
творения какого-либо из этих признаков. Например, сеть на рис
. 2.7 имеет мак-
симальный поток.
Рис. 2.7
Итак, как же находить максимальные в смысле потока сети? Для этого
сформируем пути из
a
в
z
, не обращая внимания на направление ребер. Такие
пути назовем цепями. Рассмотрим снова сеть с потоком, изображенную на рис.
2.5. Одним и таких путей является
(
)
(
)
(
)
z.cb a
6 9,3 3,6 8,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
⎯
⎯
→
⎯
Очевидно, что нет возможности увеличить поток по этому пути, поскольку
ребро из
b
в
c
наполнено до его пропускной способности. То же самое верно и
для цепи
(
)
(
)
(
)
z.еb a
7 7,3 5,6 8,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
⎯
⎯
→
⎯
Однако, при рассмотрение цепи
b c
z a
d
e
(3, 3)
(8, 8)
(9, 8)
(5, 5)
(7, 7)
(4, 2)
(7, 7)
(5, 5)
b c
z a
d
e
(1, 1)
(4, 1)
(6, 1)
(6, 2)
(2, 2)
(5, 2)

Страницы