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

Текст из файла (страница 13)

j	1	2	3	4
Yj	4	2	1	0
Sj	2/3	3	4	Ост

Пример 2:

						6
							3		3
						7
					0	7	4	2	4
					1	2	3	4	5
			0	1
6		7	7	2	7		3
	3		4	3	4	3		1
			2	4	2		1
	3		4	5	4			1
					*	1	1	1	1
						1/3
							4		4
						3

j = 1

j = 2, j =3

j = 4

_{j = 3 (так как произошла замена y3)}

j = 5, j = 1, j = 2, j = 3, j = 4, j = 5  Останов

J	1	2	3	4	5
Yj	0	6	3	2	3
Sj	*	3	4	1	4

Пример 3:

											8
					6	3		3	6	7	9
				0	7	4	2	4	7	8
			i \ j	1	2	3	4	5	6	7	8
		0	1
	6	7	2	7		3				1
	3	4	3	4	3		1
		2	4	2		1		1
	3	4	5	4			1
	6	7	6				5	3
	7	8	7		1	5			3
8	9		8					6	4	1
				1	2	3	4	5	6	7	8
				*	1	1	1	1		2	5
					3	4		4	4		7
									5

j	1	2	3	4	5	6	7	8
Yj	0	6	3	2	3	6	7	8
Sj	*	3	4	1	4	5	2	7

j = 1

j = 2

j = 3, j = 4

j = 5

j = 1, j = 2, j = 3

j = 4, j = 5, j = 6, j = 7, j = 1, j = 2

j = 3, j = 4, j = 5, j = 6, j = 7

j = 1, j = 2, j = 3, j = 4, j = 5, j = 6, j = 7  Останов

Лабораторная работа № 8 (4 часа)

Задача о максимальном потоке

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

Согласно теореме Форда и Фалкерсона максимально возможное значение суммарного потока равно пропускной способности минимального сечения между источником и адресатом.

Примем следующие обозначения:

c (x, y) – пропускная способность дуги x, y;

f_i (x, y) – поток, приписанный дуге x, y , на i-том шаге алгоритма;

F – множество ребер сети;

s – узел-источник сети;

t – узел-адресат сети;

x, y – промежуточные узлы сети.

Алгоритм применим для любого допустимого потока, например, пусть .

1. Пометить узел s символом (+).

2. Если существует непомеченный узел, в который ведет ненасыщенная дуга, то есть y: , иначе перейти к пункту 5.

3. Если y = t, направить по найденному маршруту s – t дополнительный поток

и перейти к пункту 1.

1. Если y ≠ t, выполнить пункт 2.

2. Если не существует дуги c (x, y) > f (x, y), выбрать не помеченный узел y: , пометить узел y символом (–) и выполнить пункт 2.

3. Если для любой помеченной вершины справедливо, что все смежные вершины пометить нельзя, значить найден максимальный поток.

Β – множество помеченных вершин, – дополнение Β.

Пример 1. Найти максимальный поток и минимальное сечение для графа, пропускная способность каждого ребра равна 1.

Исток (отправитель)

Сток (адресат)

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

3 – минимальное сечение

3 – максимальный поток

Решение.

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

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

Пометим ребра 01, 13, 36 знаком + и направим по найденному маршруту поток 1.

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

П ометим ребра 03, 35, 56 знаком (+) и направим по найденному маршруту поток 1.

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

Полученный поток f₂ (x, y) содержит по крайней мере одну насыщенную дугу – то есть является "полным" потоком.

Попробуем улучшить полученный поток:

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

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

Характеристики

Список файлов книги