Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

(m1+1)+…+(mn+1)=(m1+m1+…+m1)+n[pic] (2)
Следовательно, в силу неравенства (2), и так как dG(z)[pic], остались неиспользованными еще хотя бы n-k ребер графа G, инцидентных вершине z.
Для дополнения каждого из оставшихся деревьев Tn+1, …, Tk до остовного дерева графа G требуется еще по одному ребру, инцидентному вершине z, причем это ребро можно выбрать произвольно. Таким образом, мы можем построить попарно k непересекающихся по ребрам отстовных дерева графа G.

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

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

[pic]).

Текст программы 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

Рекомендуем скачать другие рефераты по теме: реферат сила, скачать контрольную.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата