ься полугамільтоновім, якщо існує ланцюг, що проходить через кожну його вершину рівно один раз.
Незважаючи на схожість у визначеннях ейлеровимі і гамільтонових графів, відповідно до теорії для цих класів графи сильно відрізняються.
До теорії гамільтонових графів відноситься і задача про бродячого торговця чи задача про комівояжера. У задачі про бродячого торговця мова йде про деяке районі, і торговця, котрий повинен відвідати певну кількість міст цього району. Відстані між містами відомі, і треба знайти найкоротший шлях, який проходить через всі міста і закінчується в початковому пункті.
Міста можна зображувати вершинами деякого графа, в якому кожній парі вершин приписана відстань. Мова йде про пошук Гамільтона циклу, для якого сума є мінімальною.
Оскільки розглядається кінцеве число вершин, то завдання вирішується (при невеликій кількості вершин) шляхом простого перебору. Ефективних алгоритмів для розв'язуваної цього завдання не створено, хоча цій проблемі присвячено багато досліджень.
Встановлено різні достатні умови Гамільтонових графа. Сформулюємо дві з них.
Теорема 3.1. (О.Оре, 1960). Якщо для будь-якої пари і несуміжних вершин графа з вершинами має місце нерівно
(3.1)
то граф Гамільтонових.
Нагадаємо, що -ступінь вершини, тобто число ребер, що виходять з вершини.
Доказ. Будемо доводити від протилежного. Припустимо, що існує негамільтоновий граф з вершинами, в якому для будь-якої пари несуміжних вершин і виконується умова (3.1). Додавання до графу нових ребер порушує умова (3.1). Позначимо через максимальний негамільтовий граф, тобто такий граф, приєднання до якого нового ребра перетворює граф на Гамільтонових. Очевидно, не може бути повним графом. Тому в існує пара несуміжних вершин і. Приєднання до ребра перетворює граф на гамільтонів чинності максимальної негамільтоновості. Таким чином, існує гамільтонова ланцюг. з'єднує і, і через все вершини (рис. 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. Таким чином, маємо:
+ p - 1=d (v) + d (V)? d (w) + d (v)? p/2 + n + p/2 + n=2n + p.
Отже, 0 n + 1, що суперечить тому, що n gt; 0. Теорема доведена.
3.3 Приклади гамільтонових графів
Приклад 3.1. Знайти всі гамільтовие цикли для графа, наведеного на рис.3. 5 [10]
Рис.3.5 Пошук всіх гамільтонових циклів для орієнтованого графа
Таблиця 3.1 Результати пошуку гамільтонових циклів
Приклад 3.2. Знайти найкоротші Гамільтона циклу в задачі «комівояжера» для 6-міст, розташованих по графу на рис.3.6 [10]
Рис.3.6 Графи при вирішенні задачі «комівояжера»
Результати розрахунків довжини «гамільтонових циклів» в задачі «комівояжера» (рис.3.6) наведені в табл.3.2
Таблиця 3.2 Результати розрахунків довжини «гамільтонових циклів»
Приклад 3.3. Покажіть, що граф, зображений на малюнку 3.7, не їсти гамільтоновим [11].
Рис. 3.7 прикладі не гамільтонового графа
