Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна №2
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра СКС
Інформація про роботу
Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Дискретна математика
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра СКС
Звіт
з лабораторної роботи № 2
з дисципліни: “Дискретна матетематика”
на тему: “ Задача про кістякове дерево екстремальної (мінімальної або максимальної) ваги
”
Мета: навчитися створювати програму яка обчислює задачу про кістякове дерево екстремальної (мінімальної або максимальної) ваги
Теоретичні відомості
При знаходженні кістякового дерева графа підхід із відкиданням ребер не є ефективним через те, що складно перевіряти наявність циклів в утворюваному графі.
Ефективним є підхід із конструюванням (утворенням) кістяка. У цьому разі просто перевіряти наявність циклів в графі, що виникає.
Вказаний підхід реалізує алгоритм Пріма (так званий алгоритм найближчого сусіда).
Крок 1. Присвоєння початкових значень.
S'={Xα}, Xα - довільна вершина графа (скажімо, перша за номером).
S''= S\S', V' = Ø
Крок 2. Оновлення даних.
Знаходимо таке ребро (Xi, Xj), що Xi ϵ S', Xj ϵ S'' та
W(Xi, Xj)= min{ W(Xα, Xβ)| Xα ϵ S', Xβ ϵ S''}
Покладаємо S' = S' U { Xi }, S'' = S\S', V' = V'U{(Xi, Xj)}
Крок 3. Перевірка на завершення.
Якщо S' = S, то G' = (S', V') - шуканий граф.
В іншому випадку переходимо на Крок 2.
Далі наведено приклад виконання алгоритму Пріма.
Граф задано списком ребер з вказанням їх ваг.
(1,4|1), (4,1|1), (1,5|3), (5,1|3), (2,3|3), (3,2|3), (2,4|5),
(4,2|5), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (4,5|2), (5,4|2).
Відповідний цьому списку граф
Спершу впорядковуємо ребра за зростанням їх ваг. Для цього слід використати якийсь алгоритм сортування.
(1,4|1), (4,1|1), (4,5|2), (5,4|2), (1,5|3), (5,1|3), (2,3|3),
(3,2|3), (2,5|4), (5,2|4), (3,5|4), (5,3|4), (2,4|5), (4,2|5).
Тепер власне виконуємо алгоритм Пріма (додаючи для кожного кроку 2 ребро мінімальної ваги).
S = {1,2,3,4,5}
Крок 1. S' = {1} S'' = {2,3,4,5} V' = Ø
Крок 2 . V' = V'U{(1,4|1)}={(1,4|1)}
S' = {1,4} S'' = {2,3,5}
Крок 3. S'≠S
Крок 2. V' = V'U{4,5|2} = {(1,4|1), (4,5|2)}
Крок 3. S'≠S
Крок 2. V' = V'U {(5,2|4)} = {(1,4|1), (4,5|2), (5,2|4)}
S' = {1,2,4,5} S'' = {3}
Крок 3. S'≠S
Крок 2. V' = V'U {(2,3|3)} = {(1,4|1), (4,5|2), (5,2|4), (2,3|3)}
S' = {1,2,3,4,5} S'' = Ø
Крок 3. S'=S
Таким чином, отримали таке кістякове дерево мінімальної ваги для початкового графа.
Вага отриманого кістякового дерева дорівнює 10.
Код програми мовою Delphi:
unit Pasik;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Buttons, Grids;
type
TForm1 = class(TForm)
StringGrid1: TStringGrid;
Label1: TLabel;
BitBtn2: TBitBtn;
Label2: TLabel;
procedure FormCreate(Sender: TObject);
procedure FormPaint(Sender: TObject);
procedure DrawLine(a1,a2,c: integer);
procedure StringGrid1SetEditText(Sender: TObject; ACol, ARow: Integer;
const Value: String);
procedure BitBtn2Click(Sender: TObject);
procedure DrawGraph;
private
{ Private declarations }
public
{ Public declarations }
end;
TMyPoint=record
x:integer;
y:integer;
name:string
end;
var
Form1: TForm1;
MyPoint:array[1..5] of TMyPoint;
koef:integer;
implementation
{$R *.dfm}
procedure TForm1.DrawGraph;
var
x,kx,ky,a,b:integer;
begin
Form1.Refresh;
for x:=1 to 5 do
begin
kx:=MyPoint[x].x+koef;
ky:=MyPoint[x].y+koef;
Form1.Canvas.Ellipse(kx,ky,kx+10,ky+10);
Form1.Canvas.TextOut(kx,ky-15,MyPoint[x].name);
end;
for a:=2 to 5 do
for b:=1 to a-1 do
if ((StringGrid1.Cells[b,a]<>'') and (StrtoInt(StringGrid1.Cells[b,a])>0)) then DrawLine (a,b,1);
end;
procedure TForm1.DrawLine(a1,a2,c: integer);
var
x1,y1,x2,y2:integer;
begin
if c=1 then Form1.Canvas.Pen.Color:=clBlack;
if c=2 then Form1.Canvas.Pen.Color:=clRed;
x1:=MyPoint[a1].x+koef+5;
y1:=MyPoint[a1].y+koef+5;
Form1.Canvas.MoveTo(x1,y1);
x2:=MyPoint[a2].x+koef+5;
y2:=MyPoint[a2].y+koef+5;
Form1.Canvas.LineTo(x2,y2);
Form1.Canvas.Pen.Color:=clBlack;
end;
procedure TForm1.FormCreate(Sender: TObject);
var
x:integer;
begin
StringGrid1.Cells[1,0]:='A';
StringGrid1.Cells[2,0]:='B';
StringGrid1.Cells[3,0]:='C';
StringGrid1.Cells[4,0]:='D';
StringGrid1.Cells[5,0]:='E';
StringGrid1.Cells[0,1]:='A';
StringGrid1.Cells[0,2]:='B';
StringGrid1.Cells[0,3]:='C';
StringGrid1.Cells[0,4]:='D';
StringGrid1.Cells[0,5]:='E';
for x:=1 to 5 do StringGrid1.Cells[x,x]:='X';
MyPoint[1].x:=10;
MyPoint[1].y:=70;
MyPoint[1].name:='A';
MyPoint[2].x:=20;
MyPoint[2].y:=30;
MyPoint[2].name:='B';
MyPoint[3].x:=70;
MyPoint[3].y:=80;
MyPoint[3].name:='C';
MyPoint[4].x:=90;
MyPoint[4].y:=20;
MyPoint[4].name:='D';
MyPoint[5].x:=120;
MyPoint[5].y:=50;
MyPoint[5].name:='E';
DrawGraph;
koef:=50;
end;
procedure TForm1.FormPaint(Sender: TObject);
var
x,kx,ky:integer;
begin
for x:=1 to 5 do
begin
kx:=MyPoint[x].x+koef;
ky:=MyPoint[x].y+koef;
Form1.Canvas.Ellipse(kx,ky,kx+10,ky+10);
Form1.Canvas.TextOut(kx,ky-15,MyPoint[x].name);
end;
end;
procedure TForm1.StringGrid1SetEditText(Sender: TObject; ACol,
ARow: Integer; const Value: String);
begin
if ACol=ARow then
begin
StringGrid1.Cells[ACol,ARow]:='X';
Exit;
end;
if StringGrid1.Cells[ACol,ARow]=Value then
begin
StringGrid1.Cells[ARow,ACol]:= Value ;
DrawGraph;
end;
end;
procedure TForm1.BitBtn2Click(Sender: TObject); //main
var
a:array[1..5,1..5] of integer;
t,min,x,y,u,i,j,k,n:longint;
b,c:array[1..5] of integer;
begin
for i:=2 to 5 do
for j:=1 to i-1 do
if ((StringGrid1.Cells[j,i]<>'') and (StrtoInt(StringGrid1.Cells[j,i])>0)) then n:=i;
for i:=1 to 5 do
for j:=1 to 5 do
if (StringGrid1.Cells[i,j]='') or (StringGrid1.Cells[i,j]='X') then a[i,j]:=32000
else a[i,j]:=StrToInt(StringGrid1.Cells[i,j]);
for i:=1 to 5 do
begin
c[i]:=0;
b[i]:=0;
end;
k:=0;
u:=1;
c[1]:=1;
b[u]:=1;
while u<n do
begin
min:=32000;
for i:=1 to u do
if b[i]>0 then
begin
t:=b[i];
for j:=1 to n do
if (a[t,j]<min) and (c[j]=0) then
begin
min:=a[t,j];
y:=t;
x:=j;
end;
end;
inc(u);
b[u]:=x;
c[x]:=1;
k:=k+a[y,x];
DrawLine (x,y,2);
a[y,x]:=32000;
a[x,y]:=32000;
end;
Label2.Caption:='Ðåçóëüòàò: '+IntToStr(k);
end;
end.
Результат виконання :
Висновок : на основі проведеної лабораторної робити я ознайомився з алгоритмом Пріма для знаходження мінімальнї або максимальнї ваги графа. Та навчився розв'язувати задачі за допомогою цього алгоритма.
15.10.2013 11:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора