Создание бесплатной программы для тестирования студентов

Размещено на http://www.allbest.ru/

Содержание

1. Введение

2. Индивидуальное задание

3. Стратегия решения

3.1 Краткая теория

3.2 Реализованный алгоритм

4. Рабочий проект

4.1 Основные используемые переменные, константы, процедуры и функции

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

6. Листинг

7. Примеры работы программы (скриншоты)

8. Тестирование и отладка программы

1. 

1. Введение

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

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

Это все позволит студенту получить хороший опыт и навыки при работе с подобными приложениями.

В этой курсовой работе данная задача решается с использованием языка программирования Delphi.



2. Индивидуальное задание

Вариант №24

Для заданного неориентированного графа найти максимальный по включению полносвязный подграф.



3. Стратегия решения

3.1 Краткая теория

В теории графов кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Клики имеют очень важное значение в теории графов и используются во многих других математических задачах. Также клики изучаются и в информатике. Несмотря на всю сложность, изучаются большое количество алгоритмов для поиска клик [1].

Изучение полных подграфов началось ещё с формулировки теоремы Рамсея в терминах теории графов Эрдёшем и Секерешем. Сам термин «клика» был введен при работе Люка и Пери, использовавшие полные подграфы при изучении социальных сетей для создания клики людей, то есть групп людей, которые знакомы друг с другом [4].

3.2 Реализованный алгоритм

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

Пусть задан неориентированный граф G1 матрицей смежностей M1



Рис. 3.1 Неориентированный граф и матрица смежностей

Если выделить клику из этого графа и представить ее в виде матрицы смежностей, то получим матрицу вида:

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

Чтобы найти клику в неориентированном графе необходимо выделить подматрицы, такие как указаны выше, в матрице смежностей. Множество вершин, образующее эту матрицу и будет множеством вершин клики. Так как исходная матрица смежностей симметрична относительно главной диагонали, то поиск подматриц будет осуществляться только в ее верхнем или нижнем треугольнике [2-3].

Шаг 1.

Двигаемся по матрице как показано на рис. 3.1 в поисках первой попавшийся единицы. Запоминаем ее координаты (R,C).

Рис. 3.2 Пример работы алгоритма

Шаг 2.

Двигаемся в поисках следующей единицы по адресу (R,C1)

Шаг 3.

Начинаем спускаться по столбцу (С1) для нахождения единицы, причем искать ее нужно по адресу (С,С1), так как в исходной матрице столбцы попарно смежных вершин не обязательно соседствуют. Запоминаем строку каждой найденной таким образом единицы для поиска в следующих столбцах. Увеличиваем длину множества вершин на 1.

Количество повторений Шага 3 равно текущему размеру множества вершин.

Если по указанному адресу мы не встречаем единицы, значит данный столбец не образует подматрицу смежностей клики - пропускаем его. Начинаем Шаг 2.

Если размер множества вершин образующих клику больше 2 то запоминаем это множество.

Так до конца строки.

Повторяем Шаг 1 для всех единиц в строке.

Таким образом проходим всю матрицу. На выходе получаем несколько множеств вершин, отбираем среди них только оригинальные, не содержащие в себе других подмножеств.

Отобранные подмножества и есть клики заданного графа.



4. Рабочий проект

На окне программы отображены 3 кнопки (SetSize_btn, RandomGraph_btn, Solve_btn); таблица, являющаяся матрицей смежности (AdjMtrx_strGrd); окно отображения графа (Graph_img); надпись, указывающая количество вершин (Size_spEdt); надпись, указывающая множество вершин максимальной клики графа (Cluqie_lbl).

4.1 Основные используемые переменные, константы, процедуры и функции

N - переменная в которой находится значение размера графа.

Len - переменная, обозначающая текущую длину клики графа.

GrafMass - числовой двумерный массив, выполняющий роль матрицы смежностей.

Clique - числовой массив, в котором записано множество вершин максимальной клики.

IndClMass - числовой массив, в котором записаны индексы максимальной клики.

DrawGraph - процедура для рисования графа.

Rec - процедура нахождения максимальной клики.



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

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

Входными данными является количество вершин и матрица смежностей графа.

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

Максимально число вершин графа в этой программе неограниченно.

В данной программе реализуется следующий алгоритм: перед его работой заполняется матрица смежностей. Из этой матрицы выделяются подматрицы, также симметричные относительно главной диагонали. Множество вершин, образующее эту матрицу и будет множеством вершин клики. Оно выводится в окне по окончанию работы алгоритма.

Того чтобы указать количество вершин графа нужно ввести необходимое значение на поле отображения вершин и нажать кнопку «Задать размер». Чтобы добавить вершину нужно нажать на стрелку «вверх» на окне отображения вершин, а чтобы убрать вершину, нужно нажать на стрелку «вниз» на том же окне. Чтобы сгенерировать матрицу смежностей для графа нажмите на кнопку «Матрица смежностей». Чтобы изобразить граф и найти его максимальную клику, необходимо нажать на кнопку «Нарисовать граф и найти клику».



6. Листинг

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, Spin, ExtCtrls;

type

{ TForm1 }

TForm1 = class(TForm)

Graph_img: TImage; //компонент для отрисовки графа

RandomGraph_btn: TButton;

Size_spEdt: TSpinEdit;

AdjMtrx_strGrd: TStringGrid;

SetSize_btn: TButton;

Solve_btn: TButton;

Cluqie_lbl: TLabel;

procedure FormCreate(Sender: TObject);

procedure RandomGraph_btnClick(Sender: TObject);

procedure SetSize_btnClick(Sender: TObject);

