Графовые модели. Остов минимального веса (стр. 3 из 4)

Рисунок 6. Исходный граф.

Выбираем вершину начала построения остова минимального веса, например, первую вершину.

Шаг 1. Найдено ребро минимального веса: 1-2=6. Полученный остов на рисунок 7.

Рисунок 7. Полученный оостов на шаге 1

Шаг 2. Найдено ребро минимального веса: 2-3=7. Полученный остов на рисунок 8.

Рисунок 8.Полученный остов на шаге 2

Шаг 3. Найдено ребро минимального веса: 3-4=9. Полученный остов на рисунок 9.

Рисунок 9.Полученный остов на шаге 3

Шаг 4. Найдено ребро минимального веса: 3-5=11.

Рассмотрены все вершины и инцидентные ребра этим вершинам, оставшиеся образуют цикл в полученном минимальном остове. А это не удовлетворяет условиям поставленной задачи.

На четвертом шаге получили окончательный остов минимального веса, который представлен на рисунке 10.

Рисунок 10. Остов минимального веса

При изменении вершины начала построения конфигурация остова минимального веса не измениться, а измениться лишь последовательность построения ребер остова.

Например, если в качестве начальной вершины выбрать четвертую вершину, то последовательность этапов построения остова минимального веса будет выглядеть следующим образом:

Шаг 1. 4-3=9;

Шаг 2. 3-2=7;

Шаг 3. 2-1=6;

Шаг 4. 3-5=11;

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

Рисунок 11. Матрица весов

Полученный минимальный остов с помощью программной модели изображен на рисунке 12.

Рисунок 12. Полученный минимальный остов

После проверки вычислений вручную и программной модели результат одинаковый, это означает, что программная модель работает и функционирует верно.

Задача №2. Дан взвешенный, связный, неориентированный граф, состоящий из девяти вершин. Необходимо найти остов минимального веса с помощью алгоритма Краскала. Исходный граф на рисунке 13.

Рисунок 13. Исходный граф

Выбираем вершину начала построения остова минимального веса, например, первую вершину.

Шаг 1. Найдено ребро минимального веса: AC=1. Полученный остов на рисунок 14.

Рисунок 13. Полученный остов на шаге 1

Шаг 2. Найдено ребро минимального веса: CF=3, AB=4, AC=4. Полученный остов на рисунок 15.

Рисунок 14. Полученный остов на шаге 2

Шаг 3. Найдено ребро минимального веса: FD=4, EK=3, AE=4. Полученный остов на рисунок 15.

Рисунок 15. Полученный остов на шаге 3

Шаг 4. Найдено ребро минимального веса: KH=5, KG=4. Рассмотрены все вершины и инцидентные ребра этим вершинам, оставшиеся ребра образуют цикл в полученном минимальном остове. А это не удовлетворяет условиям поставленной задачи.

На четвертом шаге получен окончательный остов минимального веса, который представлен на рисунке 16.

Рисунок 16. Остов минимального веса

Решим данную задачу с помощью программной модели. Чтобы решить данную задачу необходимо построить матрицу весов.

Таблица 1. Матрица весов

A	B	C	D	E	F	G	H	K
A	-	4	1	9	4	-	-	-	-
B	4	-	-	-	-	-	-	5	-
C	1	-	-	10	-	3	-	-	-
D	9	-	10	-	5	4	-	6	9
E	4	-	3	5	-	7	-	-	3
F	-	-	-	4	7	-	10	-	-
G	-	-	-	-	-	10	-	-	7
H	-	5	-	6	-	-	-	-	5
K	-	-	-	9	3	-	7	5	-

Полученный минимальный остов с помощью программной модели изображен на рисунке 17.

Рисунок 17. Остов минимального веса

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

Заключение

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

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

Список литературы

Судоплатов С.В., Овчинникова Е. В. Элементы дискретной математики: Учебник. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ,2002. – 208 с.

Кандзюба С.П., Громов В.Н. Delphi 7. Базы данных и приложения. Лекции и упражнения. – СПб: ООО «ДиаСофтЮП», 2005. – 576 с.

Богумирский Б. А. Энциклопедия Windows 98. 2-е изд. – СПб.: Питер, 2003–896 с.

Липский С.Г. «Комбинаторика для программистов»

Васильков Ю.В., Н.Н. Василькова «Компьютерные технологии вычислений в математическом моделировании», М. Финансы и Статистика, 1999

Культин Н.Б. Delphi 7 Программирование на Object Pascal. – СПб.: БХВ – Петербург, 2005. – 528 с.

