Алгоритмы на графах. Графы, оргафы, деревья
Автор работы: Пользователь скрыл имя, 12 Февраля 2015 в 11:00, курсовая работа
Описание работы
Современная математика позволяет решать сложные математические задачи. Математика рассматривает широкий круг задач, в это число входят графы, со временем графы стали развиваться как отдельная математическая дисциплина.
Графы берут свое начало с 17 века. Первой задачей является, задача о семи мостах. С того момента область наполнялась теориями, методами, алгоритмами, которые будут описаны в курсовой работе.
Содержание работы
Введение
1 Виды графов; 1.1Неориентированный граф; 1.2 Ориентированный граф;
1.3 Смешанный и изоморфный граф; 1.4 Характеристики графов смежности,
матрица и инцидентности; 2 Операции над графами; 2.1Локальные операции;
2.2Алгебраические операции; 3 Маршруты, пути, циклы в графе; 3.1 Поиск в
Ширину; 3.2 Поиск в глубину; 4 Кратчайшие пути; 4.1Алгоритм Дейкстры;
5.1Представление деревьев с помощью матрицы смежности; 6 Разработка
программы; Заключение; Список использованных источников
Файлы: 8 файлов
2_-_Titulnyy_list__list_Zadanie_k_KR.doc
— 56.00 Кб (Просмотреть файл, Скачать файл)3_-_SODERZhANIE.doc
— 51.00 Кб (Просмотреть файл, Скачать файл)4_-_VVEDENIE_do_3-kh_listov.doc
— 58.00 Кб (Скачать файл)
ВВЕДЕНИЕ
Современная математика позволяет решать сложные математические задачи. Математика рассматривает широкий круг задач, в это число входят графы, со временем графы стали развиваться как отдельная математическая дисциплина.
Графы берут свое начало с 17 века. Первой задачей является, задача о семи мостах. С того момента область наполнялась теориями, методами, алгоритмами, которые будут описаны в курсовой работе.
В процессе построения сложных программ невозможно представить программу без использования графов и его свойств, таким образом можно сказать, что графы являются фундаментом любой сложной программы.
В своих книгах М. Макконнелл, утверждает, что использование графов обеспечивает максимальную эффективность и функциональность программы, способствует ее гибкого исполнения.
Возможности вычислительной техники и созданного программного обеспечения позволяют руководителю остановиться только на математической формализации проблемы, после чего решение превращается в использование имеющихся компьютерных программ. Однако умение формализовать возникающую проблему требует особой методологии рассмотрения ситуации.
В данной курсовой работе будет рассмотрена тема «Графы и Орграфы», и описаны такие понятия как:
- Граф;
- Смешанный граф;
- Изоморфный Граф;
- Смешанный Граф;
- Ребро;
- Цена;
- Вершина.
И такие действия над графами как
- операция удаления;
- операция добавления;
- алгебраические операции;
- произведение;
- маршруты и циклы;
- поиск в глубину.
Для демонстрации этих свойств будет разработана программа на языке С++. Данная программа по заданным вершинам и указанным ценам графа строит матрицу смежности.