Практическое занятие № 6 "Нахождение кратчайшего остова графа"

ИНСТРУКЦИОННАЯ КАРТА

на выполнение практического занятия № 6

по МДК.01.02 Математический аппарат для построения компьютерных сетей (тема 1. Теория графов)

Тема занятия: Нахождение кратчайшего остова графа.

Цель проведения занятия: изучить и отработать навыки в применении алгоритма Краскала;
закрепить навыки моделирования графов в графической среде Kraskal.

После выполнения работы студент должен

знать: понятия дерева, остовного дерева графа, алгоритм Краскала;

уметь: находить кратчайший остов графа.

Материально-техническое оснащение рабочего места: инструкционные карты, конспект.

Инструктаж по технике безопасности

Рекомендованная литература:

1. Спирина М.С., Дискретная математика: Учебник для студ. Учреждений сред. проф. образования / М.С.Спирина, П.А.Спирин. –М.: Издательский центр «Академия», 2004. –368 с.

2. Александров А. В. и др. Прикладные алгоритмы на графах. Учебное пособие, ВлГУ, 2005

3. Харари Фрэнк. Теория графов / Харари Фрэнк ; Пер. с англ. В.П.Козырева; Под ред. Г.П.Гаврилова. - 4-е изд. - М. : URSS : Либроком, 2009. - 296 с

4. Битюцкий В. П. Электронный учебник: Дискретная математика / http://ait.ustu.ru/uploaded/materialy-po-disciplinam/discret-mathematics/el_ucheb/index.htm

5. Справочные данные по математике: Элементы теории графов. [Электронный ресурс]. – Режим доступа: http://book.itep.ru/10/grap1021.htm, свободный. – Загл. с экрана.

Содержание и порядок выполнения задания

Задание 1. Найти кратчайший остов графа с помощью алгоритма Краскала

Задание 2. Для графа из практической работы № 1 задана матрица весов

1. записать список ребер, упорядочив его по возрастанию их весов

2. Найти кратчайший остов графа с помощью алгоритма Краскала

3. построить полученный остов

4. используя программное обеспечение Kraskal, проверить найденный остов.

Вопросы для самоконтроля:

1. Дайте определение дерева.

2. Дайте определение ориентированного дерева.

3. Какое дерево называется остовым?

4. Дайте определение минимального остова графа.

5. В чем смысл алгоритма Краскала?

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

Порядок выполнения работы:

1. Изучить инструкцию к практической работе.

2. Выполнить задание.

3. Оформить отчет.

Содержание отчета о занятии:

1. Тема.

2. Цель.

4. Практическое задание.

5. Ответ на 1 контрольный вопрос (по указанию преподавателя).

