Xreferat.com » Рефераты по математике » Задача остовных деревьев в k–связном графе

Задача остовных деревьев в k–связном графе

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

§8 Необходимость условия (G)2k.


Мы покажм необходимость условия (G)2k для выделения k попарно непересекающихся по ребрам остовных деревьев из графа G. Более того, при n>1 для любого n мы построим (2k-1)–вершинно связный граф Gn, у которого степени всех вершин более n, но среди любых k связных остовов графа Gn какие–то два имеют общее ребро. Таким образом, ослабление условия реберной 2k–связности нельзя «компенсировать», накладывая допoлнительно условия на минимальную степень вершины и условие вершинной (2k-1)–связности. Перейдем к построению серии примеров.

Определение.8.1. Пусть AV–множество из некотрорых вершин графа G(V, E). Определим граф GA с множеством вершин (VA) (где a). Удалим в графе G все ребра между вершинами из множеcтва А, объединим все вершины множемтва А в одну новую вершину а. Для любой вершины b, мы добавим ровно dG(b, A) ребер ab. Все вершины из VA и соединяющие их ребра в графе GA будут же, как и в графе G. Назовем построенный граф GA стягиванием графа G по множеству А.

Лемма 8.2. Пусть в графе G(V, E) есть k попарно непересекающихся по ребрам остовных дерева. Тогда для любого AV в графе GA также есть k попарно непересекающихся по ребрам остовных дерева.

Доказательство. Пусть T1, T2,…, Tk –остовные деревья графа G. По определению стягивания нетрудно заметить, что графы TA1, TA2,…, TAk связны и никакие два из них не имеют общих ребер.

Определние 8.3. Пусть граф H(V, E) не имеет кратных ребер, aV, n>dH(a). Пусть граф H получен из Н в результате замены вершины а на полный грaф Kn, причем все ребра, инцидентные вершине а в графе Н, в H будут из разных вершин соответствующего Н полного графа Kn.

Для n> определим граф Hn, в котором каждую вершину а графа H заменим полным графом Kn (других вершин в Hn нет). Для каждого ребра ab графа Н проведем в графе Hn ребро, соединяющее какие–то две вершины из соответствующих a и b полных графов (такие ребра графа Hn мы назовем главными). При этом, мы проведем главные ребра так, чтобы никакие два из них не имели общего конца (это возможно так, как n>).

Текст программы

unit diplom;


interface


uses

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

StdCtrls, Buttons, ExtCtrls, Menus, CheckLst, ActnList;


type

masiv = set of byte;

TForm1 = class(TForm)

BitBtn1: TBitBtn;

Image1: TImage;

Image2: TImage;

ComboBox1: TComboBox;

Label1: TLabel;


procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Image1MouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormActivate(Sender: TObject);

procedure ComboBox1Change(Sender: TObject);


private

{ Private declarations }

function Proverka(ind: byte): boolean;

procedure Newselect(ind: byte);

procedure Duga(ind:byte);

procedure Graph;


public

{ Public declarations }

end;


var


Form1: TForm1;i:integer;

b,b1,b2,b4:boolean;

Data: array[1..20] of record x1,y1:integer;end;

matr,matr_edit:array[1..40,1..40] of integer;

mas_x,mas_y : masiv;

x2,y2:integer;

implementation


{$R *.DFM}

//************************esli mouse najata*****************************

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

Shift: TShiftState; X, Y: Integer);

begin

canvas.MoveTo(x,y); x2:=x;y2:=y;

if (ssleft in Shift) then b:=true

else

if (ssRight in Shift) then b:=false else

end;

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

Shift: TShiftState; X, Y: Integer);

var k,k1:integer;

begin

if b then

begin

Canvas.Brush.Color := clRed;

canvas.Ellipse(x-10,y-10,x+10,y+10);

inc(i);

canvas.TextOut(x-3,y-6,inttostr(i));

Data[i].x1:=x;Data[i].y1:=y;

combobox1.items.Append(inttostr(i));

end

else

//risovanie peteli

if (x=x2) and (y=y2) then begin

for k:=1 to i do

if (sqr(X-data[k].x1)+sqr(Y-data[k].y1)<=100) then

begin