procedure Solve_btnClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

var N, Dlin_cliq, i_poz: Integer; //N-размер графа, Dlin_cliq-длина клики, i_poz-на какую позицию записывать

GrafMass: array[0..100, 0..100] of Integer; //граф

Clique: array[0..100] of Integer; //клика

IndClMass: array[0..100] of Integer; //индексы для клики

implementation

{$R *.dfm}

procedure rec(stolb, Len: Integer); //stolb - текущий столбец, Len - текущая длина клики

var i, j: Integer;

begin

if Len > Dlin_cliq then begin //нашли решение

for i:= 0 to Len-1 do

Clique[i]:= IndClMass[i];

Dlin_cliq:= Len;

end;

for i:= stolb to N-1 do begin

for j:= 0 to i_poz-1 do

if GrafMass[IndClMass[j]][i] = 0 then break;

if j > N+1 then j:= 0;

if j = i_poz then begin

IndClMass[i_poz]:= i;

i_poz:= i_poz+1;

rec(stolb+1, Len+1);

end;

rec(stolb+1, Len);

end;

end;

procedure DrawGraph();

var

X, Y: array [0..100] of Integer; //координаты вершин на экране

j, i: Integer;

begin

Form1.Graph_img.Canvas.FillRect(Form1.Graph_img.ClientRect); //очистка экрана

for i:= 0 to N-1 do begin

X[i]:= Random(Form1.Graph_img.Width); //случайные значения позиций

Y[i]:= Random(Form1.Graph_img.Height);

Form1.Graph_img.Canvas.Ellipse(X[i]-10,Y[i]-10,X[i]+10,Y[i]+10);

end; //рисуем вершины

for j:= 0 to N-1 do begin

for i:= j+1 to N do

if GrafMass[j][i] = 1 then begin //рисуем линии

Form1.Graph_img.Canvas.MoveTo(X[j],Y[j]);

Form1.Graph_img.Canvas.LineTo(X[i],Y[i]);

end;

Form1.Graph_img.Canvas.TextOut(X[j]-5,Y[j]-5,IntToStr(j+1)); //пишем номера вершин

end;

end;

procedure TForm1.RandomGraph_btnClick(Sender: TObject);

var i, j: Integer;

begin

N:= Size_spEdt.Value;

for j:= 0 to N-1 do

for i:= j to N-1 do

if j = i then AdjMtrx_strGrd.Cells[i,j]:= '0' //на диагонали 0

else begin

AdjMtrx_strGrd.Cells[i,j]:= IntToStr(Random(2)); //в остальных - рандом и симметрия

AdjMtrx_strGrd.Cells[j,i]:= AdjMtrx_strGrd.Cells[i,j]; end;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Randomize;

RandomGraph_btnClick(RandomGraph_btn);

end;

procedure TForm1.SetSize_btnClick(Sender: TObject);

begin

N:= Size_spEdt.Value;

AdjMtrx_strGrd.ColCount:= N;

AdjMtrx_strGrd.RowCount:= N;

end;

procedure TForm1.Solve_btnClick(Sender: TObject);

var i, j: Integer;

begin

Dlin_cliq:= 0;

N:= AdjMtrx_strGrd.ColCount;

for j:= 0 to N-1 do //считываем граф и исправляем матрицу смежности (симметрия)

for i:= j to N-1 do begin

if AdjMtrx_strGrd.Cells[i,j] <> '0' then AdjMtrx_strGrd.Cells[i,j]:= '1';

AdjMtrx_strGrd.Cells[j,i]:= AdjMtrx_strGrd.Cells[i,j];

if j = i then AdjMtrx_strGrd.Cells[i,j]:= '0';

GrafMass[j][i]:= StrToInt(AdjMtrx_strGrd.Cells[i,j]);

GrafMass[i][j]:= GrafMass[j][i];

end;

DrawGraph(); //рисуем граф

for i:= 0 to N-1 do begin //поиск клики

i_poz:= 0;

rec(i, 0); end;

Cluqie_lbl.Caption:= 'Максимальная клика: ';

if Dlin_cliq = 1 then Cluqie_lbl.Caption:= Cluqie_lbl.Caption + 'клики нет'

else for i:= 0 to Dlin_cliq-1 do

if i < Dlin_cliq-1 then Cluqie_lbl.Caption:= Cluqie_lbl.Caption + Inttostr(Clique[i]+1) + ' -> '

else Cluqie_lbl.Caption:= Cluqie_lbl.Caption + Inttostr(Clique[i]+1);

end;

end.



7. Примеры работы программы (скриншоты)

Рис. 7.1 Начальное окно программы

Рис. 7.2 Работающее окно программы с графом, который состоит из 4 вершин и 3 ребер



8. Тестирование и отладка программы

алгоритм матрица граф неориентированный

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

Рис. 8.1 Тестовый пример №1

«Работающая программа с графом, максимальная клика которого равна множеству вершин 1-2-3»



Рис. 8.2 Тестовый пример №2

«Работающая программа с графом, максимальная клика которого равна множеству вершин 1-2-4»

Рис. 8.3 Тестовый пример №3

«Работающая программа с графом, максимальная клика которого равна множеству вершин 2-3-4»



Список использованных источников

1. Зыков А.А - «Основы теории графов» 2004 г.

2. Научная библиотека - http://sci.sernam.ru/book_comb.php?id=35.

3. Образовательный портал - http://geum.ru/referat/ref-34265_1-1.php.

4. Свободная энциклопедия - https://ru.wikipedia.org.

Размещено на Allbest.ru

...