| Головна » Статті » Математика | [ Додати статтю ] |
Розкладність графів. Квазігамільтонові Графи - реферат українською
|
Скінченний зв'язний граф 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-графом. Проблема 1. Охарактеризувати qhc-графи. Проблема 2. Охарактеризувати qhp-графи. В цьому параграфі проблеми 1 та 2 розв'язано для дерев, доведено аналог теореми Дірака для для qhc-графів, а також розглянуто деякі варіанти проблеми 2 для нескінченних графів. Нехай T(V,E) - скінченне дерево, xV, B(x,1)={x,y1,y2,...,ym}. Після видалення вершини x і ребер {x,y1}, {x,y2},..., {x,ym} дерево T розпадається на дерева , , ... , з коренями y1, y2 ,..., ym . Множину цих дерев позначимо (x)={ , , ... , }. Лема 1. Нехай T(V,E)- скінченне дерево, xV, (x)=}, V( )1, V( ), ..., V( )1, V( ) ... = V( )=1. Якщо T - ghc-граф, то k2. Доведення. Припустимо супротивне k2 і зафіксуємо gh-цикл x=x0, x1, x2, ..., xn-1 в дереві T. 3 послідовності x0, x1, x2, ..., xn-1 викреслимо всі вершини, що не належать множині V( ) V( ) V( ). Одержану послідовність позначимо z1, z2, ..., zs. Припустимо для визначеності, що z1V( ). Якщо z1=y1, то необхідно z2, z3,.., zs V( ). Отже, z1y1. Виберемо максимальний індекс t{1,2,...,s}, такий що ztV( ). Очевидно, що zt=y1 і z1, z2, ..., ztV( ). Припустимо для визначеності, що zt+1V( ). Тоді необхідно zt+1=y2 і zt+1 , ..., zs V( ). Одержано суперечність з умовою V( ){z1, z2, ..., zs}. Теорема 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, що задовольняє індуктивному припущенню. Задача 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 . Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n. Якщо |B(x,1)| +1 для будь-якої вершини xV, то за теоремою Дірака [5, стор. 74] граф Gr(V,E) є гамільтоновим. Ми доведемо достатню ознаку квазігамільтоновості графа, що є аналогом цієї теореми Дірака. Теорема 5.2. Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n. Якщо |B(x,2)| +1 для будь-якої вершини xV, то граф Gr(V,E) є квазігамільтоновим. | |
| Переглядів: 537 | |
| Всього коментарів: 0 | |