Введение

Математический факультет

«Алгоритмы на графах»

Курсовая работа

Студента 2 курса 2 группы

А. В. Анцупова

Научный руководитель:

Доцент кафедры теоретической информатики и

дискретной математики

А. А. Привалов

Москва-2015

Оглавление

Введение……………………………………………………….…………………3

1. Графы………………………………………………………………………….5

1.2. Понятие графов и их виды…………………………………………………5

1.3. Способы описания графов…………………………………………………8

1.3.1. Матричное представление графов………………………………………8

1.3.2. Теоретико-множественное представление графов……………………10

1.3.3. Задание графов соответствием……………………………………….…11

2.Алгоритмы на графах………………………………………………………..12

2.1. Алгоритм Беллмана-Форда……………………………………………….12

2.2. Алгоритм Флойда-Уоршелла……………………………………………..18

Заключение……………………………………………………………………...22

Список использованной литературы……………………………………….…23

Введение

Тема данной курсовой работы «Алгоритмы на графах» является очень актуальной в настоящее время. Благодаря своему широкому применению данная тема постоянно развивается и совершенствуется. Данная тема очень широко применяется даже в обыденной жизни человека: поиск кратчайшего пути от одной точки до другой, в работе GPS при анализе загруженности дорог и выборе оптимального маршрута движения, коммутации информационных пакетов в сетях (например, Интернет) и прочее. Можно найти множество способов применить данную тему в жизни.
Иногда применение графов для отображения какой-либо модели является очень полезным и наглядным. Графы применяются во многих областях науки. Например, в химии – молекулярная структура, в электронике – сети, дорожные карты и многое другое. Поэтому очень важно уметь применять поиск кратчайшего пути в графе.
В настоящее время существует два наиболее популярных алгоритма поиска кратчайшего пути:
1. Алгоритмы Беллмана – Форда;
2. Алгоритм Флойда – Уоршелла.
У каждого из представленных алгоритмов существуют свои достоинства и недостатки, которые необходимо отметить в данной курсовой работе и выбрать наилучший алгоритм. Выбор будет осуществляться по сложности программного кода, скорости работы, затратам памяти.
Каждый из представленных алгоритмов используется в компьютерной технике, поэтому важно отметить в данной курсовой работе и способы представления математической модели «граф», которые получили наибольшее распространение, выделить их достоинства и недостатки.
При выполнении данной курсовой работы ставятся следующие задачи:
1. Рассмотреть понятие графа и их существующие виды.
2. Рассмотреть существующие способы представления графов в вычислительной технике.
3. Дать определение кратчайшего пути.
4. Изучить существующие алгоритмы поиска кратчайшего пути в графах.
В первой главе будет дано определение графа, выделены их основные виды, а также подробно рассмотрены способы представления графов в вычислительной технике.
Во второй главе следует дать определение кратчайшего пути и вынести на рассмотрение основные алгоритмы поиска кратчайших путей, их особенности, достоинства и недостатки.
Так что же такое «граф»? Перейдем непосредственно к рассмотрению данного вопроса.

Графы