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

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

Назва:
Розкладність графів. Квазігамільтонові Графи
Тип:
Реферат
Мова:
Українська
Розмiр:
23,89 KB
Завантажень:
66
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3 
Скінченний зв'язний граф 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) - скінченне дерево, xV, 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.

Доведення. Припустимо супротивне k2 і зафіксуємо 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 для будь-якої вершини xV, то за теоремою Дірака [5, стор. 74] граф Gr(V,E) є гамільтоновим. Ми доведемо достатню ознаку квазігамільтоновості графа, що є аналогом цієї теореми Дірака.

Теорема 5.2. Нехай Gr(V,E) - скінченний зв'язний граф, |V|=n. Якщо |B(x,2)| +1 для будь-якої вершини xV, то граф Gr(V,E) є квазігамільтоновим.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3 



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

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок