Курсовая на тему "Кратчайший путь в графах"
Работа оценена на "отлично"!
Наиболее распространенные методы поиска кратчайших расстояний - это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Прима и Краскала.
Цель курсовой работы: изучить алгоритмы Дейкстры, Прима и Краскала для нахождения кратчайших путей в графе.
Задачи работы:
1. Рассмотреть основные понятия и определения;
2. Рассмотреть виды графов;
3. Изучение способов задания графов;
4. Изучение алгоритма Дейкстры Прима и Краскала для нахождения кратчайших путей в графе;
5. Приведение примеров решения задач этими методами.
Данная работа состоит из введения, двух глав, заключения и списка литературы.
ВВЕДЕНИЕ 2
ГЛАВА Ι. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ 3
1.1 ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ 3
1.2 ВИДЫ ГРАФОВ 6
1.3 СПОСОБЫ ЗАДАНИЯ ГРАФОВ 9
ГЛАВА ΙΙ. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ В ВЗВЕШЕННОМ ГРАФЕ 18
2.1 ПОИСК КРАТЧАЙШЕГО ПУТИ В ГРАФЕ С ПОМОЩЬЮ АЛГОРИТМА ДЕЙКСТРЫ 18
2.2 ЗАДАЧА О СОЕДИНЕНИИ ГОРОДОВ (АЛГОРИТМЫ ПРИМА И КРАСКАЛА) 26
ЗАКЛЮЧЕНИЕ 30
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 31
1. Белов В.В. Теория графов / В.В. Белов, Е.М. Воробьев, В.Е. Шабалов. − М. : Высшая школа, 1976. − 392 с.
2. Белоусов А.И. Дискретная математика / А.И. Белоусов, С.Б. Ткачев. − М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. – Вып. XIX. − 744 с.
3. Березина Л.Ю. Графы и их применения / Л.Ю. Березина. − М. : Просвещение, 1979. − 143 с.
4. Галушкина Ю.И. Конспект лекций по дискретной математике / Ю.И. Галушкина, А.Н. Марьямов. − М. : Айрис Пресс, 2007. − 176 с.
5. Горбатов В.А. Дискретная математика. Учебник для студентов втузов / В.А Горбатов, А.В. Горбатов, М.В. Горбатова. – М. : АСТ, Астрель, 2003. – 447 с.
6. Емеличев В.А. Лекции по теории графов / В.А. Емеличев, И.О. Мельников, В.И. Сарванов, Р.И. Тышкевич. − М. : Наука, 1990. − 384 с.
7. Логинов Б.М. Введение в дискретную математику / Б.М. Логинов. − Калуга, 1998. – 423 с.
8. Судоплатов С.В. Элементы дискретной математики / С.В. Судоплатов, Е.В. Овчинникова. − М. : ИНФРА−М, Новосибирск: Изд-во НГТУ, 2002. − 280 с. Яблонский С.В. Введение в дискретную математику / С.В. Яблонский. − М. : Высш. шк., 2001. − 384 с.
