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. Теорема доведена.