Глава 2. Гамільтона циклу
§1. Основні поняття і визначення
Якщо граф має простий цикл, що містить всі вершини графа по одному разу, то такий цикл називається Гамільтона циклом, а граф називається Гамільтона графом. Граф, який містить простий шлях, що проходить через кожну його вершину, називається полугамільтоновим. Це визначення можна поширити на орієнтовані графи, якщо шлях вважати орієнтованим.
Гамильтонов цикл не обов'язково містить всі ребра графа. Ясно, що гамільтоновим може бути тільки зв'язний граф і, що всякий гамільтонів граф є полугамільтоновим. Зауважимо, що гамильтонов цикл існує далеко не в кожному графі.
Будь-граф G можна перетворити в гамільтонів граф, додавши достатню кількість вершин. Для цього, наприклад, досить до вершин v1, ..., vp графа G додати вершини u1, ..., up і безліч ребер.
Ступенем вершини v називається число ребер d (v), інцидентних їй, при цьому петля враховується двічі. У разі орієнтованого графа розрізняють ступінь do (v) по вихідним дугам і di (v) - по вхідних.
§2. Умови існування Гамільтона циклу
На відміну від ейлерових графів, де є критерій для графа бути ейлеровим, для гамільтонових графів такого критерію немає. Більш того, завдання перевірки існування Гамільтона циклу виявляється NP-повною. Більшість відомих фактів має вигляд: «якщо граф G має достатню кількість ребер, то граф є гамільтоновим». Наведемо кілька таких теорем.
Теорема Дірака. Якщо в графі G (V, E) c n вершинами (n ≥ 3) виконується умова d (v) ≥ n / 2 для будь-якого v V, то граф G є гамільтоновим.
Від противного. Нехай G - НЕ гамильтонов. Додамо до G мінімальну кількість нових вершин u1, ..., un, поєднуючи їх з усіма вершинами G так, щоб G ': = G + u1 + ... + un був гамільтоновим.
Нехай v, u1, w, ..., v - гамільтонів цикл в графі G ', причому v G, u1 G', u1 G. Така пара вершин v і u1 в Гамільтона циклу обов'язково знайдеться, інакше граф G був би гамільтоновим. Тоді w G, w, інакше вершина u1 була б не потрібна. Більш того, вершина v несуміжних з вершиною w, інакше вершина u1 була б не потрібна.
Далі, якщо в циклі v, u1, w, ..., u ', w', ..., v є вершина w ', суміжна з вершиною w, то вершина v' несуміжних з вершиною v, так як інакше можна було б побудувати гамільтонів цикл v, v ', ..., w, w', ..., v без вершини u1, взявши послідовність вершин w, ..., v 'в зворотному порядку. Звідси випливає, що число вершин графа G ', що не суміжних з v, не менше числа вершин, суміжних з w. Але для будь-якої вершини w графа G d (w) ≥ p / 2 + n з побудови, в тому числі d (v) ≥ p / 2 + n. Загальна кількість вершин (суміжних і не суміжних з v) складає 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.
Теорема Оре. Якщо число вершин графа G (V, E) n ≥ 3 і для будь-яких двох несуміжних вершин u і v виконується нерівність:
d (u) + d (v) ≥ n і (u, v) E, то граф G - гамільтонів.
Граф G має гамільтонів цикл якщо виконується одна з наступних умов:
Умова Пошана: d (vk) ≥ k + 1 для k Умова Бонді: з 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) §3. Завдання пов'язані з пошуком гамільтонових циклів У ряді галузей промисловості виникає наступна задача планування. Потрібно зробити n продуктів, використовуючи єдиний тип апаратури. Апарат повинен бути переналаштувати після того як був проведений продукт pi (але до того як розпочато виробництво продукту pj), в залежності від комбінації (pi, pj). Вартість перенастроювання апаратури постійна і не залежить від продуктів, що виробляються. Припустимо, що ці продукти виробляються в безперервному циклі, так що після виробництва останнього з n продуктів знову поновлюється в тому ж фіксованому циклі виробництво першого продукту. Виникає питання про те, чи може бути знайдена циклічна послідовність виробництва продуктів pi (i = 1,2, ..., n), яка не потребує переналаштування апаратури. Якщо уявити цю задачу у вигляді орієнтованого графа, то відповідь на поставлене запитання залежить від того, чи має цей орієнтований граф гамільтонів цикл чи ні. Якщо не існує циклічної послідовності продуктів, що не вимагає перенастроювання апаратури, то яка повинна бути послідовність виробництва з найменшими витратами на перенастроювання, тобто вимагає найменшого числа необхідних перенастроювань? Таким чином ми розглянемо наступні два завдання. Завдання 1. Дан орієнтований граф G, потрібно знайти в G гамільтонів цикл (або все цикли), якщо існує хоча б один такий цикл. Завдання 2. Дан повний орієнтований цикл G, дуг якого приписані довільні ваги C = [cij], знайти такий гамильтонов цикл, який має найменший загальна вага. Слід зазначити, що якщо орієнтований граф G не повний, то його можна розглядати як повний орієнтований граф, приписуючи відсутнім дуг нескінченний вагу.Схожі статті