Задача про гамільтонів шлях

Задача про гамільтонів шлях і задача про гамільтонів цикл - це задачі визначення, чи існує гамільтонів шлях або гамільтонів цикл у заданому графі (орієнтованому або неорієнтованому). Обидві задачі NP-повні[1].

Зв'язок задач про гамільтонів шлях і гамільтонів циклРедагувати

Існує просте відношення між задачами знаходження гамільтонового шляху і знаходження гамільтонового циклу. З одного боку, задача про гамільтонів шлях для графа еквівалентна задачі про гамільтонів цикл у графі H, отриманому з графа G шляхом додавання нової вершини і з'єднання її з з усіма вершинами графа G. Таким чином, пошук гамільтонового шляху не може бути істотно повільнішим (у гіршому випадку, як функція числа вершин), ніж пошук гамільтонового циклу. З іншого боку, задача про гамільтонів цикл для графа G еквівалентна задачі про гамільтонів шлях у графі H отриманому копіюванням однієї вершини v графа Gv), тобто, вершина v матиме той самий окіл, що й v, і додаванням двох допоміжних вершин степеня один, одна з яких з'єднана з v, а інша з v[2]. Задача про гамільтонів цикл є також окремим випадком задачі комівояжера, отриманої встановленням усіх відстаней між двома пунктами рівними 1, якщо вони суміжні, і 2 в іншому випадку. Після розв'язання задачі комівояжера слід перевірити, що повна відстань дорівнює n (якщо так, маршрут є гамільтоновим циклом, якщо ж гамільтонового циклу немає, найкоротший шлях буде довшим від цієї величини).

АлгоритмиРедагувати

Є n! різних послідовностей вершин, які можуть бути гамільтоновими шляхами в заданому графі з n вершинами (і їх стільки в повному графі), так що алгоритм повного перебору, який перебирає всі можливі послідовності, був би дуже повільним. Ранній точний алгоритм знаходження гамільтонового циклу в орієнтованому графі був алгоритмом перебору (алгоритм Мартелло)[3].

Процедура пошуку Франка Рубіна [4] розбиває ребра графа на три класи - ті, які повинні бути на шляху, ті, які шляху належати не можуть, і ребра, для яких рішення не прийнято. В процесі пошуку набір правил прийняття рішень класифікує ребра, для яких рішення не прийнято, і визначає, зупинитися чи продовжити пошук. Алгоритм розбиває граф на компоненти, які можуть бути оброблені окремо. Для вирішення завдання за час   може бути використаний алгоритм динамічного програмування Беллмана, Хелда і Карпа. У цьому методі для кожного набору S вершин і кожної вершини v з S визначається, чи існує шлях, що проходить через усі вершини S і закінчується у v. Для кожної пари (S, v) шлях існує тоді і тільки тоді, коли v має сусідню вершину w, таку що існує шлях для  , який можна отримати зі вже отриманої інформації динамічного програмування[5][6].

Андреас Б'єрклунд дає альтернативний підхід, який використовує принцип включення-виключення для скорочення числа гамільтонових циклів, що перебираються, і задача підрахунку циклів може бути розв'язана шляхом обчислення визначника деякої матриці. Використовуючи цей метод він показав як розв'язати задачу про гамільтонів цикл для довільних графів з n вершинами за допомогою алгоритму Монте-Карло за час  . Для дводольних графів цей алгоритм можна поліпшити до часу  [7].

Для графів з максимальним степенем 3 акуратний пошук з поверненням може знайти гамільтонів цикл (якщо такий існує) за час  [8].

Гамільтонові шляхи і цикли можна знайти за допомогою розв'язника SAT.

Зважаючи на складність розв'язування задач про гамільтонів шлях і цикл на звичайних комп'ютерах, вони вивчалися для нестандартних моделей обчислень. Наприклад, Леонард Адлеман показав, що задача про гамільтонів шлях може бути розв'язана за допомогою ДНК-комп'ютера. Використовуючи паралелізм, властивий хімічним реакціям, задача може бути розв'язана за допомогою декількох кроків хімічних реакцій, які лінійно залежать від числа вершин графа. Однак, це вимагає факторіального числа молекул ДНК, що беруть участь у реакції [9] .

Оптичне розв'язання гамільтонової задачі запропонував Ольтеан[10]. Ідея полягає у створенні подібної графу структури з оптичних кабелів і розщеплювачів променя, через яку проганяється промінь у порядку розв'язування задачі. Слабким моментом цього підходу є експоненціальне зростання необхідної енергії від числа вузлів.

СкладністьРедагувати

Задача знаходження гамільтонового циклу або шляху має складність FNP[en]. Аналогічна задача розв'язності - перевірити, чи існує гамільтонів цикл або шлях. Орієнтовані і неорієнтовані задачі про гамільтонів цикл були двома з 21 NP-повних задач Карпа. Вони залишаються NP-повними навіть для неорієнтованих планарних графів максимального степеня 3[11], для орієнтованих планарних графів з півстепенем входу і виходу, що не перевищує 2[12], для неорієнтованих планарних 3-регулярних двочасткових графів без мостів, для 3-зв'язних 3-регулярних двочасткових графів[13], підграфів квадратної решітки[14] і для кубічних підграфов квадратної решітки[15].

Однак, 4-зв'язні планарні графи завжди гамільтонові згідно з результатом Татта, а задача знаходження гамільтонового циклу в цих графах може бути розв'язана за лінійний час[16] шляхом обчислення так званого шляху Татта. Татт довів цей результат, показавши, що будь-який 2-зв'язний планарний граф містить шлях Татта. Шляхи Татта, в свою чергу, можна обчислити за квадратичний час навіть для 2-зв'язних планарних графів[17], що може бути використано для пошуку гамільтонових циклів і довгих циклів в узагальнених планарних графах.

Складаючи все разом, залишається відкритою задача, чи завжди 3-зв'язні 3-регулярні двочасткові планарні графи повинні містити гамільтонів цикл і якщо повинні, задача, обмежена цими графами НЕ буде NP-повною, див. статтю «Гіпотеза Барнетта».

У графах, в яких усі вершини мають непарний степінь, довід, пов'язаний з лемою про рукостискання, показує, що число гамільтонових циклів через фіксоване ребро завжди парне, так що, якщо дано один гамильтонів цикл, то й інший повинен існувати[18]. Однак, пошук цього іншого циклу не виглядає як проста обчислювальна задача. Пападімітріу визначив клас складності PPA[en], щоб зібрати разом задачі, подібні до цієї [19] .

ПриміткиРедагувати

ЛітератураРедагувати