§ 5 КВАЗІГАМІЛЬТОНОВІ ГРАФИ

Скінченний зв'язний граф 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) назвемо квазігамільтоновим шляхом (скорочено q h-шляхом), якщо

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

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

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

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

В цьому параграфі проблеми 5.1 та 5.2 розв'язано для дерев, доведено аналог теореми Дірака для для qhc-графів, а також розглянуто деякі варіанти проблеми 5.2 для нескінченних графів.

Нехай T(V,E) - скінченне дерево, x Î V, B(x,1)={x,y1,y2,...,ym}. Після видалення вершини x і ребер {x,y1}, {x,y2},..., {x,ym} дерево T розпадається на дерева , , ... , з коренями y1, y2 ,..., ym . Множину цих дерев позначимо t(x)={, , ... , }.

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

x Î V, t(x)={, , ... ,,…,},

ï V()ï>1, ï V()ï>1, ..., ï V()ï>1, ï V()ï= ... = ï V()ï=1.

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

Доведення. Припустимо супротивне k>2 і зафіксуємо gh-цикл x=x0, x1, x2, ..., xn-1 в дереві T. 3 послідовності x0, x1, x2, ..., xn-1 викреслимо всі вершини, що не належать множині V() È V() È V(). Одержану послідовність позначимо z1, z2, ..., zs. Припустимо для визначеності, що z1 Î V(). Якщо z1=y1, то необхідно z2, z3,.., zs Î V(). Отже, z1 ¹ y1. Виберемо максимальний індекс t Î{1,2,...,s}, такий що zt Î V(). Очевидно, що zt=y1 і z1, z2, ..., zt Î V(). Припустимо для визначеності, що zt+1 Î V(). Тоді необхідно zt+1=y2 і zt+1 , ..., zs Î V(). Одержано суперечність з умовою

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

Теорема 5.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, що задовольняє індуктивному припущенню.

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

Задача 5.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 .

Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n. Якщо |B(x,1)|³+1 для будь-якої вершини x Î V, то за теоремою Дірака [5, стор. 74] граф Gr(V,E) є гамільтоновим. Ми доведемо достатню ознаку квазігамільтоновості графа, що є аналогом цієї теореми Дірака.

Теорема 5.2. Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n. Якщо |B(x,2)|³+1 для будь-якої вершини x Î V, то граф Gr(V,E) є квазігамільтоновим.

Доведення. Серед послідовностей y1,y2,…,yk різних вершин графа з умовою d(y1,y2)£2, d(y2,y3)£2,…, d(yk-1,yk)£2, виберемо послідовність x1,x2,…,xt максимальної довжини. Очевидно, що B(x1,2)Í{x1,x2,…,xt}, B(xt,2)Í{x1,x2, …, xt}. Оскільки t£n і |B(x1,2)|³+1, |B(xt,2)|³+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.

Припустимо, що t<n і виберемо вершину x Î V\{z1,z2 ,…,zt} і вершину zj, j Î{1,2,…,t} так, що d(zj,x)=1. Тоді відстань між сусідніми вершинами послідовності x,zj,zj+1,..,zt,z1,z2,..,zj-1 не перевищує 2, що суперечить максимальності t. Отже, t=n і z1,z2,..,zn - qh-цикл в графі Gr(V,E).

Загальну проблему 5.1 характеризації квазігамільтонових графів можна послабити до серії проблем про достатні ознаки квазігамільтоновості. Ось лише дві з них.

Проблема 5.3. Чи кожен ейлерів граф є квазігамільтоновим? Нагадаємо, що звязний граф називається ейлеревим, якщо локальний степінь кожної його вершини є парним числом.

Проблема 5.4. Чи кожен планарний граф є квазігамільтоновим?

Вершину x qhc-графа Gr(V,E) назвемо особливою, якщо існує qh-цикл x1,x2,…,xn в Gr, такий що x=x1 і d(x1,x2)=1. Якщо V={x}, то також вважаємо вершину x особливою. З доведення достатності в теоремі 5.1 випливає, що кожне qhc-дерево має особливу вершину. Для конструктивного описання qhp-дерев введемо дві операції приєднання.

Операція А. Нехай Gr1(V1,E1) - qhp-граф з qh-шляхом y1,y2,…ym. Візьмемо довільний qhc-граф Gr2(V2,E2), V1 Ç V2=Æ з особливою вершиною x і qh-циклом x=x1,x2,…,xn, d(x1,x2)=1. Побудуємо новий граф Gr(V1 È V2,E), де E=E1 È E2 È{(ym,x1)}. Зауважимо, що послідовність вершин

y1, y2, …, ym, x2, x1, xn, xn-1, … , x3

є qh-шляхом в графі Gr. Отже, в результаті операції приєднання А отримано новий qhp-граф Gr. Крім того, якщо Gr1, Gr2-дерева, то Gr - теж дерево.

Операція В. Нехай Gr(V,E) - qhp-граф з qh-шляхом y1,y2,…ym. Візьмемо довільну вершину yt, таку що d(y1,yt)=1. Виберемо довільний елемент x Ï V і розглянемо граф Gr¢(V È{x},E¢), де E¢=E È{(x,yt)}. Відмітимо, що послідовність

x, y1, y2,…, yt, yt+1 , …, ym

є qh-шляхом в графі Gr¢. Отже, в результаті операції приєднання В отримано новий qhp-граф Gr¢. Крім того, якщо граф Gr був деревом, то Gr¢ теж дерево.

