Метод указания к лаб работам ИСО, страница 14

На вновь открытом маршруте +0.4+4.53.51.3+1.2+2.6 вычислим приращение "полного" потока равен 1.

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

Β = {0,4,5} и Β= {1,2,3,6}.

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

s = 0, t = 6.

Р ешение:

Сетевая модель задачи о максимальном потоке (пример 2)

F	c(x,y)	f0(x,y)		f1(x,y)		f2(x,y)		f3(x,y)
0 1	3	+	3		3		3		3
0 3	3			+	2		2	+	3
0 4	2					+	2		2
0 5	7
1 2	3					+	2	+	3
1 3	7	+	3		3	–	1	–
2 6	5					+	2	+	3
3 5	7			+	2	–
3 6	3	+	3		3		3		3
4 5	2					+	2		2
5 6	2			+	2		2		2

1)

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

.

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

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

2. Направим по найденному маршруту поток интенсивностью:

.

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

2)

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

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

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

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

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.

4)

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

2

2

3

2

2

2

2

3

1

Частичное решение задачи о максимальном потоке (пример 2)

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

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

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

1. Пометим знаком (+) узел 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

1 итерация.