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

UptoLike

ВУЗ: 

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

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

Рубрика: 

44
и поскольку резерв вершины z равен 7, добавляем 7 к каждому потоку, получая
()
(
)
(
)
z, e d a
7 7,7 9,7 8,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
что изображено на рис. 2.16
Рис. 2.16
На третьем проходе помечаем а(-, ∞), b(a, 5), d(a, 1), c(d, 1), e(d, 1) и z(с, 1). Это дает a
– z путь
()
(
)
(
)
z, с d a
4 8,0 4,7 8,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
и поскольку резерв z равен 1, добавляем 1 к каждому потоку, получая
()
(
)
(
)
z, с d a
5 8,1 4,8 8,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
что изображено на рис. 2.17.
Рис. 2.17
Теперь начинается кое-что поинтересней, поэтому дальнейшее описание будет более
подробным. Пометим b(a, 5), но d пометить нельзя; помещаем b в S. При выборе вершины b
из множества S нельзя пометить вершину c, но можно пометить е(b, 5); помещаем вершину с
во множество S. Выбирая е из S, нельзя пометить вершину z, но т.к. d еще не помечена, ее
можно пометить. Поскольку ребро (d, e) ориентировано неправильно, полагаем резерв вер-
шины d равным min(7, 5) = 5. Устанавливаем е в качестве предшественника вершины d и по-
мещаем вершину d во множество S. Выбирая вершину d из множества S, имеем единствен-
ную возможность – пометить вершину c(d, 3) и поместить с в S. Выбираем вершину с из
множества S и помечаем z(c, 3). Это дает a – z путь
b (а, 5) c (d, 4)
z (e, 7)
a (-, ∞)
d
(
a
,
8
)
e (d, 8)
(4, 4)
(9, 4)
(8, 4)
(4, 0)
(8, 7)
(9, 7)
(7, 7)
(6, 0)
b (а, 5) c (d, 1)
z (с, 1)
a (-, ∞)
d
(
a
,
1
)
e (d, 1)
(4, 4)
(9, 4) (8, 5)
(4, 1)
(8, 8)
(9, 7)
(7, 7)
(6, 0)

Страницы