Вступ, Гамільтонові графи, Основні визначення та результати, Теореми достатності гамільтонова
Метою моєї курсової роботи є:
1. Ознайомлення з основними поняттями, пов'язаними з гамільтоновими графами та циклами.
2. Розглянути завдання та методи відшукання гамільтонових циклів у графах
3. Створення програми знаходження гамільтонових циклів.
Насамперед, щоб внести ясність та уточнити термінологію, хотілося б дати визначення деяким елементам графа таким, як маршрут, ланцюг, цикл.
Маршрутом у графіG(V,E) називається послідовність вершин і ребер, що чергується: ,, … , , в якій будь-які два сусідніх елементи інцидентні. Якщо = , то маршрут замкнутий, інакше відкритий.
Якщо всі ребра різні, маршрут називається ланцюгом. Якщо всі вершини (а отже, ребра) різні, маршрут називається простим ланцюгом.
Замкнений ланцюг називається циклом; замкнутий простий ланцюг називається простим циклом. Граф без циклів називається ациклічним. Для орграфів ланцюг називається шляхом, а цикл - контуром.
Основні визначення та результати
Назва «гамільтонів цикл» походить від завдання «Кругосвітня подорож», запропонованої ірландським математиком Вільямом Гамільтоном у 1859 році. Потрібно було, вийшовши з вихідної вершини графа, обійти всі його вершини та повернутися у вихідну точку. Граф був укладання додекаедра, кожній із 20 вершин графа було приписано назву великого міста світу.
Якщо граф має простий цикл, що містить всі вершини графа по одному разу, такий цикл називаєтьсягамільтоновим циклом, а граф називаєтьсягамільтоновим графом. Граф, який містить простий шлях, що проходить через кожну його вершину, називається напівгамільтоновим. Це визначення можна поширити на орієнтовані графи, якщо шлях вважатиорієнтованим.
Гамільтонів цикл не обов'язково містить усі ребра графа. Зрозуміло, що гамільтоновим може бути лише зв'язковий граф і, що кожен гамільтонів граф є напівгамільтоновим. Зауважимо, що цикл гамільтонів існує далеко не в кожному графі.
Зауваження.
Будь-який графGможна перетворити на гамільтонів граф, додавши достатню кількість вершин. Для цього, наприклад, достатньо до вершинv1,…, vpграфаGдодати вершиниu1, …, upта безліч ребер vi, ui)> ui, vi+1).
Ступенем вершини v називається число реберd(v), інцидентних їй, при цьому петля враховується двічі. У разі орієнтованого графа розрізняють ступіньdo(v) по дугах іdi(v) - по вхідних.
На відміну від ейлерових графів, де є критерій для графа бути ейлеровим, для графів гамільтонів такого критерію немає. Понад те, завдання перевірки існування гамільтонова циклу виявляється NP-полной. Більшість відомих теорем мають вигляд: «якщо графGмає достатню кількість ребер, то граф є гамільтоновим». Наведемо кілька таких теорем.
Теореми достатності гамільтонова графа
Теорема (Дірак, 1952) 1. Якщо у простому графі зn? 3 вершинамиp(v)?n/2 для будь-якої вершиниv, то графGє гамільтоновим.
Зауваження Існує кілька доказів цієї широко відомої теореми, тут ми наводимо доказ Д. Дж. Ньюмана.
Доведення. Додамо до нашого графаkнових вершин, з'єднуючи кожну з них з кожною вершиною зG. Припускатимемо, щоk- найменша кількість вершин, необхідних для того, щоб отриманий графGстав гамільтоновим. Потім,вважаючи, щоk> 0, прийдемо до суперечності.
Нехайv>p>w>…>vгамільтонів цикл у графіG, деv,w-- вершини зG, аp- одна з нових вершин. Тодіwне є суміжною зv, тому що в іншому випадку ми могли б не використовувати вершинуp, що суперечить мінімальностіk. Більше того, вершина, скажімо,w, суміжна вершиніw, не може безпосередньо слідувати за вершиноюv, суміжній вершиніv, тому що тоді ми могли б замінитиv>p>w>…>v>w>vнаv>v>…>w>w>…>v, перевернувши частину циклу, укладену міжwіv. Звідси випливає, що число вершин графаG, які не є суміжними зw, не менше числа вершин, суміжних зv(тобто одно щонайменше,n/2 +k); з іншого боку, очевидно, що число вершин графаG, суміжних зw, теж дорівнює щонайменшеn/2 +k. Оскільки жодна вершина графаGне може бути одночасно суміжної і не суміжної вершиніw, то загальна кількість вершин графаG, рівнаn+k, не менше, ніжn+ 2k. Це і є потрібне протиріччя.
Теорема (Оре) 2. Якщо число вершин графаG(V, E)n? 3 і для будь-яких двох несуміжних вершинuіvвиконується нерівність:
Граф G має гамільтонів цикл якщо виконується одна з наступних умов:
Умова Бонді: з d(vi)? i і d(vk)? k => d(vi) + d(vk)? n (k? i)
Умова Хватала: зd(vk)? k? n/2 => d(vn-k)? n k.
Далі відомо, що майже всі графи гамільтонові, тобто
деH(p) - безліч гамільтонових графів зpвершинами, аG(p) - - Багато всіх графів з p вершинами. Завдання відшукання гамільтонова циклу або еквівалентне завдання комівояжера є практично затребуваними, але для неї невідомий (і, швидше за все, не існує) ефективний алгоритм рішення.
Приклад графа, коли не виконується умова теореми Дірака, але граф є гамільтоновим.
N= 8;d(vi) = 3; 3? 8/2 = 4 не гамільтонів граф, але існує гамільтонів цикл:M= (1, 2, 3, 4, 5, 6, 7, 8, 1)