Лабораторная работа (стр. 20 ) | Авторская платформа Pandia.ru

Пусть исходный поток будет нулевой

Пометим узел s знаком (+).

Пометим ребра 01, 13, 36, а, следовательно, узлы 0, 1, 3, 6 знаком (+). Направим по найденному маршруту поток интенсивностью:

Маршрут для потока f1(x, y)

1. Пометим знаком (+) узел 0.

2. Пометим ребра 03, 35, 56, а, следовательно, узлы 0, 3, 5, 6 знаком (+) и направим по маршруту поток интенсивностью

Полученный поток f2(x, y) содержит по крайней мере одну насыщенную дугу на любом маршруте из 0 в 6, то есть является «полным» потоком. Интенсивность найденного суммарного потока равна 5.

3) Попробуем улучшить этот поток.

1. Пометим знаком (+) узел 0.

2. Пометим знаком (+) ненасыщенные дуги 04 и 45. Так как из вершины 5 выходит насыщенная дуга 56, пометим знаком (–) ненулевой поток 35 (узел 3). Так как из вершины 3 выходит насыщенная дуга 36, пометим знаком (–) ненулевой поток 13 (узел 1). Пометим знаком (+) ненасыщенные дуги 12 и 26 (узлы 2 и 6).

3. На вновь открытом маршруте +0,4 +4,5 –3,5 –1,3 +1,2 +2,6 вычислим приращение "полного" потока:

Интенсивность суммарного потока равна 7.

1. Пометим знаком(+) узел 0.

2. Пометим ребро 03 (узел 3) символом (+). Так как из вершины 3 выходит насыщенный поток 36, пометим не нулевой поток 13 (узел 1) знаком (–). Пометим знаком (+) ненасыщенные дуги 12 и 26 (узлы 2 и 6).

3. На вновь открытом маршруте +0,3 –1,3 +1,2 +2,6 вычислим приращение «полного» потока.

НЕ нашли? Не то? Что вы ищете?

Интенсивность полного потока равна 8.

5) Пометим знаком (+) узел 0. Пометим ребро 05 (узел 5) символом (+). Так как из вершины 5 выходит насыщенная дуга 56, пометим знаком (–) ненулевой поток 45 (узел 4) и т. д. Получается, что ни одну вершину пометить нельзя. Следовательно, найденный поток является максимальным.

Пример 3. Заданы топология и пропускные способности каналов замкнутой информационной сети. Найти минимальное сечение и максимальный поток для пары источник-адресат.

s = 0, t = 9.

Решение: Пусть исходный поток будет нулевой:

1. Составим таблицу, каждая строка которой помечена парой и пропускной способностью этой дуги c(x, y). Cтолбцы будут содержать потоком f(x, y), приписанные этому ребру.

2. Рассматривая всевозможные пути и выделяя маршруты, содержащие по крайней мере одну насыщенную дугу, получаем «полный» поток.

Таблица 1.

F	c(x, y)	f0(x, y)	f1(x, y)	f2(x, y)	f3(x, y)
0 1	120		0	+	70	+	90		90
0 2	100		0					+	30
0 3	100		0
0 4	100		0
1 5	70		0	+	70		70		70
1 6	30		0
1 7	20		0			+	20
2 5	50		0					+	30
2 6	40		0
2 7	10		0
3 6	20		0
3 7	40		0
3 8	80		0
4 6	20		0
4 7	40		0
4 8	80		0
5 9	100		0	+	70		70	+	100
6 9	80		0
7 9	90		0			+	20		20
8 9	150		0

Продолжение таблицы 1.

F	c(x, y)	f8(x, y)	f9(x, y)	f10(x, y)
0 1	120		90	+	110	+	120	–
0 2	100		80		80		80	+
0 3	100		100		100		100
0 4	100		100		100		100
1 5	70		70		70		70	-
1 6	30			+	20	+	30
1 7	20		20		20		20
2 5	50		30		30		30	+
2 6	40		40		40		40
2 7	10		10		10		10
3 6	20		20	–
3 7	40		10	+	30		30
3 8	80		70		70		70
4 6	20		20		20	-	10
4 7	40					+	10
4 8	80		80		80		80
5 9	100		100		100		100
6 9	80		80		80		80
7 9	90		40	+	60	+	70
8 9	150		150		150		150