Аннотация
Введение 3
Структура выпускной бакалаврской работы 4
Глава 1. Основные понятия 5
1.1 Определение графа 5
1.2 Подграф 12
1.3 Операции над графами 13
1.4 Маршруты, цепи и циклы 15
1.5 Степени вершин графа 18
1.6 Метрические характеристики графа 19
Глава 2. Алгоритмы поиска кратчайшего пути 21
2.1 Кратчайшие пути и основные алгоритмы их нахождения 21
2.2 Алгоритм Дийкстры 22
2.3 Трудоёмкость алгоритма 24
Глава 3. Математическая модель автотранспортных сетей 26
3.1 Граф автотранспортных сетей города 27
Заключение 30
Список используемой литературы 31
Теория графов - это раздел дискретной математики, рассматривающий множества и введенные для этих множеств отношения между элементами.
Визуальное отображение графа понятным образом представляется в виде рисунков, состоящих из точек (вершин) имеющих между собой некоторые отношения в виде соединительных линий (ребер). Однако, с математической точки зрения, рассмотрение понятного визуального представления целесообразнее заменить рассмотрением графа как математической структуры, имеющей ряд уникальных и применимых на практике свойств.
Удивительным является тот факт, что началом развития данной теории, которая, в нынешнее время используется в различных отраслях науки и экономики, принято считать решение Л. Эйлером в 1736 г. одной из популярных на тот момент задачи о кенигсбергских мостах, позволившая также найти критерий существования в графе определенного маршрута, именуемого в дальнейшем циклом Эйлера.
Впервые граф, как термин, был использован Д. Кёнигом спустя почти 200 лет после решения вышеописанной задачи Л. Эйлером, а также, им была написана первая книга по теории графов, как самостоятельному разделу математики.
Наряду с традиционными применениями элементов теории графов в таких науках, как физика, электротехника, теория связи, проектирование ЭВМ, химия, данная теория также проникла в экономические, социологические и лингвистические науки.
В момент появления ЭВМ и развития информационных инструментов, возникло большое количество задач, где, в отличии от классического анализа непрерывных величин, на первый план выходят рассуждения и построения дискретно-комбинаторного характера. Теория графов, как раз, могла предоставить аппарат, для такого рода исследований, что и привело во второй половине 20 века к бурному развитию теории графов.
В настоящее время, теория графов может выступать, как отличное приложение к решению задач в различных сферах жизни человека. Достаточно привести в пример такие объекты нашего мира, как линии метрополитена, канализационные и водоочистные сооружения, линии связи, а также автомобильные дороги, при рассмотрении структуры которых, даже самом поверхностном, можно найти отражение теории графов.
В частности, хотелось бы отметить именно применение теории графов, в решении проблем логистики в условиях автотранспортных структур городской среды.
В новейшей истории, не безызвестны случаи, когда логистика, становится одним из важнейших средств взаимодействия в обществе. Теория графов, позволяет решать задачи, помогающие при построении ряда алгоритмических методов в этой отрасли экономики.
Такие наработки, как методы поиска кратчайшего пути, методы решения задачи коммивояжера и т.д., могут позволить значительно оптимизировать логистические процессы, а значит экономить ресурсы и производить более качественных сервис.
Целью данной работы является рассмотрение основных понятий, свойств и алгоритмов теории графов, более пристальное рассмотрение решения задачи поиска наикратчайшего пути, а также, составление базовой математической модели некоторой городской сети на основе теории графов.
В ходе работы были рассмотрены различные определения, утверждения и теоремы теории графов. Был сформулирован и разобран алгоритм Дийкстры применяемый для поиска кратчайших путей в графе, а также была детально рассмотрена трудоемкость данного алгоритма.
Была построена показательная математическая модель автотранспортных сетей города, к которой применим математический алгоритм поиска кратчайших путей.
Математическая составляющая данной работы может быть использована в качестве базы для построения автоматической системы диспетчеризации. В частности, улучшенная математическая модель на основе теории графов и модифицированный под конкретный класс задач алгоритм поиска кратчайшего пути приведенный в данной работе, будет использоваться в компании, занимающейся сервисом экспресс доставки готовой продукции в переделах города. Это позволит оптимизировать процесс формирования маршрутов, т.к. данный процесс можно полностью автоматизировать, тем самым экономя различного рода ресурсы.