canvas.arc(data[k].x1,data[k].y1-30,data[k].x1+50,data[k].y1+30,

data[k].x1+5,data[k].y1+2,data[k].x1,data[k].y1);

break;end;

end

else

//--------------------------

for k:=1 to i do

if (sqr(X-data[k].x1)+sqr(Y-data[k].y1)<=100) then

begin

for k1:=1 to i do

if (sqr(x2-data[k1].x1)+sqr(y2-data[k1].y1)<=100) then begin

canvas.MoveTo(data[k1].x1,data[k1].y1);x2:=0;y2:=0;break;end;

canvas.Lineto(data[k].x1,data[k].y1);

matr[k1,k]:=1;matr[k,k1]:=1;

matr_edit[k1,k]:=1;matr_edit[k,k1]:=1;

matr[k,k]:=0;matr_edit[k,k]:=0;

Combobox1.visible:=true;

Label1.Visible:=true;

end;


end;


//*************************************************

procedure TForm1.FormActivate(Sender: TObject);

var j:integer;

begin

for i:=1 to 20 do

for j:=1 to 20 do

matr[i,j]:=0;

i:=0; x2:=0;y2:=0;

b1:=false;b2:=false; b4:=true;

combobox1.Items.Append('(None)');

Combobox1.visible:=false;

Label1.Visible:=false;

end;


//**provereaet esli vershina imeet kratnye riobra*********

function TForm1.Proverka(ind: byte): boolean;

var sum,i1,i2: byte;

begin

sum:=0;

for i1:=1 to i do

sum:=sum+matr[ind,i1];

if ((sum mod 2) =0) then

Proverka:=true else Proverka:=false;

end;

//*****delete vershinu********************************

procedure TForm1.Newselect(ind: byte);

var

ARect: TRect;

i1,i2:integer;

begin

with Image2.Canvas do

begin

CopyMode :=Whiteness;

ARect := Rect(0, 0, Image2.Width, Image2.Height);

CopyRect(ARect, Image2.Canvas, ARect);

CopyMode := cmSrcCopy;

//***************************

for i1:=1 to i do

for i2:=1 to i do

matr_edit[i1,i2]:=matr[i1,i2];

if proverka(ind) then

for i2:=1 to i do

begin

matr_edit[ind,i2]:=0;

matr_edit[i2,ind]:=0;

end;

if (proverka(ind)) then

begin

image2.Canvas.Brush.Color := clRed;

image2.canvas.pen.color:=clblack;

for i1:=1 to i do

for i2:=1 to i do

if matr_edit[i1,i2]=1 then

begin

image2.canvas.Ellipse(data[i1].x1-10,data[i1].y1-10,

data[i1].x1+10,data[i1].y1+10);

image2.canvas.TextOut(data[i1].x1-3,data[i1].y1-6,inttostr(i1));

image2.canvas.MoveTo(data[i1].x1,data[i1].y1);

image2.canvas.Lineto(data[i2].x1,data[i2].y1);

end;

end; end;end;

//----------------------------------------------------------

procedure TForm1.Graph;

var i1,i2:integer;

ARect: TRect;

begin

with Image2.Canvas do

begin

CopyMode :=Whiteness;

ARect := Rect(0, 0, Image2.Width, Image2.Height);

CopyRect(ARect, Image2.Canvas, ARect);

CopyMode := cmSrcCopy;


image2.Canvas.Brush.Color := clRed;

image2.canvas.pen.color:=clblack;

for i1:=1 to i do

for i2:=1 to i do

if matr[i1,i2]=1 then

begin

image2.canvas.Ellipse(data[i1].x1-10,data[i1].y1-10,

data[i1].x1+10,data[i1].y1+10);

image2.canvas.TextOut(data[i1].x1-3,data[i1].y1-6,inttostr(i1));

image2.canvas.MoveTo(data[i1].x1,data[i1].y1);

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. Был разработан алгоритм, который строит разрез по заданому графу. По данному алгоритму была написанна программа. Алгортм заключался в следующем: задается граф, по нем строится матрица смежности. В матрице суммируется строка и если при делении на два остаток от деления равен нулю, тогда данную вершину удаляют, а те вершины которые были смежные с ней соединяются между собой.

49


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: