UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75838
останнє поновлення: 2016-12-03
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваРозкладність графів. Квазігамільтонові Графи (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось1384
Скачало342
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Розкладність графів. Квазігамільтонові Графи

 

Скінченний зв'язний граф Gr(V,E) з множиною вершин V=V(Gr) і множиною

ребер E=E(Gr), називається гамільтоновим, якщо існує така нумерація f:

{1,2,...,n}(V множини його вершин, що

 

d(f(1),f(2))=d(f(2),f(3))=...=d(f(n-1),f(n))=d(f(n),f(1))=1.

 

При цьому послідовність f(1),f(2),…,f(n) називається гамільтоновим

циклом. Задача характеризації гамільтонових графів - одна з найвідоміших

нерозв'язаних проблем теорії графів (див. [5, стор. 85], [12, стор.

72]).

 

За теоремою 4.1 множину вершин довільного скінченного звязного графа

Gr(V,E) можна занумерувати f: {1,2,...,n}(V так, що

 

d(f(1),f(2))(3, d(f(2),f(3))(3, ..., d(f(n-1), f(n))(3, d(f(n), f(1))(3.

 

Послідовність вершин f(1),f(2),…,f(n) називається повним квазіциклом

графа. У зв'язку з цим твердженням природно виникають такі означення і

проблеми.

 

Означення 1. Нумерацію f: {1,2,...,n}(V множини вершин скінченного

зв'язного графа Gr(V,E) назвемо квазігамільтоновим циклом (скорочено

qh-циклом), якщо

 

d(f(1),f(2)) (2, d(f(2),f(3)) (2, ..., d(f(n-1),f(n)) (2, d(f(n),f(1))

(2.

 

Граф, що допускає таку нумерацію вершин назвемо квазігамільтоновим

графом (скорочено qhc-графом).

 

Означення 2. Нумерацію f: {1,2,...,n}(V множини вершин скінченного

зв'язного графа Gr(V,E) назвемо квазігамільтоновим шляхом (скорочено

qh-шляхом), якщо

 

d(f(1),f(2))(2, d(f(2),f(3))(2, ..., d(f(n-1),f(n))(2.

 

Граф, що допускає таку нумерацію вершин, назвемо qhp-графом.

 

Проблема 1. Охарактеризувати qhc-графи.

 

Проблема 2. Охарактеризувати qhp-графи.

 

В цьому параграфі проблеми 1 та 2 розв'язано для дерев, доведено аналог

теореми Дірака для для qhc-графів, а також розглянуто деякі варіанти

проблеми 2 для нескінченних графів.

 

}.

 

Лема 1. Нехай T(V,E)- скінченне дерево,

 

},

 

)(=1.

 

Якщо T - ghc-граф, то k(2.

 

). Одержано суперечність з умовою

 

)({z1, z2, ..., zs}.

 

Теорема 1. Скінченне дерево T(V,E) являється qhc-деревом, тоді і тільки

тоді, коли існує такий шлях x0, x1, ...,xd, що всі вершини з множини V\

{ x0, x1, ...,xd} є кінцевими вершинами дерева.

 

Доведення. Необхідність. Нехай d - діаметр дерева, тобто відстань між

двома найбільш віддаленими його вершинами x0, xd. Позначимо через x0,

x1, ...,xd найкоротший шлях від x0 до xd. Тоді

 

B(x0,1)={x0,x1}, B(xd,1)={xd-1, xd}

 

і кожна вершина з множин

 

B(x1,1)\{x0,x1,x2}, B(xd-1,1)\{xd-2,xd-1,xd}

 

є кінцевою. Візьмемо довільний індекс i({2,3,...,d-2}. Оскільки

 

(B(xi-1,1)(( 3, (B(xi+1,1)( (3,

 

то за лемою 5.1 кожна вершина з множини B(xi,1)\{xi-1,xi,xi+1} є

кінцевою вершиною дерева.

 

Достатність. Для d=0 теорема очевидна: будь-яка нумерація множини V є

qh-циклом. Припустимо, що d>0 і індукцією по d доведемо існування

qh-циклу z0, z1,…, zn-1, такого що z0=x0, z1=x1. Можна вважати, що в

умові теореми x0, xd-кінцеві вершини дерева. Для d=1 покладемо z0=x0,

z1=x1. Нехай d>1 і B(x1,1)={x0,x1,x2,y1,y2,…ym}. Видалимо вершини

x0,y1,y2,…ym і ребра {x0,x1}, {x1,y1}, {x1,y2},… {x1,ym}. Одержимо

дерево T( з шляхом x1,x2,…,xd, що задовольняє умову теореми. За

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