Содержание
Содержание
Введение3
1. Граф3
1.1.Основные термины и понятия3
1.2. Представление графов в компьютере4
1.2.1. Требования к представлению графов4
1.2.2. Матрица смежности5
1.2.3. Матрица инциденций5
1.2.4.Списки смежности6
1.2.5. Массив дуг6
1.3. Обходы графов7
2. Описание рабочего проекта8
2.1. Требования к работе программы8
2.2. Описание блок-схемы алгоритма8
2.3. Программная реализация алгоритма10
2.4. Руководство пользователя12
Заключение14
Литература15
Выдержка из текста
Результатом работы созданной программы являются графы, их составные части: остовные деревья, последовательности вершин обхода, а также матрица смежности.
Реализованы следующие способы представления графов на экране, в текстовом и графическом режимах:
табличное звездное задание графа в виде матрицы смежности из целых чисел весов ребер и нулей;
графическое представление в виде кружочков и линий с систематическим расположением вершин по кругу и постоянной формой ребер.
В первой главе работы приводятся основные теоретические положения, касающиеся программной реализации графовых алгоритмов.
Разработаны алгоритмы и программа в среде Delphi 6.0 поиска в ширину, в глубину и смешанного поиска по графу с применением целевой функции. Последнее значение целевой функции представляет собой суммарный вес остовного дерева графа, полученного при смешанном поиске.
Описание разработанной программы и руководство пользователя приведены во второй главе работы.
Список использованной литературы
1.Кристофидес Н. Теория графов. Алгоритмический подход.
2.Харари Ф. Теория графов.
3.Новиков Ф.А., Дискретная математика для программистов.
4.Б.Н. Миронов, Лабораторный практикум по теории графов.