Курсовая работа: Разработка программ для реализации комбинаторных алгоритмов

РЕФЕРАТ

Курсовая работа состоит из: 19 листов, 6 рисунков, 1 приложение с листингом разработанной программы, 1 приложение с блок-схемой алгоритма и 7 источников.
Ключевые слова: граф, связный граф, матрица смежности, поиск в глубину, неориентированный граф.
Объект разработки: программа, позволяющая определить связность неориентированного графа.
Цель работы: получение практического опыта в программировании на Delphi7, закрепление уже изученных техник программирования, получение навыков и отладки программ.
Программа была создана в образовательных целях. Она позволяет пользователю создать неориентированный граф благодаря матрице смежности и определить его связность. Кроме того, предусмотрена загрузка пользователем матрицы смежности из файла.



























СОДЕРЖАНИЕ

ВВЕДЕНИЕ
1.РАЗРАБОТКА АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ
1.1 Вариант задания
1.2 Основа для разработки алгоритма
1.3 Разработка структуры программы
1.4 Основной алгоритм определения связности графа
2. РАЗРАБОТКА ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ
2.1 Внешний вид программы
2.2 Основные переменные, константы, функции и процедуры программы
3.ПРИМЕРЫ РАБОТЫ ПРОГРАММЫ
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ А – ЛИСТИНГ ПРОГРАММЫ

ВВЕДЕНИЕ

Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин. [1]
Графы находят широкое применение в современной науке и технике. Они используются и в естественных науках (физике и химии) и в социальных науках (например, социологии), но наибольших масштабов применение графов получило в информатике и сетевых технологиях. [1]
В качестве простейшего примера из жизни можно привести схему перелётов определённой авиакомпании, которая моделируется графом, где вершинами графа являются города, а рёбрами — рейсы, соединяющие пары городов. Дерево каталогов в компьютере также является графом: диски, папки и файлы являются вершинами, а рёбра показывают вложенность файлов и папок в папки и диски. [1]
Строение Википедии моделируется ориентированным графом, в котором статьи — вершины графа, а гиперссылки — дуги (тематическая карта). [1]
Графы являются основным объектом изучения