Главная страница
qrcode

Курсовая_работа_Куликов_дискр. Курсовая работа по дисциплине Алгоритмы дискретной математики Подсчет числа остовных деревьев с помощью матрицы Кирхгофа


Скачать 329,68 Kb.
НазваниеКурсовая работа по дисциплине Алгоритмы дискретной математики Подсчет числа остовных деревьев с помощью матрицы Кирхгофа
Дата13.01.2020
Размер329,68 Kb.
Формат файлаdocx
Имя файлаКурсовая_работа_Куликов_дискр.docx
ТипКурсовая
#82879
Каталог

Министерство образования и науки Российской Федерации

Национальный исследовательский технологический университет «МИСиС»

Институт информационных технологий и автоматизированных систем управления

Кафедра Электротехники и информационно-измерительных систем
Курсовая работа
по дисциплине «Алгоритмы дискретной математики»


«Подсчет числа остовных деревьев с помощью матрицы Кирхгофа»

Руководитель,

доцент кафедры АПД ____________ Калитин Д. В.

Исполнитель,

студент гр. БИСТ-17-1____________ Куликов Г.М.

Москва,

2019

Алгоритм.

Матрицей Кирхгофа связного графа G с помеченными вершинами называется матрица Kvv=K(G), |V|=v, которую можно определить следующим образом:

Теорема Кирхгофа - число остовных деревьев в связном графе G порядка n 2 равно алгебраическому дополнению любого элемента матрицы Кирхгофа K(G).

Пример:

Найти число остовных деревьев данного графа.

Решение:

Сначала составляем для данного графа матрицу Кирхгофа.

.

Теперь находим алгебраическое дополнение, например, для элемента k11матрицы Кирхгофа.

.

Проверим, например, для элемента k23.

.

Итак, получаем, что данный граф имеет 8 остовных деревьев.

Листинг.

unit Unit1;
interface
uses

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

Dialogs, Buttons, Grids, StdCtrls, ExtCtrls;

type

// список используемых массивов

Mass=array[1..10,1..10] of integer;

Mas=array[1..10] of boolean;

Ocher=array[1..10] of integer;

Karkas=array[1..2,1..10] of integer;
type
TForm1 = class(TForm)

sg: TStringGrid;

SpeedButton3: TSpeedButton;

sr: TStringGrid;

SpeedButton4: TSpeedButton;

SpeedButton5: TSpeedButton;

Edit1: TEdit;

Label1: TLabel;

SpeedButton6: TSpeedButton;

SpeedButton7: TSpeedButton;

Image1: TImage;

Image2: TImage;

Label2: TLabel;

Label3: TLabel;

SpeedButton8: TSpeedButton;

SpeedButton9: TSpeedButton;

Edit2: TEdit;

Edit3: TEdit;

Label4: TLabel;

Label5: TLabel;

SaveDialog1: TSaveDialog;

OpenDialog1: TOpenDialog;

SpeedButton10: TSpeedButton;

Button1: TButton;

Memo1: TMemo;

Label6: TLabel;

Button2: TButton;

procedure SpeedButton3Click(Sender: TObject);

procedure SpeedButton4Click(Sender: TObject);

procedure SpeedButton5Click(Sender: TObject);

procedure SpeedButton6Click(Sender: TObject);

procedure SpeedButton7Click(Sender: TObject);

procedure SpeedButton8Click(Sender: TObject);

procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Image2Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure SpeedButton10Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Edit1KeyPress(Sender: TObject; var Key: Char);

procedure sgKeyPress(Sender: TObject; var Key: Char);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);
private

{ Private declarations }

public

procedure Printtr(f:Karkas);

procedure AllKar(v,q:integer);
end;


var nt,up,down,numb,S:integer;

AM:Mass;

Pr:Mas;

Tree:Karkas;

Turn:Ocher;
var

Form1: TForm1;

f:file of integer;

ot,u1,u2,dxi,dxj,idown,n,wrt,i,j:integer;

a:array[1..10,1..10] of integer;

m:array[1..10] of integer;

vx:array[1..10] of integer;

vy:array[1..10] of integer;

dxc:array[1..100] of integer;

