Задача остовных деревьев в k–связном графе
§8
Необходимость
условия
(G)
2k.
Мы
покажм необходимость
условия
(G)
2k
для выделения
k
попарно непересекающихся
по ребрам остовных
деревьев из
графа G.
Более того, при
n>1
для любого n мы
построим
(2k-1)–вершинно
связный граф
Gn,
у которого
степени всех
вершин более
n, но среди любых
k
связных остовов
графа Gn
какие–то два
имеют общее
ребро. Таким
образом, ослабление
условия реберной
2k–связности
нельзя «компенсировать»,
накладывая
допoлнительно
условия на
минимальную
степень вершины
и условие вершинной
(2k-1)–связности.
Перейдем к
построению
серии примеров.
Определение.8.1.
Пусть A
V–множество
из некотрорых
вершин графа
G(V,
E). Определим
граф GA
с множеством
вершин (VA)
(где a
).
Удалим в графе
G все ребра
между вершинами
из множеcтва
А, объединим
все вершины
множемтва А
в одну новую
вершину а. Для
любой вершины
b
,
мы добавим
ровно dG(b,
A) ребер
ab. Все вершины
из VA
и соединяющие
их ребра в графе
GA
будут же, как
и в графе G.
Назовем построенный
граф GA
стягиванием
графа G
по множеству
А.
Лемма
8.2.
Пусть
в графе G(V, E) есть
k попарно непересекающихся
по ребрам остовных
дерева. Тогда
для любого A
V
в графе GA
также есть k
попарно непересекающихся
по ребрам остовных
дерева.
Доказательство. Пусть T1, T2,…, Tk –остовные деревья графа G. По определению стягивания нетрудно заметить, что графы TA1, TA2,…, TAk связны и никакие два из них не имеют общих ребер.
Определние
8.3.
Пусть граф H(V,
E)
не имеет кратных
ребер, a
V,
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. Был разработан алгоритм, который строит разрез по заданому графу. По данному алгоритму была написанна программа. Алгортм заключался в следующем: задается граф, по нем строится матрица смежности. В матрице суммируется строка и если при делении на два остаток от деления равен нулю, тогда данную вершину удаляют, а те вершины которые были смежные с ней соединяются между собой.