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

(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.

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

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

Проблема 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( теж дерево.

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

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

.

за допомогою операції В.

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