Приложение А: листинг программы

unit Unit1;

interface

uses

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

Dialogs, Buttons, Grids, StdCtrls, ExtCtrls, ComCtrls, XPMan, Menus;

type

TForm1 = class(TForm)

sg: TStringGrid;

SpeedButton3: TSpeedButton;

sr: TStringGrid;

SpeedButton4: TSpeedButton;

SpeedButton5: TSpeedButton;

Edit1: TEdit;

Label1: TLabel;

SpeedButton7: TSpeedButton;

Image1: TImage;

Image2: TImage;

Label2: TLabel;

Label3: TLabel;

Timer1: TTimer;

SpeedButton8: TSpeedButton;

CheckBox1: TCheckBox;

Bevel1: TBevel;

Bevel2: TBevel;

Bevel3: TBevel;

Bevel4: TBevel;

Bevel5: TBevel;

Bevel6: TBevel;

Bevel7: TBevel;

Bevel8: TBevel;

Bevel9: TBevel;

Bevel10: TBevel;

BitBtn1: TBitBtn;

BitBtn2: TBitBtn;

Vremya: TTimer;

XPManifest1: TXPManifest;

Label4: TLabel;

BitBtn3: TBitBtn;

BitBtn4: TBitBtn;

Label5: TLabel;

Label6: TLabel;

procedure FormCreate(Sender: TObject);

procedure SpeedButton3Click(Sender: TObject);

procedure SpeedButton4Click(Sender: TObject);

procedure SpeedButton5Click(Sender: TObject);

procedure SpeedButton7Click(Sender: TObject);

procedure Image2DblClick(Sender: TObject);

procedure SpeedButton8Click(Sender: TObject);

procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Image2Click(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

procedure BitBtn2Click(Sender: TObject);

procedure VremyaTimer(Sender: TObject);

procedure FormShow(Sender: TObject);

procedure BitBtn4Click(Sender: TObject);

procedure sgClick(Sender: TObject);

procedure srClick(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

f:file of integer;

idown,n,wrt,i,j:integer;

a,ar: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;

implementation

uses Unit2;

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

var

t,i:integer;

begin

n:=8; {изначально число вершин=8}

SpeedButton3.Enabled:=True;

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);

for i:=1 to sr.ColCount do

for j:=1 to sr.Rowcount do begin

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

end;

for i:=1 to sg.ColCount do

for j:=1 to sg.Rowcount do begin

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

edit1.Text:= inttostr(t);

for t:=1 to n do begin

sg.Cells[t,t]:='-';

sr.Cells[t,t]:='-';

end; end;

edit1.Text:= inttostr(n);

end;

procedure TForm1.SpeedButton3Click(Sender: TObject);

var

o,min,imin,jmin:integer;

begin

SpeedButton3.Enabled:=false;

assignfile(f,extractfilepath(application.ExeName)+'\in.krs');

rewrite(f);

for i:= 1 to n do

for j:= 1 to n do

begin

if sg.cells[i,j]='-' then

wrt:=999

else

wrt:=strtoint(sg.cells[i,j]);

write(f,wrt);

end;

closefile(f);

assignfile(f,extractfilepath(application.exename)+'\in.krs');

reset(f);

for i:= 1 to n do

for j:= 1 to n do

begin

read(f,wrt);

if wrt=999 then

sg.cells[i,j]:='-'

else

sg.cells[i,j]:= inttostr(wrt);

a[i,j]:=wrt;

end;

closefile(f);

for i:=1 to n do

m[i]:=0;

m[1]:=1;

repeat

o:=0;

min:=100; imin:=1; jmin:=1;

for i:= 1 to n do

if m[i]=1 then

for j:= 1 to n do

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

begin

if a[i,j]<min then

begin

min:= a[i,j];

imin:=i;

jmin:=j;

o:=1;

end; end;

if o=1 then

begin

ar[imin,jmin]:=min;

ar[jmin,imin]:=min;

m[jmin]:=1;

end;

until o=0;

speedbutton4.Click;

end;

procedure TForm1.SpeedButton4Click(Sender: TObject);

begin

for i:= 1 to n do

for j:= 1 to n do

begin

if ar[i,j]=0 then

sr.cells[i,j]:='-'

else

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

end;

end;

procedure TForm1.SpeedButton5Click(Sender: TObject);

var

i,x,y:integer;

begin

idown:=1;

form1.canvas.Refresh;

if checkbox1.Checked then speedbutton8.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);