Решение. 2 страница

Четвертый шаг: проделываем все операции для вершины 3:

.

;

.

Метки для остальных вершин оставляем прежними. Метка для вершины 6 уменьшилась. Записываем меньшую.

Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 4.

.

	0^*
		6^*
			7^*
				7^*

Пятый шаг: проделываем все операции для вершины 4:

.

;

.

Для вершины 2 расстояние не рассчитываем, т.к. она уже получила постоянную метку. Метки для остальных вершин оставляем прежними.

Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 5.

.

	0^*
		6^*
			7^*
				7^*
					7^*

Шестой шаг: проделываем все операции для вершины 5:

.

;

;

;

;

Для вершины 4 расстояние не рассчитываем, т.к. она уже получила постоянную метку. Метки для остальных вершин оставляем прежними. Метки для вершин 6, 7, 8 уменьшились. Записываем меньшие.

Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 6.

.

	0^*
		6^*
			7^*
				7^*
					7^*
						9^*

Седьмой шаг: проделываем все операции для вершины 6:

.

;

Метки для остальных вершин оставляем прежними.

Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 7.

.

	0^*
		6^*
			7^*
				7^*
					7^*
						9^*
							9^*

Восьмой шаг: проделываем все операции для вершины 7:

.

;

Метки для остальных вершин оставляем прежними.

Из всех меток выбираем минимальную, записываем вершину с минимальной меткой в следующий столбец. В данном случае это вершина 8.

.

Для вершины 9 метка на девятом шаге не меняется, поэтому все результаты записываем в таблицу.

	0^*
		6^*
			7^*
				7^*
					7^*
						9^*
							9^*
								11^*
									12^*

Таким образом, минимальные расстояния от вершины 1 ко всем вершинам графа равны:

Задание 14. Найти максимальный поток в транспортной сети, изображенной на рисунке _____.

Рисунок ____.

Решение. Длянахождения максимального потока воспользуемся алгоритмом Форда-Фалкерсона. Найдем суммарную пропускную способность дуг, выходящих из истока (вершина 1) и суммарную пропускную способность дуг, входящих в сток (вершина 14).

;

.

Значит, максимальный поток в этой сети не может превосходить 31.

Далее разбиваем сеть на простые непересекающиеся цепи (произвольным образом). В данном случае удобно сделать это следующим образом:

1 – (1, 2, 6, 10, 14);

2 – (1, 3, 7, 11, 14);

3 – (1, 4, 8, 12, 14);

4 – (1, 5, 9, 13, 14).

Для каждой из цепей находим максимальный поток, исходя из пропускных способностей дуг: например, в первой цепи – (1, 2, 6, 10, 14) – минимальная пропускная способность у дуги (2,6) – 6, поэтому поток по этой дуге не может превышать 6-ти.

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

На первой итерации получаем суммарный поток: 6+5+6+4=21.

На следующих итерациях будем пытаться увеличить величину потока.

Рисунок ____ – первая итерация.

Для этого выбираем другие цепи, в которых нет насыщенных дуг.

На рисунках _______ изображены последующие итерации. (Над дугой рядом с пропускными способностями дуг через «;» обозначаем новое значение потока).

Вторая итерация: выбираем цепь, по которой можно увеличить поток: (1, 2, 3, 6, 10, 14). Поток можно увеличить на 1 (т.к. пропускная способность дуги (6, 10) равна 7).

Рисунок ____ – вторая итерация.

На второй итерации поток увеличился на 1, и стал равен 22.

Третья итерация: выбираем цепь (1, 3, 8, 7, 10, 14). По этой дуге мы можем пропустить поток величиной 2 (т.к. пропускная способность дуги (3,8) равна 2). Получаем суммарный поток, равный 22+2=24. На рис. ____ изображена сеть с потоком, равным 24.

Рисунок ____ – третья итерация.

Четвертая итерация: выбираем цепь (1, 4, 9, 13, 14). По этой дуге мы можем пропустить поток величиной 1 (т.к. пропускная способность дуги (9, 13) равна 5). Получаем суммарный поток, равный 24+1=25. На рис. ____ изображена сеть с потоком, равным 25.

Рисунок ____ – четвертая итерация.

Задание 9. Доказать справедливость соотношения .

Дата добавления: 2014-11-20