Введение
Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он сформулировал и предложил решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.
Теория графов – это раздел дискретной математики, изучающий свойства графов. В общем случае граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E – подмножество V×V. На рисунке 1 представлен граф с шестью вершинами и семью ребрами.
Рисунок 1 ¬– Граф с шестью вершинами и семью ребрами
Теория графов находит применение, например, в геоинформационных системах (ГИС). Существующие или вновь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут.
В данной работе представлены лишь некоторые вопросы из теории графов. В частности решается задачи нахождения кратчайшего пути между двумя заданными вершинами графа и нахождения минимального остовного дерева. Для решения этих задач на прктике существуют готовые алгоритмы. Рассмотрением этих алгоритмов и решением конкретно заданных практических задач получились следующие результаты:
Введение………………………………………………………………………………... 4
1 Описание алгоритмов………………………………………………………………... 5
1.1 Алгоритмы нахождения кратчайшего пути между двумя заданными вершинами графа…………………………………………………………………...
5
1.2 Алгоритмы нахождения минимального остовного дерева графа…………... 10
2 Реализация алгоритмов…………………………………………………………........ 13
2.1 Реализация алгоритма Дейкстры определения кратчайшего пути между двумя заданными вершинами графа в языке программирования С++………....
13
2.2 Реализация алгоритма Прима определения минимального остовного дерева графа в языке программирования С++…………………………………...
16
3 Тестирование алгоритмов…………………………………………………………… 18
Заключение…………………………………………………………………………....... 19
Список использованной литературы…………………………………………………. 20
1. Андерсон Джеймс А. Дискретная математика и комбинаторика. – М.: Издатель- Издательский дом \"Вильямс\", 2004. – 960 с.
2. Аляев Ю.А. Тюрин С.Ф. Дискретная математика и математическая логика. – М.: Финансы и статистика, 2006. – 368 с.
3. Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: графы, матроиды, алгоритмы. – Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001. – 288 с.
4. Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: МГТУ им. Н.Э. Баумана, 2004. – 742 с.
5. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. – М., Мир, 1998. – 704 с.
6. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. – М.: Вузовская книга , 2000. – 200с.
7. Иванов Б. Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория Базовых Знаний, 2003. – 288 с.
8. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990. – 384 с.
9. Кузнецов О П.. Адельсон-Вельский Г. М. Дискретная математика дли инженера. – М.: Энергия, 1980. – 344 с.
10. Москинова Г.И. Дискретная математика. Математика для менеджера в примерах и упражнениях. – М.: Логос, 2000. – 240 с.
11. Новиков Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2000. – 304с.
12. Плотников А.Д. Дискретная математика. – М.: Новое знание, 2005. – 288 с.
13. Хаггарти Р. Дискретная математика для программистов – М.: Техносфера, 2003. – 320 с.
14. Акимов О.Е. Дискретная математика. Логика, группы, графы. – М.: Лаборатория базовых знаний, 2001. – 376 с.
15. Кристофидес Н. Теория графов: алгоритмический подход. – М.: Мир, 1978. – 432 с.