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

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

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

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

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

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

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

Доведення. Необхідність. Нехай {xn:n((} - ін'єктивна послідовність вершин з умовою d(xn,xn+1)=1, n((. Позначимо через U множину усіх вершин з V\{xn:n((}, суміжних з вершинами множини {xn:n((}. Для кожної вершини y(U позначимо через Ty дерево з коренем y, одержане видаленням ребра (y,xm), де xm - вершина, суміжна з y. Припустимо, що знайдеться вершина z(U, така що дерево 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, такий що 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}.