Задача остовных деревьев в k–связном графе (стр. 9 из 10)

Назовем новыми ребра графа 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