Теорема 5.3. Скінченне дерево T(V,E) являється qhp-графом тоді і тільки тоді, коли T(V,E) є qhc-деревом, або T(V,E) можна отримати з деякого qhc-дерева послідовним застосуванням операцій А, В приєднання qhc-дерев.

Доведення. Достатність випливає з означення операцій приєднання А і В. Для доведення необхідності зафіксуємо деякий qh-шлях y1,y2,…,ym в дереві T(V,E) і розглянемо два випадки.

Випадок 1: Вершина y1 не є кінцевою вершиною дерева T(V,E). Виберемо максимальний індекс t Î{1,2,…,m}, такий що d(y1,yt)=1. Позначимо через дерева з коренями y1, yt, одержані видаленням з дерева T(V,E) ребра {y1,yt}. Якщо t=m, то T(V,E) - qhc-граф. Припустимо, що t<m. Очевидно, що {yt+1,…,ym}Ç V()=Æ. Значить, є qhp-графом з qh-шляхом yt, yt+1,…, ym. Крім того V()={y1,y2,…,yt-1}, d(y1, yt-1)=1. Отже, - qhc-дерево з особливою точкою y1. Залишилось помітити, що T(V,E) можна одержати операцію приєднання А до графа .

Випадок 2: Вершина y1 є кінцевою вершиною дерева T(V,E). Виберемо індекс t Î{1,2,…,m} так, що (y1,yt)Î E. Позначимо через дерево з коренем yt, одержане видаленням з T(V,E) ребра (y1,yt). Ясно, що V()={y2, y3,…, yt,…, ym} і - qhp-граф з qh-шляхом y2, y3,…, yt, yt+1 ,…, ym. Якщо t=2, то T(V,E) можна отримати з за допомогою операції А. Якщо ж t >2, то T(V,E) можна отримати з за допомогою операції В.

Нагадаємо, що нескінченний зв'язний граф Gr(V,E) називається qr-графом, якщо існує бієкція f:w®V, така що d(f(i),f(i+1))£3 для будь-якого i Î w.

Зв'язний граф називається локально скінченним, якщо локальний степінь кожної його вершини скінченний.

Стовбуром нескінченного дерева T(V,E) називається ін'єктивна послідовність {xn:n Î w} його вершин, що задовольняє такі умови

(і) d(xn, xn+1)=1 для всіх n Î w;

(іі) після видалення вершин {xn:n Î w} дерево T(V,E) розпадається на скінченні дерева.

Зауважимо, що не кожне нескінченне локально скінченне дерево має стовбур, але за лемою Кьоніга в кожному нескінченному локально скінченному дереві існує ін'єктивна послідовність вершин, що задовольняє умову (і).

Теорема 5.4. Нескінченне локально скінченне дерево T(V,E) являється qr-графом тоді і тільки тоді, коли T(V,E) має стовбур.

Доведення. Необхідність. Нехай {xn:n Î w} - ін'єктивна послідовність вершин з умовою d(xn,xn+1)=1, n Î w. Позначимо через U множину усіх вершин з V\{xn:n Î w}, суміжних з вершинами множини {xn:n Î w}. Для кожної вершини y Î U позначимо через Ty дерево з коренем y, одержане видаленням ребра (y,xm), де xm - вершина, суміжна з y. Припустимо, що знайдеться вершина z Î U, така що дерево Tz нескінченне. Знайдемо вершину xi, для якої {xi,z}Î E. За умовою теореми існує така нумерація {vn:n Î w} вершин дерева T(V,E) , що d(vn,vn+1)£3 для всіх n Î w. Виберемо індекс s Î w так, щоб B(xi,3)Í{v1,v2,…,vs}. Оскільки дерево Tz нескінченне, то знайдеться індекс t>s, такий що vt Î Tz. Тоді

{vt, vt+1, …}Ç {xn: n Î w}=Æ.

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

Достатність. Нехай {xn:n Î w} - стовбур дерева T(V,E). Позначимо через T0 дерево з коренем x0, одержане видаленням з T(V,E) ребра {x0,x1}. Для кожного n Î w, 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 Î w. За теоремою 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 Î w, 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.5. Охарактеризувати qr-дерева.

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

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

Теорема 5.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 Î w}, що проходить через усі вершини дерева. Досить довести, що xn-1 - вершина локальної нескінченності і застосувати індуктивні міркування. Припустимо супротивне: куля B(xn-1,1) скінченна. Виберемо найменше натуральне число t, таке що

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

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

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

Доведення. Нехай {vn: n Î w} - нумерація вершин дерева. Квазіпромінь {yn: n Î w}, що проходить через усі вершини дерева, побудуємо індуктивно. Покладемо y0=v0. Припустимо, що вже визначено відрізок {y0,y1,…,yk} квазіпроменя. Візьмемо першу вершину v Î{vn: n Î w}, через яку не пройшов відрізок {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: w®V назвемо квазігамільтоновим променем (скорочено qh-променем), якщо d(f(i), f(i+1))£2 для всіх i Î w. Граф, що допускає таку бієкцію назвемо qhr-графом.

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

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

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

, , …, Î t (x), |V()|>1, |V()|>1,…|V()|>1.

Якщо T(V,E) - qhr-граф, то k£ 4 і серед дерев , , …, не більше одного нескінченного дерева.

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

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

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

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

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