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

UptoLike

ВУЗ: 

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

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

Рубрика: 

41
На шаге 2 проверяем, не пусто ли множество S, и выбираем из него вершину а. На
шаге 3 полагаем резерв вершины b равным min(7, ∞) = 7 и устанавливаем вершину а в каче-
стве предшественника вершины b. Помещаем вершину b во множество S. Устанавливаем ре-
зерв вершины d равным min(6, ∞) = 6 и устанавливаем вершину а в качестве предшественни-
ка вершины d. Помещаем вершину d во множество S. Шаги 4 и 5 не применяем, поэтому воз-
вращаемся к шагу 2.
Проверяем, не является ли множество S пустым, и выбираем из него вершину, напри-
мер, b. Теперь множество S содержит только вершину d. На шаге 3 полагаем резерв вершины
с равным min(3, 7) = 3 и устанавливаем вершину b в качестве предшественника вершины с.
Помещаем вершину с во множество S = {c, d}. Опять шаги 4 и 5 не применяем и возвраща-
емся к шагу 2.
Проверяем, не является ли множество S пустым, и выбираем из S вершину, например,
с. Множество S опять содержит только вершину d. На шаге 3 полагаем резерв вершины z
равным min(3, 5) = 3 и устанавливаем вершину с в качестве предшественника вершины z. Не
помещаем z во множество S. На шаге 4 следует пометить вершину d, но она уже помечена.
На шаге 5 видим, что вершина z уже помечена, и, используя функцию предшествова-
ния, находим цепь
()
(
)
(
)
z.cb a
0 5,0 3,0 7,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
⎯
⎯
→
⎯
Добавляя 3 (резерв вершины z) к потоку каждого ребра, получаем
()
(
)
(
)
z, c b a
3 5,3 3,3 7,
⎯⎯→⎯⎯⎯→⎯⎯⎯→⎯
что дает сеть, изображенную на рис. 2.10.
Рис. 2.10
Теперь возвращаемся к шагу 1, где переустанавливаем метки и предшественников и
полагаем S = {a}. На шаге 2 выбираем вершину а и множества S. На шаге 3 устанавливаем
резерв вершины b равным min(∞, 7 - 3) = 4 и устанавливаем а в качестве предшественника
вершины b. Помещаем вершину b во множество S. Полагаем также резерв вершины d рав-
ным 6 и устанавливаем вершину а в качестве предшественника вершины d. Помещаем вер-
шину d во множество S. Шаги 4 и 5 не применяем, поэтому возвращаемся к шагу 2. Выбира-
ем вершину b из множества S. Поскольку поток из b в с равен пропускной способности из b в
c, то вершину с не помечаем. Выбираем вершину d из множества S и продолжаем процесс,
после чего получаем цепь.
(
)
(
)
zd a
0 2,0 6,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
и добавляя 2 (резерв вершины z) к потоку каждого ребра, получаем цепь
b (а, 7)
c (b, 3)
z (с, 3)
d
(а, 6)
a (-,
∞
)
(6, 0)
(3, 3)
(5, 3)
(7, 3)
(2, 0)
(2, 0)

Страницы