Алгоритмы теории графов

Предмет: Теория графов(вариант 12).

Сделана в мае 2019 года ( вуз неизвестен - заказчик не сообщил).

Есть приложение (Реализация алгоритма поиска кратчайшего пути (алгоритма Дейкстры) в Matlab).

Целью настоящей курсовой работы является решение некоторых задач, относящихся к достаточно обширному разделу дискретной математики – теории графов. В рамках теории графов рассматривается целый ряд алгоритмов, которые активно используются при решении большого количества практических задач (поиск оптимального пути между двумя пунктами, построение оптимального маршрута доставки для имеющихся точек и т.д.).

В рамках настоящей курсовой работы будут рассмотрены следующие задачи:

- приведены основные сведения и определения, относящиеся к теории графов;

- рассмотрены вопросы, связанные с математическим описанием графов;

- рассмотрены задачи, связанные с расчетом метрических характеристик графов;

- продемонстрированы некоторые алгоритмы, обработки графов.

При решении некоторых из указанных задач будет использован пакет Matlab, представляющий собой мощный инструмент, обеспечивающий возможность выполнения научных расчетов самого широкого предназначения.

Таким образом, объектом исследования в рамках настоящей работы является теория графов. Предмет исследования – изучение вариантов математического описания графов, расчет их метрических характеристик и практическое использование некоторых алгоритмов их обработки.

Для выполнения исследований в настоящей работе использовались классические научные методы: анализ, синтез, дедукция. Теоретической основной выполнения работы послужила литература и электронные источники, содержащие информацию по теории графов и возможностях пакета Matlab.

Работа была успешно сдана - заказчик претензий не имел.

Уникальность работы по Antiplagiat.ru на 20.07.2020 г. составила 92%.

Введение 3

1 Основные сведения о графах 5

2 Математическое описание графов 9

3 Расчет метрических характеристик графа 10

4 Реализация алгоритмов на графе 13

4.1 Нахождение минимального пути (алгоритм Дейкстры) 13

4.2 Построение кратчайшего остовного дерева 18

4.3 Нахождение эйлерова цикла 20

4.4 Раскраска вершин графа 22

Заключение 27

Список использованных источников 28

Приложение 1 29

1. Акимов О. Е. Дискретная математика: логика, группы, графы. М.: Лаборатория базовых знаний, 2003. – 378 с.

2. Ащихмин В. Введение в математическое моделирование. – М.: Логос, 2015. – 440 с.

3. Вирт Н. Алгоритмы и структуры данных. – М.: Вильямс, 2010. – 272 с.

4. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. М.: Наука, 2000. – 544 с.

5. Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. – М.: Вильямс, 2015. – 720 с.

6. Оре О. Теория графов. - М.: Наука, 1980. – 336 с.

7. Осипова В. А. Основы дискретной математики. М.: Инфра-М, 2012. – 160 с.

8. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ. - М.:Мир, 1984. – 456 с.

9. Скиена С. Алгоритмы. Руководство по разработке. – СпБ.: БХВ-Петербург, 2011. – 720 с.

10. Уилсон Р. Введение в теорию графов. Пер. с анг. – М.:Мир, 1977. – 208 с.

11. Харари Ф. Теория графов. М.: Либроком, 2009. – 302 с.