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

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

Скінченний зв’язний граф 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, що задовольняє умову теореми. За
припущенням індукції в T( існує qh-цикл V1, V2, … Vs, такий що v1=x1,
v2=x2 . Тоді

x1, x0, y1,y2,…ym, v2 ,v3, … vs —

qh-цикл в дереві T, що задовольняє індуктивному припущенню.

Задача 1. Довести, що дерево T є гамільтоновим графом тоді і тільки
тоді, коли V(T)=1 або V(T)=2.

Задача 2. Нехай Gr(V1,E) — qhc-граф, |V|=n, r — дільник числа n.
Довести, що існує врівноважене розбиття V0, V1,…, Vr-1 , таке що

dist(V0, V1)( 2, dist(V1, V2)( 2,…, dist(Vr-2, Vr-1)( 2, dist(Vr-1, V1)(
2 .

+1 для будь-якої вершини x(V, то за теоремою Дірака [5, стор. 74] граф
Gr(V,E) є гамільтоновим. Ми доведемо достатню ознаку
квазігамільтоновості графа, що є аналогом цієї теореми Дірака.

+1 для будь-якої вершини x(V, то граф Gr(V,E) є квазігамільтоновим.

+1, то знайдуться такі вершини xi,xi+1, i({1,2,…,t-1} що xi+1(B(x1,2),
xi(B(xt,2). Перенумеруємо вершини x1,x2,…,xt в такому порядку

x1,xi+1,xi+2,…,xt,xi,xi-1,…,x2 .

Запишемо цю послідовність як z1,z2,…,zt і помітимо, що

d(z1,z2)(2, d(z2,z3)(2, …, d(zt-1,zt)(2, d(zt,z1)(2.

Припустимо, що ts, такий що vt(Tz. Тоді

{vt, vt+1, …}( {xn: n((}=(.

Одержано суперечність з тим, що послідовність {vn:n((} пробігає всю
множину вершин V.

Достатність. Нехай {xn:n((} — стовбур дерева T(V,E). Позначимо через T0
дерево з коренем x0, одержане видаленням з T(V,E) ребра {x0,x1}. Для
кожного n((, n>0 позначимо через Tn дерево з коренем xn, одержане
видаленням ребер {xn-1,xn}, {xn,xn+1}. Якщо |V(Tn)|=1, покладемо xn(=xn.
Якщо ж |V(Tn)|>1, зафіксуємо довільну вершину xn((V(Tn), суміжну з
вершиною xn. Позначимо kn=|V(Tn)|, n((. За теоремою 4.1 існують бієкції

f0:{1,2,…,k0}(V(T0), f0 (x0()=1, f0 (x0)=k0,

f1:{k0+1,k0+2,…,k0+k1}(V(T1), f1 (x1()=k0+1, f1 (x1)=k0+k1,

f2:{k0+k1+1,k0+k1+2,…,k0+k1+k2}(V(T2), f2(x2()=k0+k1+1, f2(x2)=k0+k1+k2,

………

що задовольняють умови

d(fn(i),fn(i+1))(3

для всіх n((, i({k0+k1+…+kn-1+1, k0+k1+…+kn}.

Визначимо бієкцію f:{1,2,…}(V за правилом f(i)=fn(i) тоді і тільки тоді,
коли i попадає в область визначення функції fn. Оскільки відстань в
графі T(V,E) між вершинами xn та xn( не перевищую 2, то f — шукана
нумерація.

Проблема 5. Охарактеризувати qr-дерева.

Наведемо одну необхідну і одну достатню ознаки qr-дерева.

Вершину x зв’язного графа Gr(V,E) назвемо вершиною локальної
скінченності (локальної нескінченності), якщо куля B(x,1) скінченна
(нескінченна).

Теорема 5. Нехай T(V,E) — qr-дерево, x,y(V, x1, x2, …, xn —
найкоротший шлях від x до y, x=x1 y=xn. Позначимо через Tx,Ty дерева з
коренями x, y, одержані видаленням ребер {x,x1}, {xn-1,y}. Якщо дерева
Tx, Ty нескінченні, то x2, x3,…, xn-1 — вершини локальної
нескінченності.

Доведення. Візьмемо квазіпромінь {vn: n((}, що проходить через усі
вершини дерева. Досить довести, що xn-1 — вершина локальної
нескінченності і застосувати індуктивні міркування. Припустимо
супротивне: куля B(xn-1,1) скінченна. Виберемо найменше натуральне число
t, таке що

B(xn-1,1)( {v0, v1, …,vt}, vt ( Ty, y( vt .

Тоді {vt+1 , vt+2 ,…}( Tx= (, що суперечить нескінченності дерева Tx.

Теорема 6. Якщо всі некінцеві вершини зліченного дерева T(V,E) є
вершинами локальної нескінченності, то T(V,E) — qr-дерево.

Доведення. Нехай {vn: n((} — нумерація вершин дерева. Квазіпромінь {yn:
n((}, що проходить через усі вершини дерева, побудуємо індуктивно.
Покладемо y0=v0. Припустимо, що вже визначено відрізок {y0,y1,…,yk}
квазіпроменя. Візьмемо першу вершину v({vn: n((}, через яку не пройшов
відрізок {y0,y1,…,yk}. Нехай z1, z2,…,zm — найкоротший шлях від yk до
v, yk =z1, v=zm. Оскільки z2, z3,…,zm-1 — вершини локальної
нескінченності, то можна вибрати вершини

yk+1( B(z2,1)\ {z1, z2, z3}, yk+2( B(z3,1)\ {z2, z3, z4},…,

yk+m-2( B(zm-1,1)\ {zm-2, zm-1, zm},

жодна з яких не належить відрізку {y0,y1,…,yk}. Продовжимо відрізок
{y0,y1,…,yk} приєднанням до його кінця відрізку {yk+1,yk+2,…,yk+m-2, v}.

Нехай Gr(V,E) — зліченний звязний граф. Бієкцію f: ((V назвемо
квазігамільтоновим променем (скорочено qh-променем), якщо d(f(i),
f(i+1))(2 для всіх i((. Граф, що допускає таку бієкцію назвемо
qhr-графом.

Проблема 6. Охарактеризувати qhr-дерева.

Наступна задача показує, що клас qhr-дерев значно вужчий за клас
qr-дерев.

Задача 3. Нехай T(V,E) — зліченне дерево, x(V,

)|>1.

не більше одного нескінченного дерева.

Розглянемо деякі алгоритмічні задачі і проблеми, пов’язані з
результатами останніх двох параграфів.

Задача 4. Спираючись на доведення теореми 4.1, вказати алгоритм
побудови повного квазіциклу в довільному скінченному звязному графі.
Оцінити його складність.

Задача 5. Вказати алгоритми, які по заданому скінченному дереву
визначають, чи є це дерево qhc-графом, qhp-графом? Оцінити їх
складності.

Відомо, що задача перевірки, чи є заданий скінченний звязний граф
гамільтоновим, являється NP-повною [6].

Проблема 7. Чи є NP-повною задача тестування скінченного звязного графа
на існування в ньому qh-циклу? qh-шляху?

Похожие записи