Введение 3
Глава 1. Основные понятия и определения Теории Графов 5
1.1. Понятие графа 5
1.2. Определения и свойства 6
1.3. Маршруты, пути, циклы, расстояния 10
Глава 2. Поиск маршрутов на графе 13
2.1. Алгоритмы и задачи 13
2.2. Поиск в глубину. Задача обхода 14
2.3. Поиск в ширину 17
2.4. Поиск кратчайшего пути 18
2.4.1. Алгоритм Дейкстры 18
2.4.2. Алгоритм Беллмана-Форда 23
2.4.3. Алгоритм Флойда 26
2.5. Деревья. Оптимизация графа 28
Глава 3. Система компьютерной математики Maple 31
3.1. Основные сведения о Maple и пакете GraphTheory 31
3.2. Основные процедуры и начало работы с пакетом GraphTheory 33
3.3. Поиск маршрутов с помощью стандартных процедур Maple 43
3.3. Программирование Maplet 47
Глава 4. Методика применения СКМ Maple при поиске маршрутов на графе ... 49
4.1. Решение задач на нахождение кратчайшего пути в графе 49
4.2. Определение оптимального маршрута 55
4.3. Поиск всевозможных путей между всеми парами вершин на графе 57
Заключение 59
Список использованных литературы

Купить

Теория графов - область дискретной математики, которая применяет геометрический подход к изучению объектов и имеет большое прикладное значение. Долгое время задачи теории графов решались вручную, однако по мере развития компьютерных дисциплин и формализации разных задач из практики, оказалось, что графы — удобный способ описания самых разнообразных связей, причем не только пространственных. Например, для моделирования транспортных маршрутов, молекул, спортивных расписаний и компьютерных сетей.
С появлением компьютеров возникла возможность написания специальных программ на алгоритмических языках. В дальнейшем появились специальные пакеты вычислений, например Maple, позволяющие выполнять аналитически символьные преобразования. Для решения задач, объектами которых являются графы, эти пакеты незаменимы.
Одна из задач, которая может быть решена с помощью графа является задача о нахождении кратчайшего расстояния и заданного маршрута между объектами. Данная тема постоянно развивается благодаря своему широкому применению и использованию как в науке, так и в нашей повседневной жизни. Например, в работе GPS при поиске оптимального маршрута движения и анализе загруженности дорог и прочее. Можно найти множество способов применить данную тему в жизни, что показывает ее актуальность.
Цель дипломной работы рассмотреть основные алгоритмы поиска маршрутов на графе, их реализацию и методическое применение в СКМ Maple.
Задачи выпускной квалификационной работы:
1. Рассмотреть применение основных алгоритмов при поиске маршрутов на графе.
2. Изучить возможности применения пакета Maple - GraphTheory.
3. Перевод научной литературы с английского языка для описания пакета GraphTheory.
4. Разработать программные процедуры СКМ Maple для решения школьных задач для нахождения кратчайшего пути на графе.
Практическая значимость исследования заключается в том, что разработанная программа, наглядно демонстрирующая графическое представление графа, визуализирующего работу алгоритмов, может быть использована при подготовке к ОГЭ и ЕГЭ по информатике для учеников средних и старших классов.
Квалификационная работа состоит из 4 глав, содержания, заключения, литературы.
В первой главе раскрываются основные понятия и некоторые теоремы теории графов. Содержание главы ориентировано на теоретический материал, описанный в курсе дискретной математики.
Во второй главе излагаются подходы выбора решения и применения алгоритмов на разные типы задач. В третьей главе рассматривается возможности применения СКМ Maple в Теории графов, разбираются основные команды пакета GraphTheory. В четвертой главе показана методика применения Maple при решении задач на нахождение различных видов маршрутов на графе. В заключении приведены основные выводы.

Купить