dxv:array[1..100] of integer;

dx,ar:array[1..100,1..100] of integer;
implementation
{$R *.dfm}

// В этот метод мы выводим весь нарисованный каркас

procedure tform1.Printtr(f:Karkas);

var

i,j:integer; // переменные для цикла

strin:string;
begin

inc(S);

memo1.Lines.Add(' S='+inttostr(S)); // добавляем в меню данные
for i:=1 to 2 do

begin

strin:='';

for j:=1 to n-1 do

strin:=strin+inttostr(f[i,j])+' ';

memo1.Lines.Add(strin);

end;

end;
// сам каркас который выводим методом выше

procedure tform1.AllKar(v,q:integer);

var j:integer;

begin

if down>=up then exit;

j:=q;

// через цикл перебираем значение и строим полностью дерево каркас

while (j<=nt)and(numb
if (AM[v,j]<>0)and(Pr[j]) then begin

Pr[j]:=false;

inc(numb);

Tree[1,numb]:=V;

Tree[2,numb]:=j;

Turn[up]:=j;

inc(up);

AllKar(V,j+1);

dec(up);

PR[j]:=true;

dec(numb);

end;

inc(j);

end;

// проверяем существование дерева и выводим его

if numb=nt-1 then begin

Printtr(Tree);

exit;

end;

// проверяем дерево и рекурсией саму себя, вызываем процедуру

if j=nt+1 then begin

inc(down);

AllKar(Turn[down],1);

dec(down);

end;

end;

procedure TForm1.SpeedButton3Click(Sender: TObject);

const

maxv=100;

var

m,d:array[1..maxv] of integer;

put,t,mmin, immin:integer;

label ex;

begin

n:=strtoint(edit1.Text); //строка для ввода данных сюда заносится количество вершин

inc(dxi);

u1:=strtoint(edit2.text); //строка стартовой вершины

u2:=strtoint(edit3.text); //строка финишной вершины

for i:=1 to n do

begin

d[i]:=999; {все пометки = 999}

m[i]:=0 {все пометки временные ...}

end;

d[u1]:=0; {пометка старта = 0 (путь из t в t)}
m[1]:=1; {...кроме первой}

t:=u1; {текущая вершина = стартовая}

repeat {поехали!}

for i:= 1 to n do

if m[i]=0 then {везде где пометка временная}

begin

if (d[t]+a[t,i])
d[i]:=(d[t]+a[t,i]); {меняем значение пометки на более короткое}

end;
mmin:=9999;

immin:=0;

for i:= 1 to n do {среди всех временных пометок ищем наименьшую}

if m[i]= 0 then {и объявляем ее постоянной и текущей, так}

begin {что следущую итерацию совершаем относительно ее}

if d[i]
begin

mmin:= d[i]; immin:=i; //ищем минимальную пометку

end;

end;

t:= immin;

m[t]:=1;

until t=u2; //уничтожаем цикл

dxj:=1;

dx[dxi,1]:=u2;
i:=0;

j:=u2;

repeat

repeat

inc(i)

until (d[j]=d[i]+a[i,j]) and (i<>j); //уничтожаем цикл
j:=i;

i:=0;

inc(dxj);

dx[dxi,dxj]:=j;

until j=u1;

dxc[dxi]:=dxj;

dxv[dxi]:=d[u2];

speedbutton4.Click; // нажата кнопка

end;

procedure TForm1.SpeedButton4Click(Sender: TObject);

begin

for i:= 1 to n do

for j:= 1 to n do

begin

sr.cells[i,j]:=inttostr(dx[i,j]);

end;
end;
//кнопка рисование кружочков

procedure TForm1.SpeedButton5Click(Sender: TObject);

var

aaa, aay, aax,dy,min,imin,l,i,x,y:integer;

label start1;

begin

idown:=1;

form1.canvas.Refresh; // выбираем форму

image1.Canvas.brush.color:= clwhite; // устанавливаем кисть в белый цвет

image1.Canvas.pen.Color:=clwhite; // устанавливаем ручку в белый цвет

image2.Canvas.brush.color:= clwhite; // повторяем выше действия как с image1

image2.Canvas.pen.Color:=clwhite; // повторяем выше действия как с image1

image1.Canvas.Rectangle(0,0,image1.Width,image1.Height); // рисуем круг

image2.Canvas.Rectangle(0,0,image1.Width,image1.Height); // повторяем рисуем круг

ot:=n;

for i:=1 to n do

begin

ot:=ot-i;

if ot<=0 then

begin

ot:=i;

goto start1
end;

end;

Start1:

aaa:=1;

// округляем число до целого

aay:=round(230/(ot+1));

for i:=1 to ot do

begin

aax:=round(480/(i+1));

for j:=1 to i do

end;
with image1.Canvas do

begin
brush.color:= cllime;

pen.Color:=clblue;

font.Name:='Courier'; // выставляем шрифт

font.Size:=8; // выставляем размер
for i:= 1 to n do

for j:=1 to n do

if (a[i,j]<>0) and (a[i,j]<900) then

begin

pen.Width:=1;

moveto(vx[i],vy[i]);

lineto(vx[j],vy[j]);

brush.color:= clwhite;

end;
brush.color:= clyellow;

pen.Color:=clred;
for i:= 1 to n do

begin

font.Size:=1;

ellipse(vx[i]-12,vy[i]-12,vx[i]+12,vy[i]+12); //вычитываем круг

textout(vx[i]-4,vy[i]-7,inttostr(i));

end;

end;
with image2.Canvas do

begin
brush.color:= clyellow;

pen.Color:=clblue;

font.Name:='Courier';

font.Size:=8;

for i:= 1 to n do

for j:=1 to n do

if (a[i,j]<>0) and (a[i,j]<900) then

begin

pen.Width:=1;

moveto(vx[i],vy[i]);

lineto(vx[j],vy[j]);

brush.color:= clwhite;

textout(round((vx[i]+vx[j])/2)-3,round((vy[i]+vy[j])/2)-5,inttostr(a[i,j])); // вычитываем и выводим

end;
min:=dxv[1];

imin:=1;

for i:= 1 to ot do

if min>dxv[i] then

begin

min:=dxv[i];

imin:=i;

end;
brush.color:= clyellow;

pen.Color:=clred;

for i:= 1 to n do

begin

font.Size:=1;

ellipse(vx[i]-12,vy[i]-12,vx[i]+12,vy[i]+12);

textout(vx[i]-4,vy[i]-7,inttostr(i));

end;
end;

end;
procedure TForm1.SpeedButton6Click(Sender: TObject);

begin

n:= strtoint(edit1.text);

ot:=n;

idown:=1;

edit3.Text:=edit1.Text;

speedbutton7.Click;
end;
// работа с матрицей, добавляем по диагонали 0-ки

procedure TForm1.SpeedButton7Click(Sender: TObject);

var

i:integer;

begin

for i:= 1 to n do

begin

sg.ColCount:=n+1;

sg.Rowcount:=n+1;

sr.ColCount:=n+1;

sr.Rowcount:=n+1;

sg.Cells[0,i]:=inttostr(i);

sr.Cells[0,i]:=inttostr(i);

sg.Cells[i,0]:=inttostr(i);

sr.Cells[i,0]:=inttostr(i);

end;
for i:= 1 to n do

for j:= 1 to n do

begin

ar[i,j]:=0;

end;

end;
// генерируем рандомную матрицу

procedure TForm1.SpeedButton8Click(Sender: TObject);

begin

for i:= 1 to n do

begin

vx[i]:=random(470);

vy[i]:=random(230);

end;
end;

// работа с мышкой при клике

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

// если кружков больше или равно n рисуем кручек

if idown<=n then

begin

vx[idown]:=x;

vy[idown]:=y;

image1.Canvas.brush.color:= clyellow; // цвет белый для кисти

image1.Canvas.pen.Color:=clred; // цвет красный для ручки

image1.Canvas.Ellipse(x-12,y-12,x+12,y+12);

image1.Canvas.textout(x-4,y-7,inttostr(idown));

idown:=idown+1;

if idown=n then speedbutton9.Enabled:=true;

end

end;
// повторяем процедуру Image1Click

procedure TForm1.Image2Click(Sender: TObject);

begin

image1.Canvas.brush.color:= clwhite;

image1.Canvas.pen.Color:=clwhite;

image2.Canvas.brush.color:= clwhite;

image2.Canvas.pen.Color:=clwhite;

image1.Canvas.Rectangle(0,0,image1.Width,image1.Height);

image2.Canvas.Rectangle(0,0,image1.Width,image1.Height);
end;

procedure TForm1.Button1Click(Sender: TObject);
label start;
begin

memo1.Clear; // очищаем меню

u1:=strtoint(edit2.Text); {стартовая вершина}

u2:=strtoint(edit3.Text); {финишная вершина}

speedbutton10.Click; // нажатие кнопки

for i:= 1 to n do

for j:= 1 to n do

begin

if (sg.cells[i,j]<>'-') and (sg.cells[i,j]<>'') // проверяем пустоту StringGrid, если StringGrid не пустая строка записываем в ячейки данные

then

begin

a[i,j]:=strtoint(sg.cells[i,j]); // в эти ячейки записывается массив

a[j,i]:=strtoint(sg.Cells[i,j]); // в эти ячейки записывается массив

end

else a[i,j]:=999; // максимальный массив

end;

ot:=n;

for i:=1 to n do

begin

ot:=ot-i;

if ot<=0 then

begin

ot:=i;

goto start

end;

end;

Start:

for u2:= n-ot+1 to n do

begin

speedbutton3.Click;

speedbutton5.Click;

end;
{алгоритм поиска всех остовных деревьев графа}

begin

S:=0;

FillChar(Pr,Sizeof(Pr),true); // заполняем массив

FillChar(Tree,Sizeof(Tree),0);

Pr[1]:=false;

Turn[1]:=1;

down:=1;

up:=2;

numb:=0;

nt:=n;

for i:=1 to nt do

for j:=1 to nt do

if a[i,j]=999 then AM[i,j]:=0

else AM[i,j]:=a[i,j];

end;

AllKar(1,1); // вызываем каркас остового дерева

{конец алгоритма}

end;

procedure TForm1.SpeedButton10Click(Sender: TObject);

var

i:integer;

begin

ot:=0;

dxi:=0;

dxj:=0;

wrt:=0;

i:=0;

j:=0;
n:=strtoint(edit1.Text);
idown:=1;

speedbutton7.click;

image1.Canvas.brush.color:= clwhite;

image1.Canvas.pen.Color:=clwhite;

image2.Canvas.brush.color:= clwhite;

image2.Canvas.pen.Color:=clwhite;

image1.Canvas.Rectangle(0,0,image1.Width,image1.Height);

image2.Canvas.Rectangle(0,0,image1.Width,image1.Height);
edit1.Text:= inttostr(n);

for i:=1 to n do

sg.Cells[i,i]:='0';

end;
procedure TForm1.FormCreate(Sender: TObject);

begin

speedbutton10.Click;

end;

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);

begin

case key of

'0'..'9',#8:;

else key:=chr(0);

end;
end;

procedure TForm1.sgKeyPress(Sender: TObject; var Key: Char);

begin

case key of

'0','1',#8:;

else key:=chr(0);

end;
end;
// 2 метода ниже выводят информацию о студенте написавшего программу

procedure TForm1.Button2Click(Sender: TObject);

begin

messagebox(0,'Алгоритм подсчета числа остовных деревьев с помощью матрицы Кирхгофа','Об программе',MB_OK);

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

messagebox(0,'Студент: Георгий Куликов, группа: группа БИСТ-17-1','Об авторе',MB_OK);

end;
end.
Пример выполнения программы.

Открывает программу, выбираем размер матрицы.

Заполняем выбранную матрицу.

Рисуем вершины графа на плоскости.

Нажимаем кнопку “Найти остовы деревьев”. Результат выводится в правой части экрана.

Список используемой литературы.

В. А. Горбатов - “Фундаментальные основы дискретной математики”. Информационная математика.

Седжвик Р. – “Фундаментальные алгоритмы C++. Анализ. Структуры данных. Сортировка. Поиск.”





перейти в каталог файлов


связь с админом