Выдержка из текста работы
Годом возникновения теории графов единодушно считается год 1736, когда Леонард Эйлер опубликовал решение так называемой задачи о Кенигсбергских мостах, а также нашел общий критерий существования Эйлерового цикла в графе.
Получение дальнейших существенных результатов в этой области датируются серединой ХIХ века.
Однако начало проведения активных систематических исследований и становления теории графов как отдельного авторитетного раздела современной математики произошло еще почти 100 лет назад, то есть в середине ХХ века. Именно с этого времени граф становится одной из самых распространенных и популярных математических моделей во многих сферах науки и техники. Картинка в виде набора точек на плоскости и линий, проведенных между некоторыми из них, стала удобной и наглядной форме изображения самых разнообразных объектов, процессов и явлений.
Во многом это связано с возникновением, бурным развитием и распространением электронных вычислительных машин и, как следствие, значительным возрастанием роли задач дискретного характера. Математика от «обслуживания» преимущественно физики переходит к проникновению своих методов в другие сферы человеческой деятельности.
Одним из мощных инструментов такого проникновения является граф. С чисто формальной точки зрения граф можно рассматривать как один из разновидностей алгебраической системы (а именно, как модель), а следовательно, и всю теорию графов как раздел современной алгебры. Действительно, результаты и методы алгебры широко используются в теории графов. Однако за последние полвека активного, интенсивного и экстенсивного развития теория графов выработала свою достаточно специфическую собственную проблематику и методологию.
Одну из задач, которую можно решить с помощью графа является задача нахождения кратчайших расстояний между обьектами.
Нахождение кратчайшего пути — жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.
Наиболее распространенные методы поиска кратчайших расстояний — это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k — кратчайших путей в графе).
Целью курсовой работы было изучить и реализовать на практике алгоритм Дейкстры и Флойда для нахождения кратчайших путей в графе. Задачи работы:
1. Исследовать свойства эйлеровых и гамильтоновых цепей и циклов в теории графов.
2. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе.
3. Приведение примеров решения задач этими методами.
Для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для графов имеет построение эффективных алгоритмов, находящих точное или приближенное решение.
