Пошук Гамільтоновго циклу в неорієнтованому графі

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

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

Більш раціональний підхід полягає в розгляді всіляких простих шляхів, що починаються в довільно обраній стартовій вершині до тих пір, поки не буде виявлений Гамільтонів цикл, або всі можливі шляху не будуть досліджені. По суті справи, мова теж йде про перебір перестановок, але в значно скороченому вигляді — якщо, наприклад, вершина не суміжні з вершиною , то всі перестановок, у яких на першому місці стоїть , а на другому , не досліджуються. Розглянемо цей алгоритм більш детально.

Графічне представлення алгоритму пошуку Гамільтонового циклу

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

  1. Для деякої вершини виявиться, що суміжних нових вершин не існує. В даному випадку необхідно виконати так звану процедуру повернення, яка полягає у видаленні останньої включеної в  вершини і додаванні до неї нової, суміжної з передостанньої вершиною. Якщо і в цьому випадку не існує ніякої нової вершини, то робиться наступний крок повернення і так далі.
  2. Шлях, який визначається послідовністю вершин, що складають множину , має довжину , де  — кількість вершин графа. В даному випадку необхідно припинити пошук і перевірити, чи в заданому графі існує неорієнтоване ребро що поєвднує перший і останній елемент множини . Якщо таке ребро існує, то Гамільтонів цикл знайдено. В іншому випадку, або у випадку, коли для заданого графа необхідно знайти всі Гамільтонові цикли — виконуємо процедуру повернення.

Відмітимо, що пошук закінчується, коли множина  складається з однієї вершини  і не існує ніякої нової вершини, якою можна було б доповнити (наступний крок повернення робить множину  порожньою). Це означає, що всі Гамільтонові цикли, якщо вони існують, знайдені.

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

gaimiltoniv_cykl291

Дерево шляхів для неорієнтованого графа

Пошук Гамільтонового циклу в неорієнтованому графі — приклад:

Знайти всі Гамільтонові ланцюги для неорієнтованого графа, представленого на наступному малюнку.

Неорієнтований граф задачі

Для цього, слідуючи розглянутому вище алгоритму, на першому кроці, необхідно вибрати стартову вершину. Нехай це буде вершина номер «1». Збережемо цю вершину в якості першого елемента для множини . Далі, скориставшись одним з інцидентних їй ребер, наприклад , переходимо у вершину номер «2» (множина  на даному етапі прийме наступного вигляду ). На наступному кроці, до  додаємо нову суміжну вершину до вершини «2». В результаті отримаємо . Продовжуючи аналогічні дії далі, множина  прийме наступного вигляду . Після цього, виконавши перевірку, на наявність неорієнтованого ребра між вершинами «5» та «1» приходимо до висновку, що один з Гамільтонових циклів для задаого графа знайдено.

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

Продовжуючи ітераційний процес далі, отримаємо ще два шляхи, а саме та і на цьому алгоритм пошуку Гамільтонового циклу можна завершити (подальше повернення приводить до порожньої множини). Як не важко переконатися, з допомогою шляху, отриманому на останній ітерації, також можна побудувати Гамільтонів цикл.

Пошук Гамільтонового циклу в неорієнтованому графі

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

Блок-схема алгоритму пошуку Гамільтонового циклу в неорієнтованому графі

gaimiltoniv_cykl271

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар