Задача остовных деревьев в k–связном графе
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
a>
image2.canvas.Lineto(data[i2].x1,data[i2].y1);
end; end; end;
//****soedineam dve sosednie vershiny***********************
procedure TForm1.Duga(ind:byte);
var
v,i2,a1,d1,a2,d2,a,b: integer;
R:double;
s_1:array[1..2] of integer;
begin
v:=1;
if proverka(ind) then
for i2:=1 to i do
begin
if ((matr[ind,i2]=1) and (ind<>i2)) then
begin
s_1[v]:=i2;inc(v);
end;
if v=3 then
begin
a2:=data[s_1[1]].x1;d2:=data[s_1[1]].y1;
a1:=data[s_1[2]].x1;d1:=data[s_1[2]].y1;
a:=round((sqr(a1)+sqr(d1)-sqr(a2)-sqr(d2))/(2*(a1+d1-a2-d2)));
b:=a;
R:=sqrt(sqr(a2-a)+sqr(d2-b));
image2.canvas.pen.color:=clblue;
image2.Canvas.arc(round(a-R),round(a-R),round(a+R),round(a+R),a1,d1,a2,d2);
v:=1;
end;
end;end;
//*******vybor vershin************************************
procedure TForm1.ComboBox1Change(Sender: TObject);
begin
if combobox1.ItemIndex = 0 then
Graph
else
begin
newselect(combobox1.ItemIndex);
duga(combobox1.ItemIndex); end;
end;
end.
Вывод Целью моей дипломной работы была исследовать задачу на построение разреза в графе по вершине z. Был разработан алгоритм, который строит разрез по заданому графу. По данному алгоритму была написанна программа. Алгортм заключался в следующем: задается граф, по нем строится матрица смежности. В матрице суммируется строка и если при делении на два остаток от деления равен нулю, тогда данную вершину удаляют, а те вершины которые были смежные с ней соединяются между собой.