Курсовая на тему Разработка алгоритмического и программного обеспечения для решенияграфовых задач
Автор: Юлия
Тип работы: Курсовая
Предмет: Математические методы и модели в экономике
Страниц: 20
Год сдачи: 2010
ВУЗ, город: Москва
Выдержка
Введение
Родоначальником теории графов считается Леонард Эйлер. В 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 с.