Розкладність графів. Квазігамільтонові Графи - реферат українською
Скінченний зв'язний граф 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) є квазігамільтоновим.
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) є квазігамільтоновим.
Скачати реферат Розкладність графів. Квазігамільтонові Графи
Схожі українські реферати
|
1. Реферат: Розкpиття загальнолюдських і моpальних цінностей у новелах Гpигоpія Косинки Загальнолюдські цінності: добpо, моpаль, спpаведливість... Саме пpагнучи підняти їх, Гpигоpій Косинка у своїх новелах показав pадощі, болі, пpагнення укpаїнського наpоду, його стpаждання. Захист пpава особистості на щастя - це одна із основ г... 2. Реферат: Розклад вектора за базисом Означення 8. Лінійно залежними називають вектори , якщо існує хоч би одне дійсне число (і = 1,2,…, n), що не дорівнює нулю і виконується рівність Означення 9. Лінійно незалежними називають вектори , якщо рівність (7) виконується тільки тоді, к... 3. Реферат: Розклад вектора за базисом. Означення . Лінійно незалежними називають вектори , якщо рівність (7) виконується тільки тоді, коли усі . В системі векторів число лінійно незалежних векторів дорівнює рангу матриці, яка складена з координат цих векторів. Дійсно, якщо систему ... 4. Реферат: Розклад феодалізму і генезис індустріального суспільства Література: І. Смирнов “Економічна історія” В. Мотильов “Економічна історія зарубіжних країн” Ф.Полянський “Економічна історія зарубіжних країн” Р. Горчаков “Економічна історія зарубіжних країн” Є. Паршаков “Економічний розвиток суспіл... 5. Реферат: Розклад феодалізму і становлення індустріального суспільства в країнах Західної Європи і США (ХVI-XVIII ст.) План 1. Основні аспекти господарського розвитку країни Західної Європи в період первісного нагромадження капіталу. 2. Основні аспекти становлення індустріального суспільства в країнах Західної Європи. 3. Економічні причини та наслідки колон... 6. Реферат: Розклад функцій в степеневий ряд. Достатні умови розкладу в ряд Тейлора. Застосування степеневих рядів до наближеного обчислення План • Ряди Тейлора і Маклорена • Достатні умови розкладу в ряд Тейлора • Приклади розкладу функцій в ряди • Біноміальний ряд • Обчислення означених інтегралів за допомогою рядів • Інтегрування диференціальних рівнянь за допомогою р... 7. Реферат: Розклад функцій в степеневий ряд. Достатні умовирозкладу в ряд Тейлора. Застосування степеневих рядів до наближеного обчислення План • Ряди Тейлора і Маклорена • Достатні умови розкладу в ряд Тейлора • Приклади розкладу функцій в ряди • Біноміальний ряд • Обчислення означених інтегралів за допомогою рядів • Інтегрування диференціальних рівнянь за допомогою рядів ... 8. Реферат: Розклад числа на прості множники Означення. Розкладом натурального числа n на прості множники (факторизацією числа) називається представлення його у вигляді n = , де pi – взаємно прості числа, ki ??1 . Задача перевірки числа на простоту є простішою за задачу факторизації. Тому ... 9. Реферат: Розкладання елементарних функцій в ряд Маклорена Рядом Маклорена функції f(x) називають степеневий ряд по степенях х, який можна дістати з ряду (38) при х0 = 0: (41) З п. 2.4 випливає таке правило розкладання функції в ряд: щоб функцію f(x) розкласти в ряд Маклорена потрібно: а) з... 10. Реферат: Розкладність графів. Врівноважені розбиття скінченних графів Розглянемо скінченний зв'язний граф Gr = (V,E) з множиною вершин V і множиною ребер E. Для довільних двох вершин x,yV позначимо через d(x,y) довжину найкоротшого шляху від x до y. Для довільних вершини xV, підмножини AV і невід'ємного цілого числа m ...
11. Реферат: Розкладність графів. Квазігамільтонові Графи
Скінченний зв'язний граф 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. ... 12. Реферат: Розкладність графів. Квазіцикли і квазіпромені Послідовність x1,x2,…,xk різних вершин зв'язного графа Gr(V,E) називається квазіциклом, якщо d(x1,x2) 3, d(x2,x3) 3,…, d(xk-1,xk) 3, d(xk,x1) 3. В кожному скінченному зв'язному графі існує квазіцикл, що проходить через кожну його вершин... 13. Реферат: Розкладність графів. Комбінаторні розміри підмножин графів і груп Застосуємо результати попереднього параграфу до кульових структур графів і груп. Теорема 1 Якщо множину вершин V довільно зв'язного графа Gr(V,E) розбито на скінченне число підмножин V=V1 V2Vn, то принаймні одна підмножина Vi розбиття має ... 14. Реферат: Розкладність графів. Морфізми кульових структур груп і графів Позначимо через I граф з множиною вершин N={1,2…} і множиною ребер E={(1,2),(2,3),…}. В цьому параграфі охарактеризовано кульові B структури графів і груп, для яких справедливе одне з таких співвідношень. B B(I), B(I) B, B(I) B. Нехай Gr1(V1... 15. Реферат: Розкладність графів. Хроматичні і калейдоскопічні числа Нехай Gr(V,E) - граф, k - кардинал. Правильним k-розфарбуванням графа Gr(V,E) називається розфарбування : Vk, таке що будь-які дві суміжні вершини різнокольорові. Хроматичним числом графа Gr називається найменший кардинал k, для якого існує п... 16. Реферат: Розкол у ОУН. Наслідки розколу Друга світова війна повністю змінила українську політичну ситуацію як в Україні так і поза нею. На Україні, окрім ОУН, зникли всі політичні партії. Керівники цих партій, які перебували в еміграції не могли вести ніякої політичної діяльності. У Німечч... 17. Реферат: Розкол християнської церкви 1054 року Це надзвичайно складний історичний факт сягає своїм минулим ще в античний період. Рим виховав у своїх громадян почуцття переваги над усіма. Зачарування Римом не тільки збереглося в стародавніх народів, які прийняли зристиянство, але й перейшло до ва... 18. Реферат: Розкол Церкви 1054 року Розкол Церкви 1054 року Це надзвичайно складний історичний факт сягає своїм щн в античний період. Рим виховав у своїх громадян почуцття переваги над усіма. Зачарування Римом не тільки збереглося в стародавніх народів, які прийняли зристиянство, ал... 19. Реферат: Розкриття внутрiшнього свiту маленької людини в оповiданнi "Маленький грiшник" Михайла Коцюбинського Серед творiв Коцюбинського своєрiдне мiсце посiдає оповiдання "Маленький грiшник" (1893). У ньому змальовано життя знедолених дiтей мiста. В оповiданнi яскраво виявилась одна з особливостей стилю письменника: вмiння знаходити життєво правдивi, промов... 20. Реферат: Розкриття загальнолюдських і моральних цінностей у новелах Григорія Косинки Розкpиття загальнолюдських і моpальних цінностей у новелах Гpигоpія Косинки Загальнолюдські цінності: добpо, моpаль, спpаведливість... Саме пpагнучи підняти їх, Гpигоpій Косинка у своїх новелах показав pадощі, болі, пpагнення укpаїнського ... 21. Реферат: Розлади рухової і трофічної функції нервової системи (лекція) Лекція Розлади рухової і трофічної функції нервової системи Формування і регуляція рухової активності людини забезпечуються різними структурно-функціональними утвореннями нервової системи на різних рівнях її організації: а) кори великого мозку,... |
|