Разработка проекта приложения, при помощи которого можно задать граф с любым количеством вершин и ребер, построить его графическое изображение, автоматически рассчитать ребра полного графа. Выбор состава программных средств. Руководство пользователя.
Аннотация к работе
В теории графов дополнением или обратным к графу G называется такой граф H, имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G. Целью курсовой работы является: написать программу, при помощи которой можно задать граф с любым количеством вершин и ребер, построить графическое изображение графа, автоматически рассчитать ребра полного графа, и построить изображение полного графа, автоматически рассчитать дополнение графа и построить изображение дополнения графа. Будем использовать следующий способ задания графа: перечислением множества вершин, и перечислением множества ребер - пар вершин, соединенных ребром. Граф нам определим как модель, носителем которой является множество вершин, а отношение - бинарное отношение смежности вершин. При составлении программы необходимо разработать следующие модули: O модуль записи исходных данных в программу: для каждого графа задается множество вершин и множество ребер.В процессе выполнения курсовой работы был проведен следующий комплекс работ: 1. 3. запрограммированы основные задачи построения полного и дополнительного графов, а также вывод их на экран.
Введение
В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования автоматов, логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной оптимизации.
Полный граф - простой граф, в котором каждая пара различных вершин смежна. Полный граф с вершинами имеет ребер и обозначается .
В теории графов дополнением или обратным к графу G называется такой граф H, имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G. Чтобы найти обратный граф, необходимо дополнить данный граф до полного и удалить все ребра, которые уже были до этого.
Целью курсовой работы является: написать программу, при помощи которой можно задать граф с любым количеством вершин и ребер, построить графическое изображение графа, автоматически рассчитать ребра полного графа, и построить изображение полного графа, автоматически рассчитать дополнение графа и построить изображение дополнения графа.
Для хранения исходных данных была выбрана база данных Access, структура которой будет рассмотрена в разделе «исходные данные».
Чтобы построить интерфейс пользователя для взаимодействия с исходными данными, а также для построения изображений был выбран язык программирования АВС-Паскаль.
1. Разработка проекта приложения граф пользователь программный ребро
1.1 Постановка задачи
Будем использовать следующий способ задания графа: перечислением множества вершин, и перечислением множества ребер - пар вершин, соединенных ребром.
. Граф нам определим как модель, носителем которой является множество вершин, а отношение - бинарное отношение смежности вершин. Тогда данный граф запишется как . В таком представлении ребру соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин - его мы и будем отождествлять с ребром. Для данного графа ребра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф мы будем записывать как пару (V,E), где V - множество вершин, а E - множество ребер.
При составлении программы необходимо разработать следующие модули: O модуль записи исходных данных в программу: для каждого графа задается множество вершин и множество ребер.
O аналитический модуль: модуль построения полного графа и дополнительного графа.
O графический модуль, в котором будут строиться графические изображения заданного графа, полного графа, дополнительного графа.
Основной задачей работы является составить программу, которая: 1. Задает исходный граф;
2. Рассчитывает полный и дополнительный граф;
3. Строит изображения трех графов.
1.2 Организация входных и выходных данных
Входным данным является количество вершин графа N, двумерный массив ребер графа Gr[1..2,1..100].
Выходными данными являются построенные изображения графа, полного графа, дополнительного графа.
Промежуточными данными являются построенные массивы FULLGR[1..2,1..100], ADDGR[1..2,1..100]
1.3 Выбор состава технических и программных средств
Pascal ABC 3.0.1 - Система предназначена для обучения программированию на языке Паскаль и ориентирована на школьников и студентов младших курсов.
Эта система призвана осуществить переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию. Многие концепции в Pascal ABC упрощены, что позволяет использовать их на более ранних этапах обучения. Модуль графики обходится без объектов, хотя его возможности практически совпадают с графическими возможностями Borland Delphi.
Благодаря простоте и графическим возможностям этого программного продукта данный язык был выбран в качестве среды разработки.
Простейшие событийные программы можно писать, пользуясь лишь процедурными переменными. В консольных программах можно создавать таймеры и звуки, которые реализованы без использования объектов. В модулях может отсутствовать разделение на секцию интерфейса и секцию реализации; в этом случае модули устроены практически так же, как и основная программа, что проще на ранних этапах обучения. Тела методов можно определять непосредственно внутри классов, что позволяет создавать классы практически сразу после изучения записей, процедур и функций. Имеется модуль контейнерных классов (динамические массивы, стеки, очереди, множества), а также библиотека визуальных компонентов.
Компилятор Pascal ABC не генерирует исполняемый код в виде.exe-файла, а создает в результате компиляции дерево программы в памяти, которое затем выполняется с помощью встроенного интерпретатора.
В программе решаются независимые друг от друга подзадачи: 1. Ввод данных;
2. Построение полного графа;
3. Построение дополнительного графа;
4. Построение графического изображения графов.
Алгоритм работы программы представлен на рисунке 1.
Рисунок 1 - Модель работы программы
2. Описание приложения
Входное данное N - количество вершин.
Массив gr:array[1..100,1..100] of integer - двумерный массив ребер графа. Каждая строка массива задает ребро графа, где первый элемент - первая вершина графа, второй элемент - вторая вершина графа.
Массив FULLGR:array[1..100,1..100] of integer - двумерный массив ребер полного графа. Каждая строка массива задает ребро графа, где первый элемент - первая вершина графа, второй элемент - вторая вершина графа.
Массив ADDGR:array[1..100,1..100] of integer - двумерный массив ребер полного графа. Каждая строка массива задает ребро графа, где первый элемент - первая вершина графа, второй элемент - вторая вершина графа.
Массив KOORDV:array[1..100,1..100] of integer; - используется при построении графа и задает координаты вершины графа на графическом полотне (асбцисса - первое число в строке, ордината - второе число в строке).
Остальные данные являются промежуточными.
Используем основные приемы обработки массивов для программирования задачи - ввод массива, заполнение массива, проверка элементов массива на какое-либо условие.
Изображение графа строим с помощью графических примитивов.
Координаты вершин графа будем задавать так, чтобы они находились на воображаемой окружности с центром в центре графического экрана и радиусом 150 пиксел. Исходя из количества вершин графа, рассчитывается угол, на который вершины отстоят друг от друга.
2.1 Руководство пользователя
После запуска программы необходимо ввести количество вершин графа и далее ребра графа. После ввода каждой вершины необходимо отвечать вводом 0 - если хотим закончить ввод ребер графа и числом, отличным от нуля, если хотим продолжить добавлять ребра графа в исходный граф.
Рисунок 2 - Задание графа
Программа выдает заданный граф:
Рассчитывает полный граф:
Рисунок 3 - Расчет полного графа и дополнительного графа
После этого программа выводит изображения графов.
Приведем примеры результатов работы программы.
Рисунок 4 - Исходный заданный граф
Рисунок 5 - Изображение полного графа
Рисунок 7 - Изображение дополнительного графа
Рисунок 8 - Исходный граф
Рисунок 9 - Полный граф
Рисунок 10 - Дополнительный граф
2.2 Вызов и загрузка
Вызов программы производится открытием среды программирования АВС-Паскаль и загрузкой программного файла (с расширением pas). запуск программы проводится клавишей F9.
Вывод
В процессе выполнения курсовой работы был проведен следующий комплекс работ: 1. Проведена формализация задачи;
2. Спроектированы основные программные структуру для задания графов в памяти ЭВМ;
3. запрограммированы основные задачи построения полного и дополнительного графов, а также вывод их на экран.
4. Подготовлены контрольные примеры для контроля правильности вычислений. В соответствии с контрольными примерами программа была отлажена.
5. Подготовлена пояснительная записка.
Цели, поставленные в начале выполнения курсовой работы, выполнены.
Список литературы
1. Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка - М.: Финансы и статистика, 1982. - С. 151.
2. Вирт Н. Алгоритмы структуры данных = программы - М.: Мир, 1985. - С. 406.
3. Грогоно П. Программирование на языке Паскаль - М.: Мир, 1982. - С. 384.
4. Перминов О. Н. Язык программирования Паскаль : Справочник - М.: Радио и связь, 1989. - С. 128. - ISBN 5-256-00311-9.
5. Культин Н.Б. Delphi 6. Программирование на Object Pascal - СПБ.: БХВ-Петербург, 2001. - С. 528. - ISBN 5-94157-112-7.
6. Моргун А. Н. Программирование на языке Паскаль (Pascal). Основы обработки структур данных - М.: Диалектика, 2005. - С. 576. - ISBN 5-8459-0935-X.
7. Рубенкинг Н.Дж. Турбо Паскаль для Windows: в 2-х томах. Пер. с англ. - М.: Мир, 1993.