Алгоритмы на графах. Нахождение кратчайшего пути - Математика курсовая работа

Главная

Математика
Алгоритмы на графах. Нахождение кратчайшего пути

Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Алгоритмы на графах. Нахождение кратчайшего пути
Годом возникновения теории графов единодушно считается год 1736, когда Леонард Эйлер опубликовал решение так называемой задачи о Кенигсбергских мостах, а также нашел общий критерий существования Эйлерового цикла в графе.
Получение дальнейших существенных результатов в этой области датируются серединой ХIХ века.
Однако начало проведения активных систематических исследований и становления теории графов как отдельного авторитетного раздела современной математики произошло еще почти 100 лет назад, то есть в середине ХХ века. Именно с этого времени граф становится одной из самых распространенных и популярных математических моделей во многих сферах науки и техники. Картинка в виде набора точек на плоскости и линий, проведенных между некоторыми из них, стала удобной и наглядной форме изображения самых разнообразных объектов, процессов и явлений.
Во многом это связано с возникновением, бурным развитием и распространением электронных вычислительных машин и, как следствие, значительным возрастанием роли задач дискретного характера. Математика от "обслуживания" преимущественно физики переходит к проникновению своих методов в другие сферы человеческой деятельности.
Одним из мощных инструментов такого проникновения является граф. С чисто формальной точки зрения граф можно рассматривать как один из разновидностей алгебраической системы (а именно, как модель), а следовательно, и всю теорию графов как раздел современной алгебры. Действительно, результаты и методы алгебры широко используются в теории графов. Однако за последние полвека активного, интенсивного и экстенсивного развития теория графов выработала свою достаточно специфическую собственную проблематику и методологию.
Одну из задач, которую можно решить с помощью графа является задача нахождения кратчайших расстояний между обьектами.
Нахождение кратчайшего пути - жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.
Наиболее распространенные методы поиска кратчайших расстояний - это использование алгоритма Дейкстры (для нахождения кратчайшего пути между двумя вершинами), алгоритма Флойда (для нахождения кратчайших путей между всеми парами вершин) и алгоритма Йена (для нахождения k - кратчайших путей в графе).
Целью курсовой работы было изучить и реализовать на практике алгоритм Дейкстры и Флойда для нахождения кратчайших путей в графе. Задачи работы:
1. Исследовать свойства эйлеровых и гамильтоновых цепей и циклов в теории графов.
2. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе.
3. Приведение примеров решения задач этими методами.
Для графов с конечным множеством вершин и ребер, как правило, проблема существования алгоритма решения задач, в том числе экстремальных, решается положительно. Решение многих задач, связанных с конечными графами, может быть выполнено с помощью полного перебора всех допустимых вариантов. Однако таким способом удается решить задачу только для графов с небольшим числом вершин и ребер. Поэтому существенное значение для графов имеет построение эффективных алгоритмов, находящих точное или приближенное решение.
Доказательство. Заметим, что каждое ребро графа в сумме учитывается дважды (см. рис.1.12), и поэтому справедливо равенство (1.1). Заметим, что сумма степеней всех вершин в графе (или мультиграф без петель) должно быть чётным. Это следует из того, что если взять вершины, вообще не связаны друг с другом, то сумма степеней этих вершин равна нулю. Добавляя любое ребро, связывает две вершины, увеличиваем сумму всех степеней на 2 единицы. Таким образом, сумма всех степеней вершин парная. Из равенства 1.1 следует такое утверждение: число вершин нечетной степени в графе обязательно является четным числом. Теорема доказана.
Матрица смежности - это симметричная матрица, элементы которой равны нулю или единице (диагональные элементы равны нулю) и такая, что сумма чисел в любой строке и любом столбце равна степени соответствующей вершины. Так, для графа, приведенного на рис.1.13, матрица смежности построится в виде:
Рис.1.13. К построению матрицы смежности 3-х вершинного графа
Последовательность ребер , в которой соседние ребра инцидентны одной и той же вершине называются цепью. Цепь называется простой, если все вершины, принадлежащие ей (кроме, возможно, первой и последней), различны; число в этом случае называют длиной цепи.
Если , то цепь называется циклом. Цикл, в котором все вершины различны, называется простым. Примеры простых цепей и простых циклов приведены на рис.1.14:
(1,3), (3,4), (4,6) - простая цепь;
(1,2), (2,5), (5,6) - простая цепь;
(1,3), (3,4), (4,6), (6,5), (5,2) (2,1) - простой цикл.
Рис 1.14. Пример графа с простыми цепями и простыми циклами
Граф является подграфом графа , если . Если , то подграф называется остовним подграфом.
эта сумма называется прямой, если , .
Пусть дан граф G=(Х, Г), дугам которого приписаны веса (стоимости длины), задаваемые матрицей С = [cij].
Задача о «кратчайшем пути» состоит в нахождении кратчайшего пути от заданной начальной вершины sx до заданной конечной вершины tx, при условии, что такой путь существует tR(s) (здесь R(s) - множество, достижимое из вершины s) и все циклы в графе имеют неотрицательный суммарный вес. Так как если в графе будет присутствовать цикл с отрицательным суммарным весом и хi - некоторая его вершина, то, двигаясь от s к хi, обходя этот цикл достаточно большое число раз и попадая, наконец в t, получится путь со сколь угодно малым (> ?) весом. Таким образом, в этом случае кратчайшего пути не существует. Так что неориентированные дуги (ребра) графа G не могут иметь отрицательные веса.
Процедура находит путь минимального веса в графе G = (V, E) заданном весовой матрицей W у которой элемент равен весу ребра соединяющего i-ую и j-ую вершины. При этом предполагается, что все элементы wij неотрицательны. Путь ищется из вершины номер u1 к вершине номер u2 . Процедура использует алгоритм Дейкстры. Для представления веса, равного бесконечности, используется число GM, передаваемое в алгоритм. Это число можно задавать в зависимости от конкретной задачи.
Алгоритм по которому происходит поиск заключается в следующем:
1. Всем вершинам приписывается вес - вещественное число, d(i) := GM для всех вершин кроме вершины с номером u1, а d(u1 ) := 0.
2. Всем вершинам приписывается метка m(i) := 0.
3. Вершина u1 объявляется текущей: t := u1.
4. Для всех вершин у которых m(i) равно 0, пересчитываем вес по формуле
5. Среди вершин для которых выполнено m(i) = 0 ищем ту для которой d(i) минимальна, если минимум не найден, т.е. вес всех не "помеченных" вершин равен бесконечности (GM), то путь не существует, покидаем алгоритм.
6. Иначе найденную вершину c минимальным весом полагаем текущей и помечаем (m(t) := 1).
7. Если t = u2 , то найден путь веса d(t), покидаем алгоритм и переходим на следующий шаг.
Дан граф смежности для нахождения минимального пути от вершины 1 до всех остальных (рис. 4.1.)
Представим граф, в виде матрица длин дуг
Таблица 1. Представление матрицы к задаче 1
Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.
Задаем стартовые условия: d(1)=0, d(x)=? Окрашиваем вершину 1, y=1.
Находим ближайшую вершину к окрашенной нами, используя формулу:
Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=7. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу, ведущую в эту вершину. Согласно выражению это дуга (1,4)
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(3)=1-4-2-5-6-3 Длина маршрута L=63;
d(6)=1-4-2-5-6 Длина маршрута L=48.
Дан граф смежности для нахождения минимального пути от вершины 1 до всех остальных
Представим граф, в виде матрица длин дуг
Стартовая вершина, от которой строится дерево кратчайших путей - вершина 1.
Задаем стартовые условия: d(1)=0, d(x)=?
Находим ближайшую вершину к окрашенной нами, используя формулу:
Минимальную длину имеет путь от вершины 1 до вершины 4 d(4)=2. Включаем вершину №4 в текущее ориентированное дерево, а так же дугу, ведущую в эту вершину. Согласно выражению это дуга (1,4)
Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа.
d(3)=1-4-6-5-2-3 Длина маршрута L=9;
Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности. курсовая работа [228,5 K], добавлен 30.01.2012
Эйлеровы цепи и циклы, теоремы. Алгоритм построения эйлерова цикла. Обоснование алгоритма. Нахождение кратчайших путей в графе. Алгоритм Форда отыскания кратчайшего пути. Задача отыскания кратчайших расстояний между всеми парами вершин. Алгоритм Флойда. реферат [108,4 K], добавлен 01.12.2008
Поиск кратчайших путей для пар вершин взвешенного ориентированного графа с весовой функцией. Включение матрицы в алгоритм Флойда, содержащую вершину, полученную при нахождении кратчайшего пути. Матрица, которая содержит длины путей из вершины в вершину. презентация [36,1 K], добавлен 16.09.2013
Понятия теории графов, их связность и задача о кратчайшей цепи. Программная реализация метода Дейкстры, его сравнение с методом простого перебора. Описание логики программного модуля. Примеры работы программы нахождения кратчайшей цепи в связном графе. курсовая работа [330,2 K], добавлен 25.11.2011
Способы решения задач дискретной математики. Расчет кратчайшего пути между парами всех вершин в ориентированном и неориентированном графах с помощью использования алгоритма Флойда. Анализ задачи и методов ее решения. Разработка и характеристика программы. курсовая работа [951,4 K], добавлен 22.01.2014
Основные понятия теории графов. Маршруты и связность. Задача о кёнигсбергских мостах. Эйлеровы графы. Оценка числа эйлеровых графов. Алгоритм построения эйлеровой цепи в данном эйлеровом графе. Практическое применение теории графов в науке. курсовая работа [1006,8 K], добавлен 23.12.2007
Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры. контрольная работа [466,3 K], добавлен 11.03.2011
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Алгоритмы на графах. Нахождение кратчайшего пути курсовая работа. Математика.
Реферат по теме Методика использования тока в биологически активных точках
Контрольная работа по теме Тепловая защита зданий
Курсовая работа по теме Рабочее время: понятие, нормы и виды
Реферат По Математике Криволинейные И Поверхностные Интегралы
Дипломная работа: Разработка системы KPI. Скачать бесплатно и без регистрации
Сочинение Рассуждение По Литературе План Клише
Небольшое Сочинение На Тему Богатство Русского Языка
Курсовая работа по теме Постановка поисково-оценочного бурения на Иньвинской площади
Развивающие Самостоятельные И Контрольные Работы 3 Класс
Контрольная Работа На Тему Метод Отдельного Случая (Кейс-Стади) И Его Использование В Практике Социальной Работы
Курсовая Работа На Тему Техника Как Социокультурное Явление
Дипломная работа по теме Современные тенденции формирования рынка труда региона
Реферат: Использование телеконференций в медицине
Шпаргалка: Переходная экономика России
Дипломная работа: Риски менеджмента и управление человеческими ресурсами в сестринском деле. Скачать бесплатно и без регистрации
Реферат: Business Law Antitirust Essay Research Paper OutlineThesis
Курсовая работа по теме Экономическая эффективность откорма крупного рогатого скота
Курсовая работа по теме Понятие и сущность конституции
Системы Канализации Реферат
Дипломная работа по теме Государственная правоохранительная служба как предмет комплексного межотраслевого института российского права
Методика поиска и разведки месторождений полезных ископаемых - Геология, гидрология и геодезия курсовая работа
Смоляне в окружении А. Пушкина - Литература реферат
Лексические и фонетические основы русского языка - Иностранные языки и языкознание шпаргалка