Алгоритмы на графах. Нахождение кратчайшего пути
Основные понятия и свойства эйлеровых и гамильтоновых цепей и циклов в теории графов. Изучение алгоритма Дейкстры и Флойда для нахождения кратчайших путей в графе. Оценки для числа ребер с компонентами связанности. Головоломка "Кенигзберзьких мостов".
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 08.10.2014 |
| Размер файла | 2,4 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Примерами применения теории графов является поиск связных компонентов и поиск кратчайших, самых „дешевых” и самых „дорогих” путей в коммуникационных сетях. Для построения таких путей используются разнообразные алгоритмы на графах. В работе рассмотрены наиболее употребимые алгоритмы - алгоритмы Дейкстры и Флойда.
Следовательно, практическая ценность теории графов бесспорна.
СПИСОК ЛИТЕРАТУРЫ
1. Альфред В. Ахо, Джон Э. Хопкрофт, Структуры данных и алгоритмы. изд. дом «Вильямс», Москва, 2000. 118с.
2. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку. М.: «Вильямс», 2006. 189--195 с.
3. Голицына О. Л., Попов И. И. Основы алгоритмизации и программирования: Учебное пособие/ 2-е издание., М.: ФОРУМ. 2006.432 с. (Профессиональное образование).
4. Кузнецов Ю. Н., Кузубов В. И., Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. М.; 1980, 300 с. (Высшая школа)
5. Лавров С.С. Программирование. Математические основы, средства, теория. СПб.: БХВ, Петербург, 2001. 319 с.
6. Мелихов А.Н. применение графов для проектирования дискретных устройств. / А.Н. Мелихов, Л.С. Бернштейн, В.М. Курейчик - М.: Наука, 1974. 304 с.: ил.
7. Павленкова Е.В., Чекмарев Д.Т. СБОРНИК ЗАДАНИЙ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ. Учебно-методическое пособие. Нижний Новгород: Нижегородский госуниверситет, 2012. 68 с.
8. Хаггарти Р Дискретная математика для программистов. - М.: «Техносфера», 2003. - 320 с.
9. Шпак Ю. А. Delphi 7 на примерах/Под ред. Ю. С. Ковтанюка К.: Издательство Юниор, 2003. 384 с.
Размещено на Allbest.ur
Подобные документы
Основные понятия теории графов. Содержание метода Дейкстры нахождения расстояния от источника до всех остальных вершин в графе с неотрицательными весами дуг. Программная реализация исследуемого алгоритма. Построение матриц смежности и инцидентности.
курсовая работа [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Понятие и содержание теории графов. Правила построения сетевых графиков и требования к ним. Сетевое планирование в условиях неопределенности. Теория принятия решений, используемые алгоритмы и основные принципы. Пример применения алгоритма Дейкстры.
курсовая работа [1,0 M], добавлен 26.09.2013Основные понятия теории графов. Расстояния в графах, диаметр, радиус и центр. Применение графов в практической деятельности человека. Определение кратчайших маршрутов. Эйлеровы и гамильтоновы графы. Элементы теории графов на факультативных занятиях.
дипломная работа [145,5 K], добавлен 19.07.2011Описание заданного графа множествами вершин V и дуг X, списками смежности, матрицей инцидентности и смежности. Матрица весов соответствующего неориентированного графа. Определение дерева кратчайших путей по алгоритму Дейкстры. Поиск деревьев на графе.
курсовая работа [625,4 K], добавлен 30.09.2014
