Задачи по дискретной математике, математической логике и теории алгоритмов (стр. 3 )

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 5.4

по теме : задача о почтальоне (2 часа).

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

Л А Б О Р А Т О Р Н А Я Р А Б О Т А N 5.5

по теме : автоматизированное построение покрывающего дерева для графа

(4 часа).

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

Вариант 1 Вариант 2

	1	2	3	4	5	6	7	1	2	3	4	5	6	7
1	-	-	5	7	-	8	-	-	3	2	3	-	-	-
2		-	-	3	2	-	-		-	-	5	3	-	-
3			-	2	-	2	-			-	6	2	-	-
4				-	-	6	-				-	-	3	2
5					-	4	3					-	7	8
6						-	4						-	5
7							-							-

Вариант 3 Вариант 4

	1	2	3	4	5	6	7	1	2	3	4	5	6	7
1	-	-	5	8	-	6	-	-	1	3	2	-	-	-
2		-	-	6	2	-	9		-	-	5	3	-	-
3			-	2	7	2	-			-	9	2	-	-
4				-	-	6	-				-	-	5	2
5					-	4	3					-	7	8
6						-	4						-	5
7							-							-

Вариант 5 Вариант 6