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

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

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

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


Реферат на тему:
Розкладність графів. Квазігамільтонові Графи
Скінченний зв'язний граф 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)- скінченне дерево,
x V, (x)={ , , ... , ,…, },
V( ) 1, V( ) 1, ..., V( ) 1, V( ) = ... = V( ) =1.
Якщо T - ghc-граф, то k 2.
Доведення. Припустимо супротивне k 2 і зафіксуємо gh-цикл x=x0, x1, x2, ..., xn-1 в дереві T. 3 послідовності x0, x1, x2, ..., xn-1 викреслимо всі вершини, що не належать множині V( ) V( ) V( ). Одержану послідовність позначимо z1, z2, ..., zs. Припустимо для визначеності, що z1 V( ). Якщо z1=y1, то необхідно z2, z3,.., zs V( ). Отже, z1 y1. Виберемо максимальний індекс t {1,2,...,s}, такий що zt V( ). Очевидно, що zt=y1 і z1, z2, ..., zt V( ). Припустимо для визначеності, що zt+1 V( ). Тоді необхідно 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) є квазігамільтоновим.
Доведення. Серед послідовностей y1,y2,…,yk різних вершин графа з умовою d(y1,y2) 2, d(y2,y3) 2,…, d(yk-1,yk) 2, виберемо послідовність x1,x2,…,xt максимальної довжини. Очевидно, що B(x1,2) {x1,x2,…,xt}, B(xt,2) {x1,x2, …, xt}. Оскільки t n і |B(x1,2)| +1, |B(xt,2)| +1, то знайдуться такі вершини xi,xi+1, i {1,2,…,t-1} що xi+1 B(x1,2), xi B(xt,2). Перенумеруємо вершини x1,x2,…,xt в такому порядку
x1,xi+1,xi+2,…,xt,xi,xi-1,…,x2 .
Запишемо цю послідовність як z1,z2,…,zt і помітимо, що
d(z1,z2) 2, d(z2,z3) 2, …, d(zt-1,zt) 2, d(zt,z1) 2.
Припустимо, що tЗагальну проблему 1 характеризації квазігамільтонових графів можна послабити до серії проблем про достатні ознаки квазігамільтоновості. Ось лише дві з них.
Проблема 3. Чи кожен ейлерів граф є квазігамільтоновим? Нагадаємо, що звязний граф називається ейлеревим, якщо локальний степінь кожної його вершини є парним числом.
Проблема 4. Чи кожен планарний граф є квазігамільтоновим?
Вершину x qhc-графа Gr(V,E) назвемо особливою, якщо існує qh-цикл x1,x2,…,xn в Gr, такий що x=x1 і d(x1,x2)=1. Якщо V={x}, то також вважаємо вершину x особливою. З доведення достатності в теоремі 5.1 випливає, що кожне qhc-дерево має особливу вершину. Для конструктивного описання qhp-дерев введемо дві операції приєднання.
Операція А. Нехай Gr1(V1,E1) - qhp-граф з qh-шляхом y1,y2,…ym. Візьмемо довільний qhc-граф Gr2(V2,E2), V1 V2= з особливою вершиною x і qh-циклом x=x1,x2,…,xn, d(x1,x2)=1. Побудуємо новий граф Gr(V1 V2,E), де E=E1 E2 {(ym,x1)}. Зауважимо, що послідовність вершин
y1, y2, …, ym, x2, x1, xn, xn-1, … , x3
є qh-шляхом в графі
Loading...

 
 

Цікаве