Сутність гамільтонових графів

3.1   Сутність гамільтонових графів

Ейлерові цикли характеризуються властивістю проходити по одному разу через кожне ребро графа, а гамільтонові цикли — через кожну вершину.

Назва гамільтонів граф виникла у зв язку з тим , що в 1859 році відомий ірландський математик сер Вільям Гамільтон випустив до продажу своєрідну іграшкову головоломку . ЇЇ основою частиною був правильний додекаедр, зроблений з дерева (рис.3.1). Це один з так званих правильних багатогранників: його граням є 12 правильних п’ятикутників, в кожній з його вершин сходиться три ребра. Кожна з вершин гамільтонового додекаедра була позначена назвою одного з крупних міст Земної кулі –Брюсель, Кантон, Делі, Лондон і так далі. Задача полягає в знаходженні шляху вздовж ребер додекаедра, який проходить через кожне місто в точності один раз. Гамільтонів цикл на додекаедрі не пок-риває, звичайно, всіх ребер додекаедра, бо в кожній вершині він проходить в точності по двох ребрах.

Рис.3.1. Гамільтонів цикл у додекаедрі [4]

3.2 Основні поняття та означення

Означення 3.1.

Зв’язний граф називається гамільтоновим графом , якщо існує замкнений ланцюг, який проходить через кожну вершину графа рівно один раз.

Означення.3.2 .

Зв’язний граф називається напівгамільтоновим , якщо існує ланцюг , який проходить через кожну його вершину рівно один раз.

Не дивлячись на подібність в означеннях ойлерових та гамільтонових графів, відповідно теорії для цих класів графів сильно відрізняються.

До теорії гамільтонових графів відноситься і задача про бродячого тор-говця, або задача про комівояжера. В задачі про бродячого торговця мова йде про деякий район, та торговця , який повинен відвідати певну кількість міст цього району. Відстані між містами відомі, і треба знайти найкоротший шлях , який проходить через всі міста і закінчується в початковому пункті.

Міста можна зображати вершинами деякого графа, в якому кожній парі вершин приписана відстань . Мова йде про пошук гамільтонового циклу , для якого сума  є мінімальною.

Оскільки розглядається скінченне число вершин , то задача розв’язана (при невеликій кількості вершин) шляхом простого перебору. Ефективних алго-ритмів для розв’ язання цієї задачі не створено, хоча цій проблемі присвячено багато досліджень.

Встановлено різні достатні умови гамільтоновості графа . Сформулюємо дві з них.

Теорема 3.1.( О.Оре , 1960). Якщо для будь-якої пари  і несуміжних вершин графа  з  вершинами  має місце нерівніть

 (3.1)

то граф  гамільтонів.

Нагадаємо , що  степінь вершини  , тобто число ребер , які виходять з вершини  .

Доведення.

Будемо доводити від супротивного. Припустимо , що існує негамільтонів граф з  вершинами, в якому для будь-якої пари несуміжних вершин  і  виконується умова (3.1). Додавання до графа нових ребер не порушує умову (3.1). Позначимо через  максимальний негамільтонів граф , тобто таrий граф , приєднання до якого нового ребра перетворює граф на гамільтонів. Вочевидь,  не може бути повним графом, бо повний граф гамільтонів. Тому в  існує пара несуміжних вершин  і  . Приєднання до  ребра  перетворює граф  на гамільтонів в силу максимальної негамільтоновості . Таким чином , існує гамільтонів ланцюг. який сполучає  і  , він проходить через всі вершини ( рисунок 3.2)

Рис. 3.2. Гамільтонів ланцюг (1)

Оточимо кожну з , які суміжні з , кружечком, і вершину , яка лежить лівіше, квадратиком так, як зображено на рисунку, поданому нижче:

Рис. 3.3. Гамільтонів ланцюг(2)

 з цих  вершин оточені кружечком;

 з цих  вершин оточені квардатиком;

- не оточені квадратиком.

Зазначимо , що в силу умови теореми

Звідси випливає , що вершина  суміжна з деякою вершиною, яка оточена квадратиком . Таким чином , виходить , що граф  має гамільтонів цикл , зображений на рисунку 3.4

Рис.3.4. Гамільтонів ланцюг(3)

Отже прийшли до суперечності . Теорема доведена.

З теореми 3.1 випливає наступна теорема.

Теорема 3.2 (Г.Дірака, 1952) Якщо для будь-якої вершини  графа  з вершинами  виконується нерівність , то граф  гамільтонів.

Доведення. Від супротивного. Нехай — не гамільтонів. Додамо до  мінімальну кількість нових вершин , … ,, з'єднуючи їх з усіма вершинами  так, щоб :=  + + … + був гамільтонів.

Нехай , , , … ,— гамільтонів цикл у графі , причому  ,  ,  . Така пари вершин  і  у гамільтоновому циклі обов'язково знайдеться, інакше граф  був би гамільтонов. Тоді  ,   {,…,},інакше вершина  була б не потрібна. Більше того, вершина несуміжна з вершиною , інакше вершина була б не потрібна.

Далі, якщо в циклі , , , … ,,, … , є вершина , суміжна з вершиною w, те вершина v’ несуміжна з вершиною v, тому що інакше можна було б побудувати гамільтонов цикл ,, … ,,, … , без вершини , взявши послідовність вершин , … , у зворотному порядку. Звідси треба, що число вершин графа , не суміжних з , не менш числа вершин, суміжних з . Але для будь-якої вершини  графа  d() ≥ p/2+n по побудові, у тому числі d()  p/2+n. Загальне число вершин (суміжних і не суміжних з ) становить n+ p-1. Таким чином, маємо:

n+ p-1 = d(v)+d(V) ≥ d(w)+d(v) ≥ p/2+n+p/2+n = 2n+p.

Отже, 0  n+1, що суперечить тому, що n > 0. Теорема доведена.