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

UptoLike

ВУЗ: 

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

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

Рубрика: 

43
Рис. 2.13
Пример. Найдите максимальный поток для сети, изображенной на рис. 2.14.
Рис. 2.14
Первые несколько проходов ничем не примечательны, поэтому опишем их вкратце.
На первом проходе помечаем а(-, ∞), b(a, 9), d(a, 8), c(b, 4), e(b, 4) и z(c, 4). Это дает a – z
путь
()
(
)
(
)
z, c b a
0 8,0 4,0 9,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
и поскольку резерв z равен 4, добавляем 4 к каждому потоку, получая
()
(
)
(
)
z, c b a
4 8,4 4,4 9,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
что изображено на рис. 2.15
Рис. 2.15
На втором проходе помечаем а(-, ∞), b(a, 5), d(a, 8), c(d, 4), e(d, 8) и z(e, 7). Это дает a
– z путь
()
(
)
(
)
z, e d a
0 7,0 9,0 8,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
b c
z a
d
e
4
9
8
4
8
9
7
6
b (а, 9) c (b, 4)
z (c, 4)
a (-,
∞
)
d
(
a
,
8
)
e (b, 4)
(4, 4)
(9, 4)
(8, 4)
(4, 0)
(8, 0)
(9, 0)
(7, 0)
(6, 0)

Страницы