Я пытаюсь решить проблему гамильтонова цикла.
Условие моей задачи:
Группа состоит из N человек. В ней у каждого ровно N/2 друзей. Дружба симметрична (если А — друг Б, то Б — друг А). У одного человека в группе есть книга (его номер X), которую все хотели бы прочитать, а затем обсудить с другими.
Необходимо определить способ передачи книги, при котором она посещала бы всех ровно один раз, переходя только от друга к другу, и, наконец, возвращалась бы своему владельцу.
То есть удовлетворяет условию теоремы Дирака.
На маленьких графиках мои решения работают правильно, но на больших графиках мое решение дает исключение ограничения времени.
Есть ли способ, как это можно решить быстрее, чем O (n!)?