Лабораторное задание
Для проведения лабораторной работы необходимо выполнить следующие действия.
1. Изучить основные понятия теории графов
Путь к файлу: D:\ИПОВС\АиСД\OSTOV\Теория графов
2. Вызвать систему Ostov1, включающую в себя изучение методов Крускала и Прима.
Путь к файлу: D:\ИПОВС\АиСД\OSTOV\Ostov1
Система работает в диалоговом режиме с использованием “меню”. Вся необходимая информация во время работы системы отображается на экране дисплея и не требует специальных пояснений.
Для графов, содержащих 10 и 12 вершин построить остовные деревья двумя методами.
По окончании работы выставляется оценка.
3. Вызвать системы Ostov2 и Ostov3 для исследования методов Крускала и Прима.
Путь к файлу: D:\ИПОВС\АиСД\OSTOV\Ostov2 (Ostov3 )
Результаты записать в тетрадь.
Требования к отчёту
Отчёт должен содержать:
конспект лабораторной работы;
примеры работы методов Крускала и Прима;
результаты выполнения работы;
выводы по работе;
Контрольные вопросы
Что понимается под остовным деревом?
Каковы особенности методов Крускала и Прима?
3. В чём состоит методика анализа сложности алгоритмов построения остовного
дерева графа?
Литература
Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.
Д.Кнут Искусство программирования , том 1. Основные алгоритмы. Уч . пос. М.:Изд. Дом " Вильямс ", 2000.
Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.
Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учеб. пособие. М : Финансы и статистика, 2004.
Задание : Построить остовное дерево графа методами Крускала и Прима.
1
;
24
2
;
23
3
;
22
4
;
21
5
;
20
6; 19
7
;
18
8; 17
9
;
16
1
0;
15; 25
1
1;
14
12; 13
Решить задачи
Задача 1. Дана карта дорог между городами, где указана длина каждой дороги (данные не совпадают с настоящими). Соединить все города автострадой минимальной длины, т.е. построить остовное дерево методами Прима и Крускала.
|
Задача 2. Задать веса ребрам и построить остовное дерево графа |
|
|
Задача 3. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля-Меркурий, Плутон-Венера, Земля-Плутон, Плутон-Меркурий, Меркурий-Венера, Уран-Нептун, Нептун-Сатурн, Сатурн-Юпитер, Юпитер-Марс и Марс-Уран. Можно ли добраться с Земли до Марса?
Задача 4. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
Задача 5. Какое максимальное число висячих вершин может иметь дерево, обладающее 9 вершинами? Какое минимальное число висячих вершин оно может иметь? Сделайте рисунки таких деревьев.
Задача 6. В доме отдыха Вишкиль 57 корпусов. Электрик решил соединить телефонными проводами каждый корпус ровно с пятью другими. Сможет ли он это сделать?
Задача 7. У предприятия имеется 4 завода и 9 торговых точек. Каждый завод должен поставлять свою продукцию во все торговые точки. Сколько всего дорог необходимо проложить, чтобы осуществить задуманное? Определите вид полученного графа.
Задача 8. На участке 3 дома и 3 колодца. От каждого дома к каждому колодцу ведет тропинка. Когда владельцы домов поссорились, они задумали проложить дорогу от каждого дома к каждому колодцу так, чтобы не встречаться на пути к колодцам. Может ли осуществиться их намерение?
Задача 9. Муравей забрался в банку из-под сахара, имеющую форму куба. Сможет ли он последовательно обойти все рёбра куба, не проходя дважды по одному ребру?
Задача 10. На занятии 20 школьников решили каждый по 6 задач, причём каждая задача была решена ровно двумя школьниками. Можно ли организовать разбор всех задач таким образом, чтобы каждый школьник рассказал ровно по 3 задачи.