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

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

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

{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, зафіксуємо довільну вершину xnV(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,yV, 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-дерево.