Гамільтона шляху і цикли
Гамільтоновим циклом (шляхом) називають простий цикл (шлях), що містить всі вершини графа. У графі, зображеному на рис. 8.1 зліва, гамільтоновим циклом є, наприклад, послідовність,,,,,. У графі, зображеному в центрі, ні гамільтонових циклів, але є Гамільтона шляху, наприклад,. У правом графі немає і гамільтонових шляхів.
Зовні визначення Гамільтона циклу схоже на визначення ейлерова циклу. Однак є кардинальна відмінність в складності рішення відповідних завдань розпізнавання і побудови. Ми бачили, що є досить простий критерій існування ейлерова циклу і ефективний алгоритм його побудови. Для гамільтонових же циклів (і шляхів) невідомо ніяких просто перевіряються необхідних і достатніх умов їх існування, а всі відомі алгоритми вимагають для деяких графів перебору великого числа варіантів.
Гамильтонов цикл являє собою, з комбінаторної точки зору, просто перестановку вершин графа. При цьому в якості початкової вершини циклу можна вибрати будь-яку вершину, так що можна розглядати перестановки з фіксованим першим елементом. Самий нехитрий план пошуку Гамільтона циклу полягає в послідовному розгляді всіх цих перестановок і перевірці для кожної з них, чи становить вона цикл в даному графі. Такий спосіб дій вже при не дуже великому числі вершин стає практично неможливим попри швидке зростання кількості перестановок - є! перестановок з елементів з фіксованим першим елементом.
Більш раціональний підхід полягає в розгляді всіляких простих шляхів, що починаються в довільно обраної стартовою вершині, до тих пір, поки не буде виявлений гамильтонов цикл або всі можливі шляху не будуть досліджені. По суті справи, мова теж йде про перебір перестановок, але значно скороченому - якщо, наприклад, вершина суміжна з вершиною, то все! перестановок, у яких на першому місці стоїть, а на другому, не розглядаються.
Розглянемо цей алгоритм докладніше. Будемо вважати, що граф заданий околицями вершин: для кожної вершини задано безліч вершин, суміжних з. На кожному кроці алгоритму є вже побудований відрізок шляху, він зберігається в стеці PATH. Для кожної вершини, що входить в PATH. зберігається безліч всіх вершин, суміжних з, які ще не розглядалися в якості можливих продовжень шляху з вершини. Коли вершина додається до шляху, безліч вважається рівним. Надалі розглянуті вершини віддаляються з цього безлічі. Черговий крок полягає в дослідженні околиці останньої вершини шляху PATH. Якщо і в є вершини, які не належать шляху, то одна з таких вершин додається до шляху. В іншому випадку вершина виключається з стека. Коли після додавання до шляху чергової вершини виявляється, що шлях містить всі вершини графа. залишається перевірити, суміжні чи перша і остання вершини шляху, і при позитивному відповіді видати черговий гамильтонов цикл.
Алгоритм 2. Пошук гамільтонових циклів
- вибрати довільно вершину
- whiledo
- if
- then взяти
- if вершина не перебуває у PATH
- then
- ifPATH містить всі вершини
- thenif суміжно з
- then видати цикл
- else видалити вершину з PATH
Цей алгоритм дуже схожий на алгоритм пошуку в глибину і відрізняється від нього по суті тільки тим, що відкрита вершина. коли вся її околиця досліджена, не закривається, а знову стає новою (виключається з стека). На початку все вершини нові. Процес закінчується, коли всі вершини знову стануть новими. Насправді це і є пошук в глибину. тільки не в самому графі, а в дереві шляхів. Вершинами цього дерева є всілякі прості шляхи, що починаються в вершині, а ребро дерева з'єднує два шляхи, один з яких виходить з іншого додаванням однієї вершини в кінці. На рис. 8.2 показані граф і його дерево шляхів з вершини.