Остаток. Задачами практики являются

• Название: Задачами практики являются
• Дата: 08.10.2018
• Размер: 472.94 Kb.
• Имя файла: Остаток.docx
• Тип: Задача; #52811

Цели и задачи практики

Задачами практики являются:

• 
  закрепление изученных материалов в сфере программирования Delphi;
  
• 
  изучение методов решения поставленных задач;
  
• 
  закрепление теоретического материала и практических навыков по дисциплинам «Информатика и программирование» и «Практика на электронно-вычислительных машинах»
  

Целями практики являются:

• 
  применение приобретенных навыков, знаний и методов дисциплин направления «Прикладная информатика» для решения конкретных задач;
  
• 
  приобретение навыков практической работы в сфере информационных технологий;
  

Задания на учебную практику

1. 
   В заданном неориентированном графе найти все четырехвершинные полные подграфы.
   
2. 
   Найти диаметр графа (задать возможность выбора: ориентированный или неориентированный граф).
   
3. 
   Определить, изоморфны ли два заданных графа.
   

Теоретическая часть
Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).

Граф может быть ориентированным или неориентированным. В ориентированном графе, связи являются направленными (то есть пары в E являются упорядоченными, например, пары (a, b) и (b, a) это две разные связи). В свою очередь в неориентированном графе, связи ненаправленные, и поэтому если существует связь (a, b) то значит, что существует связь (b, a).

Существует два способа представления графа, в виде списков смежности и в виде матрицы смежности. Оба способа подходят для представления ориентированных и неориентированных графов.

Матрица смежности

Этот способ является удобным для представления плотных графов, в которых количество рёбер (|E|) примерно равно количеству вершин в квадрате (|V|2).

В данном представлении мы заполняем матрицу размером |V| x |V| следующим образом:

A[i][j] = 1 (Если существует ребро из i в j)

A[i][j] = 0 (Иначе)

Данный способ подходит для ориентированных и неориентированных графов. Для неориентированных графов матрица A является симметричной (то есть A[i][j] == A[j][i], т.к. если существует ребро между i и j, то оно является и ребром из i в j, и ребром из j в i). Благодаря этому свойству можно сократить почти в два раза использование памяти, храня элементы только в верхней части матрицы, над главной диагональю)

Понятно, что с помощью данного способа представления, можно быстро проверить есть ли ребро между вершинами v и u, просто посмотрев в ячейку A[v][u].

Для фиксированной вершины графа  расстояние до наиболее удаленной от нее вершины:  называют эксцентриситетом (максимальное удаление) вершины .

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

Простая цепь, длина которой равна , называется диаметральной цепью. Очевидно, что диаметр графа равен наибольшему среди всех эксцентриситетов вершин графа. Два графа называются изоморфными, если у них одинаковое число вершин (обозначим его n) и вершины каждого из них можно занумеровать так числами от 1 до n, что в первом графе две вершины соединены ребром тогда и только тогда, когда вершины с такими же номерами во втором графе соединены.

Практическая часть

Тестирование программы №1. Нахождение четырехвершинных подграфов в заданном графе.



Тестирование программы №2. Вычисление диаметра орграфа.
Тестирование программы №3. Определить: изоморфны ли два заданных графа.



Приложения

Код программы №1:

unit Unit1;

interface

uses

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

Dialogs, StdCtrls, ExtCtrls, Grids;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label7: TLabel;

Label8: TLabel;

Label9: TLabel;

Label14: TLabel;

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Edit5: TEdit;

Button1: TButton;

Button3: TButton;

Button4: TButton;

Button7: TButton;

StringGrid1: TStringGrid;

StringGrid2: TStringGrid;

StringGrid3: TStringGrid;

NeorgrafRadioButton1: TRadioButton;

OrgrafRadioButton2: TRadioButton;

Button10: TButton;

procedure Button3Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

procedure StringGrid1DrawCell(Sender: TObject; ACol, ARow: Integer;

Rect: TRect; State: TGridDrawState);

procedure Button1Click(Sender: TObject);

procedure Button7Click(Sender: TObject);

procedure Button10Click(Sender: TObject);

private

{Private declarations }

public

{ Public declarations }

end;

var

Form1:TForm1;

A,i,j,k,s:Integer;

n,b,c:array[0..30,0..30] of integer;

count:integer;

implementation
{$R*.dfm}

procedure TForm1.Button1Click(Sender: TObject);

begin

try

A:=StrToInt(Edit1.Text);

except

Application.MessageBox('Необходимо ввести число','Ошибка', MB_OK+MB_ICONSTOP);

end;

StringGrid1.ColCount:=A;

StringGrid1.RowCount:=A;

StringGrid2.ColCount:=A;

StringGrid2.RowCount:=A;

StringGrid3.RowCount:=A;

StringGrid4.RowCount:=A;

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

