Разработка программы, при помощи которой можно задать граф с любым количеством вершин и ребер

Разработка программы, при помощи которой можно задать граф с любым количеством вершин и ребер

Введение

В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования автоматов, логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной оптимизации.

Полный граф - простой граф, в котором каждая пара различных вершин смежна. Полный граф с  вершинами имеет  рёбер и обозначается .

В теории графов дополнением или обратным к графу G называется такой граф H, имеющий то же множество вершин, что и G, но в котором две несовпадающие вершины смежны тогда и только тогда, когда они не смежны в G. Чтобы найти обратный граф, необходимо дополнить данный граф до полного и удалить все ребра, которые уже были до этого.

Целью курсовой работы является: написать программу, при помощи которой можно задать граф с любым количеством вершин и ребер, построить графическое изображение графа, автоматически рассчитать ребра полного графа, и построить изображение полного графа, автоматически рассчитать дополнение графа и построить изображение дополнения графа.

Для хранения исходных данных была выбрана база данных Access, структура которой будет рассмотрена в разделе «исходные данные».

Чтобы построить интерфейс пользователя для взаимодействия с исходными данными, а также для построения изображений был выбран язык программирования АВС-Паскаль.

1. Разработка проекта приложения

граф пользователь программный ребро

1.1 Постановка задачи

Будем использовать следующий способ задания графа: перечислением множества вершин, и перечислением множества ребер - пар вершин, соединенных ребром.

