Построение k непересекающихся остовных деревьев.

 

Теорема 7.1. Пусть граф G(V, E) таков что (G)=k, а вершина z V не является точкой сочленения. Тогда существует такой разрез G^z графа G по вершине z, что для любых x,y V\{z} выполняется соотношение l(x, y, G^z)=l(x, y, G) и, в частности (G^z) (G).

Замечание. Доказательство обобщается на случай, когда вершина z –точка сочленения, но ни одно из ребер с концами в z не является мостом. В частности, при (G) 2 для любой вершины z существует разрез по z такой, что (G^z) (G).

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

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

Теорема 7.2. Пусть степени всех вершин мультиграфа G(V, E) строго более k и (G) k. Тогда существует ребро e E такое, что (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 и одна из его вершин z V имеет степень 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 ребер, после чего были удалены петли, то m k. По индукционному предположению, у графа G₁ существуют непересекающиеся по ребрам остовные деревья T₁, T₂, …, T_k. Опишем метод построения по каждому из этих k деревьев остовного графа G. Все ребра, которые могут входить в деревья T₁, T₂, …, T_k, либо являются ребрами графа G, либо новыми ребрами. Пусть дерево T_i содержит m_i новых ребер, тогда

m₁+m₂+…+m_k m k (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. По построению очевидно, что при i j, 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.

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

 

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

Определение.8.1. Пусть A V –множество из некотрорых вершин графа 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 попарно непересекающихся по ребрам остовных дерева. Тогда для любого A V в графе G^A также есть k попарно непересекающихся по ребрам остовных дерева.

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

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