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

UptoLike

ВУЗ: 

КФУ | Казань

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

Рубрика: 

§ 2. Нахождение максимального потока: алгоритм и теорема 55
Рис. 4
ну a
1
. В самом деле, из a
1
в a
2
ведет дуга, причем f(a
1
, a
2
) = 4 > 0,
следовательно, вершина a
1
получает метку (a
−
2
, 1), где 1 = min(4, 1).
Теперь вершине a
4
приписываем метку (a
+
1
, 1), а стоку t — метку
(a
+
4
, 1).
Рис. 5
Изменение потока. Положив f(a
4
, t) = 0 + 1 = 1, f(a
1
, a
4
) =
0 + 1 = 1, f(a
1
, a
2
) = 4 − 1 = 3, f(a
3
, a
2
) = 1 + 1 = 2 и f(s, a
3
) =
1 + 1 = 2, получаем поток величины 6 (см. рис. 6).
Помечивание вершин. Приписав источнику s метку (−, ∞), а вер-
шине a
3
— метку (s
+
, 1), убеждаемся в том, что дальнейшее помечива-
ние невозможно. Таким образом, сток остался непомеченным. Работа
алгоритма закончена, поток максимальной величины 6 построен. За-
метим, что пропускная способность разреза (X,
¯
X), где X = {s, a
3
},
тоже равна 6 и является минимальной согласно теореме 1.
Интуиция, возможно, подсказывает читателю, что должна быть
связь между потоками в сети и путями из источника в сток. Действи-
тельно, справедливо следующее
Предложение 1. Если в сети существует (s, t)-путь, то в ней
имеется поток положительной величины. Обратно, если в сети
§ 2. Нахождение максимального потока: алгоритм и теорема                 55




                                   Рис. 4

ну a1 . В самом деле, из a1 в a2 ведет дуга, причем f (a1 , a2 ) = 4 > 0,
следовательно, вершина a1 получает метку (a−   2 , 1), где 1 = min(4, 1).
                                             +
Теперь вершине a4 приписываем метку (a1 , 1), а стоку t — метку
(a+
  4 , 1).




                                   Рис. 5

    Изменение потока. Положив f (a4 , t) = 0 + 1 = 1, f (a1 , a4 ) =
0 + 1 = 1, f (a1 , a2 ) = 4 − 1 = 3, f (a3 , a2 ) = 1 + 1 = 2 и f (s, a3 ) =
1 + 1 = 2, получаем поток величины 6 (см. рис. 6).
    Помечивание вершин. Приписав источнику s метку (−, ∞), а вер-
шине a3 — метку (s+ , 1), убеждаемся в том, что дальнейшее помечива-
ние невозможно. Таким образом, сток остался непомеченным. Работа
алгоритма закончена, поток максимальной величины 6 построен. За-
метим, что пропускная способность разреза (X, X̄), где X = {s, a3 },
тоже равна 6 и является минимальной согласно теореме 1.
    Интуиция, возможно, подсказывает читателю, что должна быть
связь между потоками в сети и путями из источника в сток. Действи-
тельно, справедливо следующее
   Предложение 1. Если в сети существует (s, t)-путь, то в ней
имеется поток положительной величины. Обратно, если в сети

Страницы