<{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>. Граф нам определим как модель, носителем которой является множество вершин, а отношение - бинарное отношение смежности вершин. Тогда данный граф запишется как <{a,b,c,d}; {(a,b), (b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)}>. В таком представлении ребру соответствуют две пары вершин (v1,v2) и (v2,v1), инцидентных данному ребру. Чтобы задать такое представление, достаточно для каждого ребра указать двухэлементное множество вершин - его мы и будем отождествлять с ребром. Для данного графа рёбра задаются множеством {{a,b},{b,c},{a,c},{c,d}} и граф мы будем записывать как пару (V,E), где V - множество вершин, а E - множество рёбер.

При составлении программы необходимо разработать следующие модули:

Ø  модуль записи исходных данных в программу: для каждого графа задается множество вершин и множество ребер.

Ø  аналитический модуль: модуль построения полного графа и дополнительного графа.

Ø  графический модуль, в котором будут строиться графические изображения заданного графа, полного графа, дополнительного графа.

Основной задачей работы является составить программу, которая:

.        Задает исходный граф;

.        Рассчитывает полный и дополнительный граф;

.        Строит изображения трех графов.

1.2 Организация входных и выходных данных

Входным данным является количество вершин графа N, двумерный массив ребер графа Gr[1..2,1..100].

Выходными данными являются построенные изображения графа, полного графа, дополнительного графа.

Промежуточными данными являются построенные массивы FullGr[1..2,1..100], AddGr[1..2,1..100]

.3 Выбор состава технических и программных средств

ABC 3.0.1 - Система предназначена для обучения программированию на языке Паскаль и ориентирована на школьников и студентов младших курсов.

Эта система призвана осуществить переход от простейших программ к модульному, объектно-ориентированному, событийному и компонентному программированию. Многие концепции в Pascal ABC упрощены, что позволяет использовать их на более ранних этапах обучения. Модуль графики обходится без объектов, хотя его возможности практически совпадают с графическими возможностями Borland Delphi.

Благодаря простоте и графическим возможностям этого программного продукта данный язык был выбран в качестве среды разработки.

Простейшие событийные программы можно писать, пользуясь лишь процедурными переменными. В консольных программах можно создавать таймеры и звуки, которые реализованы без использования объектов. В модулях может отсутствовать разделение на секцию интерфейса и секцию реализации; в этом случае модули устроены практически так же, как и основная программа, что проще на ранних этапах обучения. Тела методов можно определять непосредственно внутри классов, что позволяет создавать классы практически сразу после изучения записей, процедур и функций. Имеется модуль контейнерных классов (динамические массивы, стеки, очереди, множества), а также библиотека визуальных компонентов.

Компилятор Pascal ABC не генерирует исполняемый код в виде.exe-файла, а создает в результате компиляции дерево программы в памяти, которое затем выполняется с помощью встроенного интерпретатора.

В программе решаются независимые друг от друга подзадачи:

1.      Ввод данных;

.        Построение полного графа;

.        Построение дополнительного графа;

.        Построение графического изображения графов.

Алгоритм работы программы представлен на рисунке 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 пиксел. Исходя из количества вершин графа, рассчитывается угол, на который вершины отстоят друг от друга.

.1 Руководство пользователя

После запуска программы необходимо ввести количество вершин графа и далее ребра графа. После ввода каждой вершины необходимо отвечать вводом 0 - если хотим закончить ввод ребер графа и числом, отличным от нуля, если хотим продолжить добавлять ребра графа в исходный граф.

Рисунок 2 - Задание графа

Программа выдает заданный граф:

Рассчитывает полный граф:

Рисунок 3 - Расчет полного графа и дополнительного графа

После этого программа выводит изображения графов.

Приведем примеры результатов работы программы.

Рисунок 4 - Исходный заданный граф

Рисунок 5 - Изображение полного графа

Рисунок 7 - Изображение дополнительного графа

Рисунок 8 - Исходный граф

Рисунок 9 - Полный граф

Рисунок 10 - Дополнительный граф

2.2 Вызов и загрузка

Вызов программы производится открытием среды программирования АВС-Паскаль и загрузкой программного файла (с расширением pas). запуск программы проводится клавишей F9.

Заключение

В процессе выполнения курсовой работы был проведен следующий комплекс работ:

.        Проведена формализация задачи;

.        запрограммированы основные задачи построения полного и дополнительного графов, а также вывод их на экран.

.        Подготовлены контрольные примеры для контроля правильности вычислений. В соответствии с контрольными примерами программа была отлажена.

.        Подготовлена пояснительная записка.

Цели, поставленные в начале выполнения курсовой работы, выполнены.

Библиография

1.      Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка - М.: Финансы и статистика, 1982. - С. 151.

.        Вирт Н. Алгоритмы + структуры данных = программы - М.: Мир, 1985. - С. 406.

.        Грогоно П. Программирование на языке Паскаль - М.: Мир, 1982. - С. 384.

.        Перминов О. Н. Язык программирования Паскаль : Справочник - М.: Радио и связь, 1989. - С. 128. - ISBN 5-256-00311-9.

.        Культин Н.Б. Delphi 6. Программирование на Object Pascal - СПб.: БХВ-Петербург, 2001. - С. 528. - ISBN 5-94157-112-7.

.        Моргун А. Н. Программирование на языке Паскаль (Pascal). Основы обработки структур данных - М.: Диалектика, 2005. - С. 576. - ISBN 5-8459-0935-X.

.        Рубенкинг Н.Дж. Турбо Паскаль для Windows: в 2-х томах. Пер. с англ. - М.: Мир, 1993.

Приложения

ЛИСТИНГ ПРОГРАММЫ

Листинг 1 - Код программы на Паскаль.

program graf;graphabc, crt;N:integer;:array[1..100,1..100] of integer;:array[1..100,1..100] of integer;:array[1..100,1..100] of integer;:array[1..100,1..100] of integer;,j,k,Nv,M,l,R,AR:integer;,Y,Xc,Yc:integer;,pr1,pr2:boolean;,Ug:real;,YcFrom,XcTo, YcTo:integer;

begin;('Введите количество вершин графа');(N);

{Ввод графа}:=1;

i:=0;k<>0 do:=i+1;

writeln('Введите ребро графа');('Введите номер первой вершины');

readln(Nv);[1,i]:=Nv;

writeln('Введите номер второй вершины');

readln(Nv);[2,i]:=Nv;

writeln('Eще одну вершину? (1/0)');(k);;:=i; {количество ребер};('Заданный граф');

for i:=1 to M do(Gr[1,i], ' ', Gr[2,i]);

readln;

{задать полный граф}('Полный граф');

k:=0;i:=1 to N-1 doj:=i+1 to N do:=k+1;[1,k]:=i;[2,k]:=j;(FullGr[1,k], ' ', FullGr[2,k]);

end;();

{задать дополнительный граф}:=0;:=0;('Дополнительный граф');

for j:=1 to k do

{берем j-ое ребро полного графа и проверяем, входит ли оно в граф}

pr:=false;i:=1 to M do:=(FullGr[1,j]=gr[1,i]) and (FullGr[2,j]=gr[2,i]);:=(FullGr[2,j]=gr[1,i]) and (FullGr[1,j]=gr[2,i]);(pr1 or pr2) then pr:=true

end;not(pr) then

{добавляем ребро в дополнительный граф}

begin:=l+1;[1,l]:=FullGr[1,j];[2,l]:=FullGr[2,j];(AddGr[1,l], ' ', AddGr[2,l]);;;:=l;;

{Построить изображение графа}();(0,0,'Заданный граф');

SetPenWidth(3);(clBlue);:=320;:=200;:=2*Pi/N;:=0;i:=1 to N do:=X+trunc(150*cos(Ug));:=Y-trunc(150*sin(Ug));:=25;[1,i]:=Xc;[2,i]:=Yc;(Xc - R, Yc - R, Xc + R, Yc + R);(xc,yc,inttostr(i));:=Ug+Alf;;(1);(clred);j:=1 to M do:=KoordV[1,gr[1,j]];:=KoordV[2,gr[1,j]];:=KoordV[1,gr[2,j]];:=KoordV[2,gr[2,j]];(XcFrom,YcFrom);

LineTo(XcTo,YcTo);;

{изображение графа построено};

{Построить изображение полного графа}();(0,0,'Полный граф');(3);

SetPenColor(clBlue);:=320;:=200;:=2*Pi/N;:=0;i:=1 to N do:=X+trunc(150*cos(Ug));:=Y-trunc(150*sin(Ug));:=25;[1,i]:=Xc;[2,i]:=Yc;(Xc - R, Yc - R, Xc + R, Yc + R);(xc,yc,inttostr(i));:=Ug+Alf;;(1);(clred);j:=1 to k do:=KoordV[1,Fullgr[1,j]];:=KoordV[2,Fullgr[1,j]];:=KoordV[1,Fullgr[2,j]];:=KoordV[2,Fullgr[2,j]];(XcFrom,YcFrom);

LineTo(XcTo,YcTo);;

{изображение полного графа построено};

{Построить изображение дополнительного графа}();(0,0,'Дополнительный граф');(3);

SetPenColor(clBlue);:=320;:=200;:=2*Pi/N;:=0;i:=1 to N do:=X+trunc(150*cos(Ug));:=Y-trunc(150*sin(Ug));:=25;[1,i]:=Xc;[2,i]:=Yc;(Xc - R, Yc - R, Xc + R, Yc + R);(xc,yc,inttostr(i));:=Ug+Alf;;(1);(clred);j:=1 to AR do:=KoordV[1,addgr[1,j]];:=KoordV[2,addgr[1,j]];:=KoordV[1,addgr[2,j]];:=KoordV[2,addgr[2,j]];(XcFrom,YcFrom);(XcTo,YcTo);;

{изображение дополнительного графа построено}.