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

Теорема 7.1 позволяет редуцировать граф, не уменьшая реберной связности. Это открывает широкие возможности для построения различных конструкций. В наших конструкциях также использует последовательные разрезы графа по вершинам опирается на теорему 7.1.

Для построения нам также потребуется классический результат относительно минимально k-связных графов.

Теорема 7.2. Пусть степени всех вершин мультиграфа G(V, E) строго более k и (G)k. Тогда существует ребро eE такое, что (G-e)k.

Замечание. Впервые результат теоремы 7.2 для графов без кратных ребер доказал. Это доказательство обобщается на случай мультиграфа.

Перейдем к доказательству основного результата настоящей работы.

Теорема 7.3. Пусть мультиграф G(V, E) (в нем допускается наличие кратных ребер, но запрещены петли) таков, что (G)2k. Тогда у мультиграфа G существуют попарно k непересекающиеся ребра остовных дерева.

Доказательство. Будем доказывать теорему индукцией по количеству вершин в мультиграфе G₀. База для мультиграфа с двумя вершинами очевидна. Предположим, что теорема доказана для любого 2k- реберно связного мультиграфа, у которого меньше вершин, чем у G. По теореме 7.2, у графа G(V, E) существует остовный подграф G₀(V, E₀), такой, что (G₀)=2k и одна из его вершин zV имеет степень d(z)=2k. Очевидно, что граф G₀-z связен, следовательно, по теореме 7.1 существует разрез G графа G₀ по вершине z такой, что (G)2k. Если в графе G есть петли, то уберем их. Из условия (G)2k следует, что графа G₁, полученного из G в результате удаления петель, выполняется условие (G₁)2k.

Назовем новыми ребра графа G₁, добавленные при разрезе по вершине z. Пусть этo ребра e₁, …, e_m. Поскольку при построении разреза было добавлено k ребер, после чего были удалены петли, то mk. По индукционному предположению, у графа G₁ существуют непересекающиеся по ребрам остовные деревья T₁, T₂, …, T_k. Опишем метод построения по каждому из этих k деревьев остовного графа G. Все ребра, которые могут входить в деревья T₁, T₂, …, T_k, либо являются ребрами графа G, либо новыми ребрами. Пусть дерево T_i содержит m_i новых ребер, тогда

m₁+m₂+…+m_kmk (1)

Если дерево T_i не содержит ни одного нового ребра, то оно является подграфом мультиграфа G. Поскольку множество вершин дерева T_i содержит все вершины графа G, кроме z, то добавив к T_i вершину z и любое ребро графа G с концом в z, мы получим остовное дерево T'_i графа G. Отметим, что в этом случае для построения дерева T'_i потребовалось одно ребро графа G, инцидентное вершине z (причем это ребро можно выбрать произвольно).

Предположим, что m_i>0, то есть дерево T_i содержит новые ребра. Поставим в соответствие дереву T_i подграф T_i^* графа G, в котором каждое новое ребро xy дерева T_i заменим на два ребра xy и yz графа G. Каждое новое ребро в дереве T_i соответствует двум ребрам в графе T_i^*, при этом, к вершинам дерева добавляется вершина z. Следовательно, мы получили связный остовный подграф T_i^* графа G, в котором количество ребер на m_i-1 больше, чем в дереве. Таким образом, в графе T_i^* ровно m_i-1 цикл, причем не трудно заметить, что каждый из этих циклов проходит через вершину z. Следовательно, из графа T_i^* можно удалить m_i-1 инцидентных вершине z ребер так, что получится отстовное дерево T_i^' графа G. В дерево T_i^' входит m_i+1 ребро, инцидентное вершине z. По построению очевидно, что при ij, m_i>0 и m_j>0 остовные деревья T_i^' и T_j^' графа не имеют общих ребер.

Пронумеруем k непересекающихся по ребрам остовных деревьев графа G таким образом, чтобы деревья T₁, …, T_n содержали новые ребра, а деревья T_n+1, …, T_k не содержали новых ребер (где 0). С помощью описанного выше способа построим по остовным деревьям T₁, …, T_n графа G₁ остовные деревья T'₁, …, T'_n графа G, никакие два из этих деревьев не будут иметь общих ребер. Всего при построении этих n деревьев использовано (m₁+1)+…+(m_n+1) ребер графа G, инцидентных вершине z. В силу неравенства (1), мы получаем, что

(m₁+1)+…+(m_n+1)=(m₁+m₁+…+m₁)+n (2)

Следовательно, в силу неравенства (2), и так как d_G(z), остались неиспользованными еще хотя бы n-k ребер графа G, инцидентных вершине z. Для дополнения каждого из оставшихся деревьев T_n+1, …, T_k до остовного дерева графа G требуется еще по одному ребру, инцидентному вершине z, причем это ребро можно выбрать произвольно. Таким образом, мы можем построить попарно k непересекающихся по ребрам отстовных дерева графа G.

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

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

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

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

Доказательство. Пусть T₁, T₂,…, T_k -остовные деревья графа G. По определению стягивания нетрудно заметить, что графы T^A₁, T^A₂,…, T^A_k связны и никакие два из них не имеют общих ребер.

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

Для n> определим граф Hⁿ, в котором каждую вершину а графа H заменим полным графом K_n (других вершин в Hⁿ нет). Для каждого ребра ab графа Н проведем в графе Hⁿ ребро, соединяющее какие-то две вершины из соответствующих a и b полных графов (такие ребра графа Hⁿ мы назовем главными). При этом, мы проведем главные ребра так, чтобы никакие два из них не имели общего конца (это возможно так, как 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. Был разработан алгоритм, который строит разрез по заданому графу. По данному алгоритму была написанна программа. Алгортм заключался в следующем: задается граф, по нем строится матрица смежности. В матрице суммируется строка и если при делении на два остаток от деления равен нулю, тогда данную вершину удаляют, а те вершины которые были смежные с ней соединяются между собой.

Размещено на Allbest.ru