WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

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

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

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) і розглянемо два випадки.
Випадок 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-граф. Припустимо, що t2, то T(V,E) можна отримати з за допомогою операції В.
Нагадаємо, що нескінченний зв'язний граф Gr(V,E) називається qr-графом, якщо існує бієкція f: V, така що d(f(i),f(i+1)) 3 для будь-якого i .
Зв'язний граф називається локально скінченним, якщо локальний степінь кожної його вершини скінченний.
Стовбуром нескінченного дерева 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}.
Нехай Gr(V,E) - зліченний звязний граф. Бієкцію f: V назвемо квазігамільтоновим променем (скорочено qh-променем), якщо d(f(i), f(i+1)) 2 для всіх i . Граф, що допускає таку бієкцію назвемо qhr-графом.
Проблема 6. Охарактеризувати qhr-дерева.
Наступна задача показує, що клас qhr-дерев значно вужчий за клас qr-дерев.
Задача 3. Нехай T(V,E) - зліченне дерево, x V,
, , …, (x), |V( )|>1, |V( )|>1,…|V( )|>1.
Якщо T(V,E) - qhr-граф, то k 4 і серед дерев , , …, не більше одного нескінченного дерева.
Розглянемо деякі алгоритмічні задачі і проблеми, пов'язані з результатами останніх двох параграфів.
Задача 4. Спираючись на доведення теореми 4.1, вказати алгоритм побудови повного квазіциклу в довільному скінченному звязному графі. Оцінити його складність.
Задача 5. Вказати алгоритми, які по заданому скінченному дереву визначають, чи є це дерево qhc-графом, qhp-графом? Оцінити їх складності.
Відомо, що задача перевірки, чи є заданий скінченний звязний граф гамільтоновим, являється NP-повною [6].
Проблема 7. Чи є NP-повною задача тестування скінченного звязного графа на існування в ньому qh-циклу? qh-шляху?
Loading...

 
 

Цікаве