Инструкционная карта составлена преподавателем: Шнарева Г.В.

	1 2 3 4 5 6 1   10 2 5   8 2 10   3     11 3 2 3   4 6 4 4 5   4     7 5     6     6 6 8 11 4 7 6		1 2 3 4 5 6 1   1   1   1 2 1   1   1   3   1   1   1 4 1   1   1   5   1   1   1 6 1   1   1		1 2 3 4 5 6 1   1 1   1 1 2  1   1 1   1 3  1 1    1 1   4   1  1      1 5  1   1      1 6  1  1    1  1
	1 2 3 4 5 6 1   1 1     1 2 1   1 1 1   3 1 1     1 1 4   1     1   5   1 1 1   1 6 1   1   1		1 2 3 4 5 6 1   1 1     1 2  1   1   1   3 1   1   1   1 4      1   1   5   1     1   1 6 1    1  1		1 2 3 4 5 6 1   1 1 1     2 1   1 1   1 3  1 1   1 1 1 4  1  1  1   1 1 5      1 1    1 6    1  1  1 1
	1 2 3 4 5 6 1   1   1 1   2  1   1   1   3    1   1 1 1 4  1    1   1 1 5  1 1   1  1   1 6     1   1  1		1 2 3 4 5 6 1   1 1   1   2 1   1 1 1   3 1 1     1 1 4   1     1 1 5 1 1 1 1   1 6     1 1 1		1 2 3 4 5 6 1   1   1 1 1 2 1   1 1 1   3   1   1 1 1 4 1 1 1   1   5 1 1 1 1     6 1   1
	1 2 3 4 5 6 1   1   1 1   2 1   1   1 1 3   1   1     4 1   1     1 5 1 1       1 6   1   1 1		1 2 3 4 5 6 1   1   1   1 2 1   1 1 1 1 3    1   1 1 1 4 1   1 1      1 5   1  1      1 6 1  1  1 1   1		1 2 3 4 5 6 1   1 1 1   1 2 1   1       3 1 1   1 1 1 4 1   1   1 1 5     1 1   1 6 1   1 1 1
	1 2 3 4 5 6 1   1 1 1 1   2  1       1   3  1     1 1 1 4  1    1   1 1 5 1  1  1  1    1 6     1 1  1		1 2 3 4 5 6 1   1 1   1 1 2  1   1 1   1 3  1 1    1 1   4   1  1      1 5  1   1      1 6  1  1    1  1		1 2 3 4 5 6 1   1   1 1   2 1   1     1 3   1   1 1   4 1   1     1 5 1   1     1 6   1   1 1
	1 2 3 4 5 6 1   1 1 1     2 1   1 1   1 3  1 1   1 1 1 4  1  1  1   1 1 5      1 1    1 6    1  1  1 1		1 2 3 4 5 6 1   1   1 1 1 2 1   1 1 1   3   1   1 1 1 4 1 1 1   1   5 1 1 1 1     6 1   1		1 2 3 4 5 6 1   1   1 1 1 2 1   1 1     3   1   1 1   4 1 1 1   1 1 5 1   1 1     6 1     1
	1 2 3 4 5 6 1   1 1 1   1 2 1   1       3 1 1   1 1 1 4 1   1   1 1 5     1 1   1 6 1   1 1 1		1 2 3 4 5 6 1   1   1 1   2 1   1     1 3   1   1 1   4 1   1     1 5 1   1     1 6   1   1 1		1 2 3 4 5 6 1   1 1 1   1 2 1   1     1 3 1 1   1 1 1 4 1   1     1 5     1     1 6 1 1 1 1 1
	1 2 3 4 5 6 1   1   1 1 1 2 1   1 1     3   1   1 1   4 1 1 1   1 1 5 1   1 1     6 1     1		1 2 3 4 5 6 1   1 1 1   1 2 1   1     1 3 1 1   1 1 1 4 1   1     1 5     1     1 6 1 1 1 1 1		1 2 3 4 5 6 1   1   1   1 2 1   1   1   3   1   1   1 4 1   1   1   5   1   1   1 6 1   1   1
	1 2 3 4 5 6 1   1   1   1 2 1   1   1   3   1   1   1 4 1   1   1   5   1   1   1 6 1   1   1		1 2 3 4 5 6 1   1 1     1 2 1   1 1 1   3 1 1     1 1 4   1     1   5   1 1 1   1 6 1   1   1		1 2 3 4 5 6 1   1 1     1 2 1   1 1 1   3 1 1     1 1 4   1     1   5   1 1 1   1 6 1   1   1
	1 2 3 4 5 6 1   1 1     1 2  1   1   1   3 1   1   1   1 4      1   1   5   1     1   1 6 1    1  1		1 2 3 4 5 6 1   1   1 1   2  1   1   1   3    1   1 1 1 4  1    1   1 1 5  1 1   1  1   1 6     1   1  1		1 2 3 4 5 6 1   1 1     1 2  1   1   1   3 1   1   1   1 4      1   1   5   1     1   1 6 1    1  1
	1 2 3 4 5 6 1   1 1   1   2 1   1 1 1   3 1 1     1 1 4   1     1 1 5 1 1 1 1   1 6     1 1 1		1 2 3 4 5 6 1   1   1 1   2 1   1   1 1 3   1   1     4 1   1     1 5 1 1       1 6   1   1 1		1 2 3 4 5 6 1   1   1 1   2  1   1   1   3    1   1 1 1 4  1    1   1 1 5  1 1   1  1   1 6     1   1  1