Основы дискретной математики

В результате работы алгоритма был найден гамильтонов цикл DCABD общего веса 24. Делая полный перебор всех циклов в этом маленьком графе, можно обнаружить еще два других гамильтоновых цикла: ABCDA общего веса 23 и ACBDA общего веса 31. В полном графе с двадцатью вершинами существует приблизительно 6,1 * 10^16 гамильтоновых циклов, перечисление которых требует чрезвычайно много машинной памяти

и времени.

Реализация примера данного алгоритма в Delphi:

procedure TForm1. Button1Click (Sender: TObject);

const mat:array [1 4,1 4] of byte=((0,5,6,8), (5,0,7,10), (6,7,0,3), (8,10,3,0));

Versh:array [1 4] of char=('a', 'b', 'c', 'd');

buk:char='d';

Type t=set of 'a' 'd';

Var dlina, i, j, min, n, k, s:byte;

put:string;

z:t;

begin

dlina:=0;

Memo1. Lines. Clear;

for i:=1 to 4 do if versh[i]=buk then begin n:=i; s:=i;

include (z, buk);

put:=put+buk;

end;

for j:=1 to 3 do begin

if mat [n, 1]<>0 then begin min:=mat [n, 1]; k:=1; end

else begin min:=mat [n, 2]; k:=2; end;

for i:=1 to 4 do

if (mat [n, i]<min) and (mat [n, i]<>0) and (not (versh[i] in z)) then begin

min:=mat [n, i];

k:=i;

end;

dlina:=dlina+min;

put:=put+versh[k];

include (z, versh[k]);

n:=k;

end;

put:=put+'d';

dlina:=dlina+mat [k, s];

Memo1. Lines. Add ('маршрут:'+' '+put);

Memo1. Lines. Add ('длина маршрута='+IntToStr(dlina));

end;

end.

Рисунок 3.19 – Форма с результатом

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

3.2.1 Задание к работе

1 изучить теоретический материал по методическому пособию [24], лекциям и записям на практических занятиях;

2 получить задание по индивидуальному варианту в виде графа или матрицы смежности, в первом случае построить матрицу смежности, во втором – нарисовать граф;

3 составить подробное описание графа: ориентированный или неориентированный, количество вершин, дуг (рёбер), содержит ли циклы и какие, найти степени вершин, количество компонент связности и т. д.;

4 создать приложение на Delphi для расчёта матрицы инцидентности по известной матрице смежности (если граф достаточно сложный, то можно взять подграф этого графа);

5 в качестве дополнительного творческого задания создать приложение на Delphi для реализации алгоритма ближайшего соседа, алгоритма Прима, алгоритма Уоршелла, алгоритма Дейкстры, алгоритма определения количества компонент связности графа и других известных алгоритмов на графах. [13], [17], [18], [19], [20], [21].

3.2.2 Примеры выполнения

Пример 1: По заданной матрице смежности построить матрицу инцидентности.

implementation

procedure TForm1. UpDown1Click (Sender: TObject; Button: TUDBtnType);

begin

with UpDown1 do begin

with StringGrid1 do begin

RowCount:=Position;

ColCount:=Position;

end;

StringGrid2. RowCount:=Position;

end;

end;

procedure TForm1. BitBtn1Click (Sender: TObject);

var i, j, CD, P, n:byte;

MS:array of array of byte;

MI:array of array of ShortInt;

begin

P:=StrToInt (Edit1. Text);

SetLength (MS, P, P);

CD:=0;

for i:=0 to P‑1 do for j:=0 to P‑1 do begin

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

if MS [i, j]=1 then inc(CD);

end;

SetLength (MI, P, CD);

for i:=0 to High(MS) do for j:=0 to CD‑1 do MI [i, j]:=0;

n:=0;

for i:=0 to High(MS) do for j:=0 to High(MS) do

if MS [i, j]=1 then begin

MI [i, n]:=1;

MI [j, n]:=-1;

inc(n);

end;

StringGrid2. ColCount:=CD;

for i:=0 to High(MS) do for j:=0 to CD‑1 do

StringGrid2. Cells [j, i]:=IntToStr (MI[i, j]);

end;

end.

Рисунок 3.20 – Форма с результатом

Пример 2: По заданной матрице смежности построить матрицу инцидентности.

var

Form1: TForm1;

const maxv=4;

type canh=record dinh1, dinh2:byte;

dodai:real; end;

dothi=record n:byte;

l:array [1 maxv, 1 maxv] of real;

x, y:set of 1 maxv;

t:array [1 maxv] of canh;

nt:byte;

it:real; end;

implementation

{$R *.dfm}

procedure TForm1. Button1Click (Sender: TObject);

var g:dothi;

min:real;

x, y, x0, y0:1 maxv;

i, j:byte;

begin memo1. Clear;

g.n:=maxv;

edit1. Text:=inttostr(maxv);

stringgrid1.cells [0,0]:=' Номер';

for i:=1 to maxv do begin

stringgrid1.cells [0, i]:=inttostr(i);

stringgrid1.cells [i, 0]:=inttostr(i); end;

g.nt:=0; g.it:=0; g.x:=[1 g.n]; g.y:=[1];

for i:=1 to maxv do

for j:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]);

while g.nt<g.n‑1 do begin

min:=-1;

for x:=1 to g.n do

for y:=1 to g.n do

if (x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then

begin

if (min=-1) or (min>g.l [x, y]) then begin

min:=g.l [x, y];

x0:=x; y0:=y; end;

end;

g.y:=g.y+[y0];

g.nt:=g.nt+1;

g.it:=g.it+min;

with g.t [g.nt] do begin

dinh1:=x0;

dinh2:=y0;

dodai:=min; end; end;

for i:=1 to (maxv‑1) do

with g.t[i] do

memo1. Lines.add ('Ребро: '+inttostr(dinh1)+inttostr(dinh2)+' '+

'Весом: '+floattostr(dodai));

end;

end.

Рисунок 3.21 – Форма с результатом

Пример 3: Составить приложение на Delphi, реалилующее алгоритм Уоршелла.

var

Form1: TForm1;

const maxv=4;

type canh=record dinh1, dinh2:byte;

dodai:real; end;

dothi=record n:byte;

l:array [1 maxv, 1 maxv] of real;

x, y:set of 1 maxv;

t:array [1 maxv] of canh;

nt:byte;

it:real; end;

implementation

{$R *.dfm}

procedure TForm1. Button1Click (Sender: TObject);

var g:dothi;

min:real;

x, y, x0, y0:1 maxv;

i, j:byte;

begin memo1. Clear;

g.n:=maxv;

stringgrid1.cells [0,0]:=' Номер';

for i:=1 to maxv do begin

stringgrid1.cells [0, i]:=inttostr(i);

stringgrid1.cells [i, 0]:=inttostr(i); end;

g.nt:=0; g.it:=0; g.x:=[1 g.n]; g.y:=[1];

for i:=1 to maxv do

for j:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]);

while g.nt<g.n‑1 do begin

min:=-1;

for x:=1 to g.n do

for y:=1 to g.n do

if (x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then

begin

if (min=-1) or (min>g.l [x, y]) then begin

min:=g.l [x, y];

x0:=x; y0:=y; end;

end;

g.y:=g.y+[y0];

g.nt:=g.nt+1;

g.it:=g.it+min;

with g.t [g.nt] do begin

dinh1:=x0;

dinh2:=y0;

dodai:=min; end; end;

for i:=1 to (maxv‑1) do

with g.t[i] do

memo1. Lines.add ('Ребро: '+inttostr(dinh1)+inttostr(dinh2)+' '+

'Весом: '+floattostr(dodai));

end;

end.

Рисунок 3.23 – Форма с результатом

 Скачать реферат