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

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

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

Скінченний зв'язний граф 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}. Оскільки