Дискретная математика: графы и автоматы. Альпин Ю.А - 54 стр.

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

54 Глава 3. Задача о максимальном потоке в сети
пометить вершину a
2
: она получает метку (a
+
1
, 4), где 4 = min(6, 4).
Аналогично, приписываем вершине a
4
метку (a
+
1
, 4). Этим заверше-
на обработка вершины a
1
. Переходя к обработке помеченной вер-
шины a
2
, замечаем, что из неё можно пометить сток t, так как
c(a
2
, t)−f(a
2
, t) = 5−0 = 5 > 0, его метка — (a
+
2
, 4), где 4 = min(5, 4).
Сеть с указанными метками изображена на рис. 3. Поскольку сток по-
лучил метку, переходим к изменению потока.
Рис. 3
Изменение потока. Сток t получил метку (a
+
2
, 4), поэтому меня-
ем f(a
2
, t) = 0 на f(a
2
, t) = 0 + 4 = 4 и переходим к вершине
a
2
. Её метка — (a
+
1
, 4), значит, f(a
1
, a
2
) = 0 следует заменить на
f(a
1
, a
2
) = 0 + 4 = 4. Наконец, для вершины a
1
с меткой (s
+
, 4) ме-
няем f(s, a
1
) = 0 на f(s, a
1
) = 0 + 4 = 4. Стираем все метки. Теперь
величина потока равна 4.
Помечивание вершин. Cнова приписываем s метку (−, ∞). У вер-
шины s есть две смежных вершины — a
1
и a
3
. Вершину a
1
из s по-
метить нельзя, так как c(s, a
1
)−f(s, a
1
) = 4 − 4 = 0, а a
3
— мож-
но, поскольку c(s, a
3
)−f(s, a
3
) = 3 − 0 = 3 > 0. Следовательно, a
3
получает метку (s
+
, 3). Вершина s обработана, переходим к поме-
ченной вершине a
3
. С a
3
смежна одна непомеченная вершина — a
2
.
Из a
3
в a
2
ведёт дуга, причём c(a
3
, a
2
)−f(a
3
, a
2
) = 2−0=2>0, по-
этому a
2
получает метку (a
+
3
, 2), где 2 = min(2, 3). Обработка вер-
шины a
3
завершена, переходим к помеченной вершине a
2
. Поскольку
c(a
2
, t)−f(a
2
, t) = 5−4=1>0 стоку t приписываем метку (a
+
2
, 1), где
1 = min(1, 2). Сеть с новыми метками изображена на рис. 4.
Изменение потока. Двигаясь по меткам вершин от t к s, устанав-
ливаем f(a
2
, t) = 4 + 1 = 5, f(a
3
, a
2
) = 0 + 1 = 1, f(s, a
3
) = 0 + 1 = 1.
Стираем метки. Величина нового потока равна 5.
Помечивание вершин. Приписываем s метку (−, ∞), вершине a
3
—
метку (s
+
, 2), вершине a
2
— метку (a
+
3
, 1). Сток из a
2
пометить нельзя,
поскольку c(a
2
, t) − f(a
2
, t) = 5 − 5 = 0 , но можно пометить верши-
54                                Глава 3. Задача о максимальном потоке в сети


пометить вершину a2 : она получает метку (a+     1 , 4), где 4 = min(6, 4).
Аналогично, приписываем вершине a4 метку (a+         1 , 4). Этим заверше-
на обработка вершины a1 . Переходя к обработке помеченной вер-
шины a2 , замечаем, что из неё можно пометить сток t, так как
c(a2 , t)−f (a2 , t) = 5−0 = 5 > 0, его метка — (a+
                                                  2 , 4), где 4 = min(5, 4).
Сеть с указанными метками изображена на рис. 3. Поскольку сток по-
лучил метку, переходим к изменению потока.




                                      Рис. 3

     Изменение потока. Сток t получил метку (a+            2 , 4), поэтому меня-
ем f (a2 , t) = 0 на f (a2 , t) = 0 + 4 = 4 и переходим к вершине
a2 . Её метка — (a+    1 , 4), значит, f (a1 , a2 ) = 0 следует заменить на
f (a1 , a2 ) = 0 + 4 = 4. Наконец, для вершины a1 с меткой (s+ , 4) ме-
няем f (s, a1 ) = 0 на f (s, a1 ) = 0 + 4 = 4. Стираем все метки. Теперь
величина потока равна 4.
     Помечивание вершин. Cнова приписываем s метку (−, ∞). У вер-
шины s есть две смежных вершины — a1 и a3 . Вершину a1 из s по-
метить нельзя, так как c(s, a1 )−f (s, a1 ) = 4 − 4 = 0, а a3 — мож-
но, поскольку c(s, a3 )−f (s, a3 ) = 3 − 0 = 3 > 0. Следовательно, a3
получает метку (s+ , 3). Вершина s обработана, переходим к поме-
ченной вершине a3 . С a3 смежна одна непомеченная вершина — a2 .
Из a3 в a2 ведёт дуга, причём c(a3 , a2 )−f (a3 , a2 ) = 2−0=2>0, по-
этому a2 получает метку (a+       3 , 2), где 2 = min(2, 3). Обработка вер-
шины a3 завершена, переходим к помеченной вершине a2 . Поскольку
c(a2 , t)−f (a2 , t) = 5−4=1>0 стоку t приписываем метку (a+            2 , 1), где
1 = min(1, 2). Сеть с новыми метками изображена на рис. 4.
     Изменение потока. Двигаясь по меткам вершин от t к s, устанав-
ливаем f (a2 , t) = 4 + 1 = 5, f (a3 , a2 ) = 0 + 1 = 1, f (s, a3 ) = 0 + 1 = 1.
Стираем метки. Величина нового потока равна 5.
     Помечивание вершин. Приписываем s метку (−, ∞), вершине a3 —
метку (s+ , 2), вершине a2 — метку (a+      3 , 1). Сток из a2 пометить нельзя,
поскольку c(a2 , t) − f (a2 , t) = 5 − 5 = 0, но можно пометить верши-

Страницы