Практическая работа № 5 пропускная способность сети

Цель работы: Изучение теоретических и практических приёмов определения пропускной способности сети.

Пропускная способность сети определяется суммой максимальных потоков в двух направлениях. Таким образом, задача сводится к определению максимального потока от истока s к стоку t.

Алгоритм нахождения максимального потока

Рассмотрим задачу определения максимального потока между двумя выделенными узлами связной сети. Каждая дуга сети обладает пропускными способностями в обоих направлениях, которые определяют максимальное количество потока, проходящего по данной дуге. Ориентированная (односторонняя) дуга соответствует нулевой пропускной способности в запрещенном направлении.

Пропускные способности с_ij сети можно представить в матричной форме. Для определения максимального потока из истока s в сток t используются следующие шаги.

Шаг 1. Найти цепь, соединяющую s с t, по которой поток принимает положительное значение в направлении s→t. Если такой цепи не существует, перейти к шагу 3. В противном случае перейти к шагу 2.

Шаг 2. Пусть c^-_ij — пропускные способности дуг цепи (s, t) в направлении s→t(t→s) и =min{c^-_ij}>0

Матрицу пропускных способностей C_ij можно изменить следующим образом:

(а) вычесть  из всех c^-_ij;

(б) прибавить  ко всем c⁺_ij. При этом общая пропускная способность сети не изменится. Перейти к шагу 1.

Операция (а) дает возможность использовать остатки пропускных способностей дуг выбранной цепи в направлении s→t. Операция (б) восстанавливает исходные пропускные способности сети, поскольку уменьшение пропускной способности дуги в одном направлении можно рассматривать как увеличение ее пропускной способности в противоположном направлении.

Шаг 3. Найти максимальный поток в сети. Пусть С=||с_ij|| — исходная матрица пропускных способностей, и пусть С*=||с^*_ij|| — последняя матрица, получившаяся в результате модификации исходной матрицы (шаги 1 и 2).

Оптимальный поток X=||x_ij|| в дугах задается как

.

Максимальный поток из s в t равен

.

Тестовый пример

Рассмотрим сеть с указанными на рис.5.1 пропускными способностями.

Рис.5.1. Граф сети

Соответствующая матрица пропускных способностей С приведена в табл. 5.1. В качестве исходной цепи можно выбрать s→1→4→t.

Таким образом, ячейки (s, 1), (1, 4) и (4, t) помечаются знаком (-), а ячейки (1, s), (4, 1) и (t, 4) - знаком (+). Для данной цепи максимальный поток определяется как =min{c_s1, c₁₄, c_4t=min{10, 5,13=5.

Матрица С в табл. 5.1 корректируется путем вычитания =5 из всех элементов, помеченных знаком (-), и сложения со всеми элементами, имеющими знак (+). Результаты приведены в табл. 5.2.

Табл. 5.1 .Цепь (s→1→4→t),=5 Табл. 5.2. Цепь s→3→2→t), =10

	s	1	2	3	4	t
s		10	3	14	4
1	5		5	9	5
2	5	6		15		10
3	12	7	10		7	2
4	3	9		8		13
t			3	4	5

	s	1	2	3	4	t
s		5	3	14	4
1	10		5	9	0
2	5	6		15		10
3	12	7	10		7	2
4	3	14		8		8
t			3	4	10

Результаты последующих итераций приведены в табл. 5.3-5.6.

Табл. 5.3. =5 Табл. 5.4. =3 Цепь (s→1→3→4→t) Цепь (s→1→3→4→t)

	s	1	2	3	4	t
s		5	3	4	4
1	10		5	9	0
2	5	6		25		0
3	22	7	0		7	2
4	3	14		8		8
t			13	4	10

	s	1	2	3	4	t
s		0	3	4	4
1	15		5	4	0
2	5	6		25		0
3	22	12	0		2	2
4	3	14		13		3
t			13	4	15

Табл.5.5. Цепь (s→3→t), =2 Табл. 5.6. Нет стока

					s			1			2				3			4		t
			s					0			3				2			1
			1		15						5				4			0
			2		5			6							25					0
			3		24			12			0							2		0
			4		6			14							13					0
			t								13				4			20

	s	1	2	3	4	t
s		0	3	4	1
1	15		5	4	0
2	5	6		25		0
3	22	12	0		2	2
4	6	14		13		0
t			13	4	18

Из табл. 5.6 следует, что между s и t нельзя построить цепей с положительным потоком, поскольку все элементы в столбце t равны нулю. Таким образом, табл. 5.6 дает матрицу C^*. В табл. 5.1 (матрица С) и табл.5.6 (матрица С^*) приведены данные, характеризующие оптимальный поток, которые используются для вычисления Х=C-C* с заменой отрицательных величин нулями.

В табл. 5.7 дана матрица X, а табл. 5.8 приведена рядом для удобства сравнений исходной матрицы и матрицы потоков.

Таблица 5.7. Таблица 5.8.

Матрица оптимального потока Исходная матрица

	s	1	2	3	4	t
s		10		12	3
1				5	5
2						10
3			10		5	2
4						13
t

	s	1	2	3	4	t
s		10	3	14	4
1	5		5	9	5
2	5	6		15		10
3	12	7	10		7	2
4	3	9		8		13
t			3	4	5

.

Из табл. 5.8 видно, что z=10+12+3=10+2+13=25. Сумма всех (=5+10+5+3+2=25) также дает максимальный поток. В табл.5.8 показана исходная матрица с отметкой узлов, через которые происходит сток.