fori:=0 to A-1 do

for j:=0 to A-1 do

begin

if NeorgrafRadioButton1.Checked then

begin

if i=j then StringGrid1.Cells[i,j]:=IntToStr(0)else

StringGrid1.Cells[i,j]:=IntToStr(random(2))

end

else

if OrgrafRadioButton2.Checked then

begin

if i=j then StringGrid1.Cells[i,j]:= IntToStr(0)

else StringGrid1.Cells[i,j]:=IntTostr(random(2))

end;

end;

end;

procedure TForm1.Button4Click(Sender: TObject);

var bbb:boolean;

begin

for i:=0 to A-1 do

for j:=0 to A-1 do

n[i,j]:=StrToInt(StringGrid1.Cells[i,j]);

b:=n;

count:=1;

for i:=0 to A-1 do

for j:=0 to A-1 do

begin

Stringgrid2.Cells[i,j]:='';

if i=j then StringGrid2.Cells[i,j]:=StringGrid1.Cells[i,j] else

if StrToInt(StringGrid1.Cells[i,j])=1 then

StringGrid2.Cells[i,j]:=StringGrid1.Cells[i,j];

end;

begin

Inc(count);

for i:=0 to A-1 do

for j:=0 to A-1 do

begin

s:=0;

for k:=0 to A-1 do s:=s+n[i,k]*b[k,j];

c[i,j]:=s;

end;

b:=c;

for i:=0 to A-1 do

for j:=0 to A-1 do

if (b[i,j]<>0) and (stringgrid2.Cells[i,j]='') then

stringgrid2.Cells[i,j]:=inttostr(count); {inttostr(b[i,j])};

bbb:=false; // ionouo iao

for i:=0 to A-1 do

for j:=0 to A-1 do

if stringgrid2.Cells[i,j]='' then bbb:=true;

if bbb and (count
end;

for i:=0 to A-1 do

for j:=0 to A-1 do

if StringGrid2.Cells[i,j]='' then

StringGrid2.Cells[i,j]:='inf';

end;

procedure TForm1.StringGrid1DrawCell(Sender: TObject; ACol, ARow: Integer;Rect: TRect; State: TGridDrawState);

begin

for i:=0 to A-1 do

for j:=0 to A-1 do

begin

if NeorgrafRadioButton1.Checked then

StringGrid1.Cells[i,j]:=StringGrid1.Cells[j,i]

end

end;

procedure TForm1.Button7Click(Sender: TObject);

var max : integer;

b : boolean;

begin

for i:=0 to A-1 do

begin

b:=false;

for j:= 0 to A-1 do

begin

if StringGrid2.Cells[j,i]='inf'then

begin

StringGrid3.Cells[0,i]:='inf';

b:=true;

end;

end;

if not b then

begin

max:=0;

for j:= 0 to A-1 do

if StrToInt(StringGrid2.Cells[j,i])>max then

max:=StrToInt(StringGrid2.Cells[j,i]);

StringGrid3.Cells[0,i]:=IntToStr(max);

end;

end;

end;

// Диаметр

procedure TForm1.Button10Click(Sender: TObject);

var

max:integer;

begin

edit3.Clear;

max:=-1;

for j:=0 to A-1 do

begin

if StringGrid3.Cells[0,j]='inf' then

begin

edit3.Text:='inf';

break;

end;

if StrToInt(StringGrid3.Cells[0,j])>max then

max:=StrToInt(StringGrid3.Cells[0,j]);

Edit3.Text:=IntToStr(max);

end;

end;

end.
Код программы №2.

unit Unit1;

interface

uses

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

Dialogs, ExtCtrls, Grids, StdCtrls, Spin;

type

TForm1 = class(TForm)

Image1: TImage;

StringGrid1: TStringGrid;

SpinEdit1: TSpinEdit;

SpinEdit2: TSpinEdit;

SpinEdit3: TSpinEdit;

Label1: TLabel;

Button1: TButton;

Button2: TButton;

Label2: TLabel;

Button3: TButton;

procedure FormCreate(Sender: TObject);

procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Image1Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{Private declarations }

public

{Public declarations }

end;

type

TMyPoint = record

x,y,l:word;

s:array of word;

end;

const PointR = 15;

var

Form1: TForm1;

MyList: array of TMyPoint;

ver: word;

Array1: array[1..99] of integer; //++

Array2: array[1..99] of integer; //++

Array3: array[1..99] of integer; //++

Array4: array[1..99] of integer; //++

Array5: array[1..99] of integer; //++

Array6: array[1..99] of integer; //++

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

begin

Image1.Canvas.Brush.Color:=clWhite;

Image1.Canvas.Pen.Color:=clBlack;

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

ver:= 0; // нет вершин

StringGrid1.Cells[1, 0]:='1';

StringGrid1.Cells[0, 1]:='1';

StringGrid1.Cells[1, 1]:='0';

end;

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

Shift: TShiftState; X, Y: Integer);

