Введение в линейное программирование. Палий И.А. - 70 стр.

UptoLike

ВУЗ: 

СибАДИ | Омск

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

Рубрика: 

Шаг 4. Увеличивающая цепь имеет вид s →V
2
→V
1
→ t; E
t
= 1. На
каждой дуге увеличивающей цепи величина потока возрастает на 1 (рис.
9.7).
Шаг 5. Стираем все пометки и возвращаемся к шагу 1 (рис. 9.8).
Шаг 2. От вершины s можно пометить вершину V
3
меткой (s
+
, 1). От
вершины V
3
по обратной дуге можно пометить вершину V
2
меткой (
−
3
V
,
min(1; 2)) = (
−
3
V
, 1). От вершины V
2
по прямой дуге метится вершина V
1
меткой (V
2
+
, 1), а от вершины V
1
метится сток меткой (V
1
+
, 1) (рис. 9.8).
Рис. 9.6. Расстановка меток по алгоритму Форда-Фалкерсона
Рис. 9.7. Увеличение потока вдоль увеличивающей цепи
Шаг 3. Вершина t получила пометку, следовательно, поток в сети
можно увеличить.
Шаг 4. Увеличивающая цепь имеет вид s → V
3
← V
2
→V
1
→ t. По ней
можно увеличить поток на 1 (рис. 9.9).
Шаг 5. Стираем все пометки и возвращаемся к шагу 1 (рис. 9.10).
Шаг 2. Все дуги, выходящие из источника, насыщены. Ни одной из
вершин нельзя приписать метку. Следовательно, найден максимальный
поток. Множество R помеченных вершин содержит единственную
вершину s, R = {s}. Тогда
R = {V
1
, V
2
, V
3
, t}. Минимальный разрез
∗
),( RR
4(3) + 1 5(0) + 1 6(3) + 1
(V
1
+
, 1) (V
2
+
, 1)
(s
+
, 1) (0,∞)
s V
1
t
V
2
(V
2
+
, 1)
(V
1
+
, 1)
(s
+
, 1)
(s
+
, 1)
(0, ∞)
5
S
t
V
3
V
1
V
2
4(3)
3(3)
1(1)
6(3)
2
3(3)
2(2)
2(1)

Страницы