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

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

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

В теории графов дополнением или обратным к графу 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. Рассчитывает полный и дополнительный граф;

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−311−9.

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

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

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

Приложения

ЛИСТИНГ ПРОГРАММЫ Листинг 1 — Код программы на Паскаль.

program graf;

uses graphabc, crt;

var N: integer;

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;

i, j, k, Nv, M, l, R, AR:integer;

X, Y, Xc, Yc: integer;

pr, pr1, pr2:boolean;

Alf, Ug: real;

XcFrom, YcFrom, XcTo, YcTo: integer;

begin

clrscr;

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

readln (N);

{Ввод графа}

k:=1;

i:=0;

while k<>0 do

begin

i:=i+1;

writeln ('Введите ребро графа');

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

readln (Nv);

gr[1,i]: =Nv;

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

readln (Nv);

gr[2,i]: =Nv;

writeln ('Eще одну вершину? (1/0)');

readln (k);

end;

M:=i; {количество ребер}

clrscr;

writeln ('Заданный граф');

for i:=1 to M do

writeln (Gr[1,i], ' ', Gr[2,i]);

readln;

{задать полный граф}

writeln ('Полный граф');

k:=0;

for i:=1 to N-1 do

for j:=i+1 to N do

begin

k:=k+1;

FullGr[1,k]: =i;

FullGr[2,k]:=j;

writeln (FullGr[1,k], ' ', FullGr[2,k]);

end;

readln ();

{задать дополнительный граф}

i:=0;

l:=0;

writeln ('Дополнительный граф');

for j:=1 to k do

begin

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

pr:=false;

for i:=1 to M do

begin

pr1:=(FullGr[1,j]=gr[1,i]) and (FullGr[2,j]=gr[2,i]);

pr2:=(FullGr[2,j]=gr[1,i]) and (FullGr[1,j]=gr[2,i]);

if (pr1 or pr2) then pr:=true

end;

if not (pr) then

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

begin

l:=l+1;

AddGr[1,l]: =FullGr[1,j];

AddGr[2,l]:=FullGr[2,j];

writeln (AddGr[1,l], ' ', AddGr[2,l]);

end;

end;

AR:=l;

readln;

{Построить изображение графа}

ClearWindow ();

TextOut (0,0,'Заданный граф');

SetPenWidth (3);

SetPenColor (clBlue);

X:=320;

Y:=200;

Alf:=2*Pi/N;

Ug:=0;

for i:=1 to N do

begin

Xc:=X+trunc (150*cos (Ug));

Yc:=Y-trunc (150*sin (Ug));

R:=25;

KoordV[1,i]: =Xc;

KoordV[2,i]:=Yc;

Ellipse (Xc — R, Yc — R, Xc + R, Yc + R);

textOut (xc, yc, inttostr (i));

Ug:=Ug+Alf;

end;

SetPenWidth (1);

SetPenColor (clred);

for j:=1 to M do

begin

XcFrom:=KoordV[1,gr[1,j]];

YcFrom:=KoordV[2,gr[1,j]];

XcTo:=KoordV[1,gr[2,j]];

YcTo:=KoordV[2,gr[2,j]];

MoveTo (XcFrom, YcFrom);

LineTo (XcTo, YcTo);

end;

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

readln;

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

ClearWindow ();

TextOut (0,0,'Полный граф');

SetPenWidth (3);

SetPenColor (clBlue);

X:=320;

Y:=200;

Alf:=2*Pi/N;

Ug:=0;

for i:=1 to N do

begin

Xc:=X+trunc (150*cos (Ug));

Yc:=Y-trunc (150*sin (Ug));

R:=25;

KoordV[1,i]: =Xc;

KoordV[2,i]:=Yc;

Ellipse (Xc — R, Yc — R, Xc + R, Yc + R);

textOut (xc, yc, inttostr (i));

Ug:=Ug+Alf;

end;

SetPenWidth (1);

SetPenColor (clred);

for j:=1 to k do

begin

XcFrom:=KoordV[1,Fullgr[1,j]];

YcFrom:=KoordV[2,Fullgr[1,j]];

XcTo:=KoordV[1,Fullgr[2,j]];

YcTo:=KoordV[2,Fullgr[2,j]];

MoveTo (XcFrom, YcFrom);

LineTo (XcTo, YcTo);

end;

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

readln;

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

ClearWindow ();

TextOut (0,0,'Дополнительный граф');

SetPenWidth (3);

SetPenColor (clBlue);

X:=320;

Y:=200;

Alf:=2*Pi/N;

Ug:=0;

for i:=1 to N do

begin

Xc:=X+trunc (150*cos (Ug));

Yc:=Y-trunc (150*sin (Ug));

R:=25;

KoordV[1,i]: =Xc;

KoordV[2,i]:=Yc;

Ellipse (Xc — R, Yc — R, Xc + R, Yc + R);

textOut (xc, yc, inttostr (i));

Ug:=Ug+Alf;

end;

SetPenWidth (1);

SetPenColor (clred);

for j:=1 to AR do

begin

XcFrom:=KoordV[1,addgr[1,j]];

YcFrom:=KoordV[2,addgr[1,j]];

XcTo:=KoordV[1,addgr[2,j]];

YcTo:=KoordV[2,addgr[2,j]];

MoveTo (XcFrom, YcFrom);

LineTo (XcTo, YcTo);

end;

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

end.