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

UptoLike

ВУЗ: 

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

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

Рубрика: 

42
(
)
(
)
z.d a
2 2,2 6,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
Текущая ситуация изображена на рис. 2.11.
Рис. 2.11
Снова возвращаемся к шагу 1 и повторяем процесс, пока не получим цепь
()
(
)
(
)
z.cd a
3 5,0 2,2 6,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
⎯
⎯
→
⎯
Добавляя 2 (резерв вершины z) к потоку каждого ребра, получаем
()
(
)
(
)
z.cd a
5 5,2 2,4 6,
⎯
⎯
→
⎯
⎯
⎯
→
⎯
⎯
⎯
→
⎯
Ситуация изображена на рис. 2.12.
Рис. 2.12
Возвращаемся к шагу 1, переустанавливаем метки предшественника и полагаем S =
{а}. На шаге 2 выбираем вершину а из множества S. Как и ранее, на шаге 3 полагаем резерв
вершины b равным 4 и устанавливаем вершину а в качестве предшественника вершины b.
Помещаем вершину b во множество S. Устанавливаем также резерв вершины d равным 6 - 4
= 2 и помещаем вершину d во множество S. Возвращаемся к шагу 2. Выбираем вершину b из
множества S. Поскольку поток из вершины b в вершину с равен пропускной способности из
b в с, пометить с нельзя, поэтому, в конце концов, возвращаемся к шагу 2. Выбираем верши-
ну d из множества S. Поскольку поток из вершины d в вершину с и вершину z равен их про-
пускным способностям, нельзя помечать с и z. Опять возвращаемся к шагу 2, но множество S
пусто. Процесс закончен. Окончательный поток изображен на рис. 2.13.
b (а, 4)
c (d, 2)
z (d, 2)
d
(а, 6)
a (-,
∞
)
(6, 2)
(3, 3)
(5, 3)
(7, 3)
(2, 0)
(2, 2)
b (а, 4)
c (d, 2)
z (с, 2)
d
(а, 4)
a (-, ∞)
(6, 4)
(3, 3)
(5, 5)
(7, 3)
(2, 2)
(2, 2)
b (а, 4)
c (-, -)
(
)
d
a (-,
∞
)
(6, 4)
(3, 3)
(5, 5)
(7, 3)
(2, 2)

Страницы