var

x1,x2,y1,y2,i,cnt:integer;

name:string;

begin

x1:=x-PointR;

x2:=x+PointR;

y1:=y-PointR;

y2:=y+PointR;

if ssLeft in Shift then

if (((x1>0) and (x20) and (y2
begin

ver:=ver+1;

str(ver,name);

Array1[ver]:=x-PointR;

Array2[ver]:=x+PointR;

Array3[ver]:=y-PointR;

Array4[ver]:=y+PointR;

Image1.Canvas.Brush.Color:=clWhite;

Image1.Canvas.Pen.Color:=clBlack;

Image1.Canvas.Ellipse(Rect(x1,y1,x2,y2));

Image1.Canvas.Font.Color:=clBlack;

Image1.canvas.TextOut(x - Image1.canvas.TextWidth(name) div 2,y - Image1.canvas.TextHeight(name) div 2,name);

SetLength(MyList,ver);

MyList[ver-1].x := x;

MyList[ver-1].y := y;

MyList[ver-1].l := 0;

end;

end;

procedure TForm1.Image1Click(Sender: TObject);

var

i:longint;

begin

if ver > 1 then

begin

stringGrid1.RowCount:=StringGrid1.RowCount+1;

stringGrid1.ColCount:=StringGrid1.ColCount+1;

StringGrid1.Cells[0,ver]:=intToStr(ver);

StringGrid1.Cells[ver, 0]:=intToStr(ver);

for i:=1 to ver do

begin

StringGrid1.Cells[ver, i]:='0';

StringGrid1.Cells[i,ver]:='0';

spinedit1.MaxValue :=ver;

spinedit2.MaxValue :=ver;

spinedit3.MaxValue :=ver;

end;

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var a1,a2:word;

begin

a1:=SpinEdit1.Value;

a2:=SpinEdit2.Value;

begin

Image1.Canvas.Pen.Color := clRed;

Image1.Canvas.MoveTo(MyList[a1-1].x,MyList[a1-1].y);

Image1.Canvas.LineTo(MyList[a2-1].x,MyList[a2-1].y);

Stringgrid1.Cells[a2,a1]:='1';

Stringgrid1.Cells[a1,a2]:='1';

inc(MyList[a1-1].l);

setlength(MyList[a1-1].s,MyList[a1-1].l);

MyList[a1-1].s[MyList[a1-1].l-1]:=a2;

end;

end;

procedure TForm1.Button2Click(Sender: TObject);

var a3:byte;

x1,x2,y1,y2,i,j,cnt:integer;

begin

a3:=SpinEdit3.Value;

for i:=1 to ver do

begin

if ((Stringgrid1.Cells[i,a3]<>'1') and (i<>a3)) then

begin

Array5[i]:=i;

end

else

begin

Array6[i]:=i;

end;

end;

for i:=1 to ver do

begin

a3:=SpinEdit3.Value;

x1:=Array1[Array5[i]];

x2:=Array2[Array5[i]];

y1:=Array3[Array5[i]];

y2:=Array4[Array5[i]];

Image1.Canvas.Brush.Color:=clWhite;

Image1.Canvas.Pen.Color:=clWhite;

Image1.Canvas.Ellipse(Rect(x1,y1,x2,y2));

x1:=Array1[Array6[i]];

x2:=Array2[Array6[i]];

y1:=Array3[Array6[i]];

y2:=Array4[Array6[i]];

Image1.Canvas.Pen.Color := clWhite;

Image1.Canvas.MoveTo(x1,y1);

Image1.Canvas.LineTo(x2,y2);

end;

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

Image1.Canvas.Brush.Color:=clWhite;

Image1.Canvas.Pen.Color:=clBlack;

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

ver:= 0;

StringGrid1.Cells[1, 0]:='1';

StringGrid1.Cells[0, 1]:='1';

StringGrid1.Cells[1, 1]:='0';

StringGrid1.ColCount:=2;

StringGrid1.RowCount:=2;

FillChar(Array5, SizeOf(Array5), 0);

end;

end.

Код программы №3.

unit Unit1;

interface

uses

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

Dialogs, StdCtrls;

Const

N=10;

type

Graf=array[1..n,1..n] of byte;

Vect=array[1..N] of byte;

TForm1 = class(TForm)

Edit1: TEdit;

Button1: TButton;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

Per:vect;

G1,G2:Graf;

implementation

{$R *.dfm}

Procedure PolnGraf;

var i,j:byte;

Begin

randomize;

for i:=1 to n do begin

for j:=1 to n do begin

{G1[i,j]:=random(2);

G2[i,j]:=random(2);{}

//if i=j then begin G1[i,j]:=1;G2[i,j]:=1;end else begin G1[i,j]:=0;G2[i,j]:=0;end;

G1[i,j]:=0;G2[i,j]:=0;

//G2[i,j]:=G1[i,j];

end;

end;

//G1[3,7]:=1;

j:=random(11);

i:=random(11);

G1[i,j]:=1;

j:=random(11);

i:=random(11);

If (j=0)or (j=6) then j:=4;

G2[j,i]:=1;

{G1[6,7]:=1;

G2[4,8]:=G1[6,7];

{for j:=1 to n do begin

G2[5,j]:=G2[7,j];

G2[7,j]:=G1[5,j];

end;{}

end;

function Proverka(l:byte):boolean;

Label 1;

var i,j:byte;

b:boolean;

Begin

b:=true;

for i:=1 to l do begin

for j:=1 to l do begin

if G1[i,j]<>G2[Per[i],Per[j]] then begin

b:=false; goto 1;end;

end;end;

1:

Proverka:=b;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Image1.Canvas.Brush.Color:=clWhite;

Image1.Canvas.Pen.Color:=clBlack;

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

ver:= 0; // нет вершин

StringGrid1.Cells[1, 0]:='1';

StringGrid1.Cells[0, 1]:='1';

StringGrid1.Cells[1, 1]:='0';

end;

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

Shift: TShiftState; X, Y: Integer);

var

x1,x2,y1,y2,i,cnt:integer;

name:string;

begin

x1:=x-PointR;

x2:=x+PointR;

y1:=y-PointR;

y2:=y+PointR;

if ssLeft in Shift then

if (((x1>0) and (x20) and (y2
begin

ver:=ver+1;

str(ver,name);

Array1[ver]:=x-PointR;

Array2[ver]:=x+PointR;

Array3[ver]:=y-PointR;

Array4[ver]:=y+PointR;

Image1.Canvas.Brush.Color:=clWhite;

Image1.Canvas.Pen.Color:=clBlack;

Image1.Canvas.Ellipse(Rect(x1,y1,x2,y2));

Image1.Canvas.Font.Color:=clBlack;

Image1.canvas.TextOut(x - Image1.canvas.TextWidth(name) div 2,

y - Image1.canvas.TextHeight(name) div 2,

name);

SetLength(MyList,ver);

MyList[ver-1].x := x;

MyList[ver-1].y := y;

MyList[ver-1].l := 0;

end;

end;

Procedure Perestanovka;

Label 2,1;

var i1,i2,i3,i4,i5,i6,i7,i8,i9,i10:byte;

t:longint;

Begin

t:=0;

for i1:=1 to N do begin Per[1]:=i1;

for i2:=1 to N do begin if i1<>i2 then begin Per[2]:=i2;

for i3:=1 to n do begin if (I3<>i1) and (I3<>i2) then

begin Per[3]:=i3; for i4:=1 to n do begin if (i4<>i3)and(i4<>i2)and(i4<>i1) then begin Per[4]:=i4; for i5:=1 to n do

begin if (i5<>i1)and(i5<>i2)and(i5<>i3)and(i5<>i4) then begin Per[5]:=I5;

for i6:=1 to n do begin if (i6<>i1)and(i6<>i2)and(i6<>i3)and(i6<>i4) and(i6<>i5) then

begin Per[6]:=I6;for i7:=1 to n do begin if (i7<>i1)and(i7<>i2)and(i7<>i3)and(i7<>i4) and(i7<>i5)and(i7<>i6) then begin Per[7]:=I7; for i8:=1 to n do

begin if (i8<>i1)and(i8<>i2)and(i8<>i3)and(i8<>i4) and(i8<>i5)and(i8<>i6)and(i8<>i7) then begin Per[8]:=I8;

for i9:=1 to n do begin if (i9<>i1)and(i9<>i2)and(i9<>i3)and(i9<>i4) and(i9<>i5)and(i9<>i6)and(i9<>i7)and(i9<>i8) then

begin Per[9]:=I9;for i10:=1 to n do begin if (i10<>i1)and(i10<>i2)and(i10<>i3)and(i10<>i4) and(i10<>i5)and(i10<>i6)and(i10<>i7)and(i10<>i8)and(i10<>i9) then begin

Per[10]:=I10;

if Proverka(n)=true then begin t:=1;goto 2;end;

{Per[10]:=I10;

t:=t+1;

if t=2000000 then begin

Per[10]:=I10;

end;{}

end;

end;

end;

end;

showmessage('Done');goto 1;

2:for i1:=1 to N do form1.Edit1.Text:=form1.Edit1.Text+' I('+inttostr(i1)+')='+inttostr(Per[i1])+' ,';

1:

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

form1.Edit1.Text:='';

PolnGraf;

Perestanovka;

end;

end.