ВУЗ:
Составители:
Рубрика:
Найдем максимальный поток для транспортной сети, показанной на
рис.9.11 (табл. 9.2).
Шаг 1. Метим первую строку меткой (s
+
, 5 – 3) = (s
+
, 2).
Шаг 2. Метим второй столбец меткой (1
+
, min(2; 3 – 2)) = (1
+
, 1).
Шаг 3. От второго столбца помечаются строки 2 и 3. Метка второй
строки: (2
−
, min(1; 3)) = (2
−
, 1). Метка третьей строки: (2
−
, min(1; 1)) = (2
−
,
1).
Шаг 2. От второй строки можно пометить первый столбец меткой
(1
+
, min(1; 3 – 2)) = (1
+
, 1). Но поток на дуге (2, t) равен 2, а ее
пропускная способность равна 3, следовательно, найдена увеличивающая
цепь (рис. 9.12), вдоль которой можно увеличить поток на 1. Определим
вершины этой цепи. Сток метится от первого столбца. Первый столбец
помечен от первой строки, вторая строка помечена от второго столбца,
второй столбец помечен от первой строки, первая
строка помечена от
источника (табл. 9.2).
Таблица 9.2
(2
+
, 1) (1
+
,1)
(s
+
, 2)
(2
−
, 1)
(2
−
, 1)
Отметим знаком «+» потоки на прямых дугах и знаком «–» потоки на
обратных дугах найденной увеличивающей цепи. Прибавим к потокам,
отмеченным знаком плюс, и вычтем из потоков, отмеченных знаком
минус, единицу (рис. 9.12). Величина потока в транспортной сети
увеличится на 1.
Попытаемся снова увеличить поток (табл. 9.3).
Шаг 1. Первая строка получает метку (s
+
, 1).
Шаг 2. От первой строки нельзя пометить ни один столбец, так как все
дуги, выходящие из первой вершины множества V
a
, насыщены.
Следовательно, величина максимального потока равна
j
i
1 3
2+
2 6
6
3 6
4
1 5
3+
3
2+
1
1
2 5
5
3
2+
4
3
−
3 2
2
1
1
1
1
4 2
2
3 2
2
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
