§ 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) назвемо квазігамільтоновим
шляхом (скорочено qh-шляхом),
якщо
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-шляху?