Алгоритмы поиска с возвратом для построения гамильтонова разложения $4$-регулярного мультиграфа

Рассматривается задача построения гамильтонова разложения регулярного мультиграфа на гамильтоновы циклы без общих рёбер. Известно, что проверка несмежности вершин в полиэдральных графах симметричного и асимметричного многогранников коммивояжёра является NP-полной задачей. С другой стороны, достаточное условие несмежности вершин можно сформулировать в виде комбинаторной задачи построения гамильтонова разложения $4$-регулярного мультиграфа. В статье представлены два алгоритма поиска с возвратом для проверки несмежности вершин в полиэдральном графе коммивояжёра и построения гамильтонова разложения $4$-регулярного мультиграфа: алгоритм на основе последовательного расширения простого пути и алгоритм на основе процедуры цепного фиксирования рёбер.
По результатам вычислительных экспериментов для неориентированных мультиграфов оба переборных алгоритма проиграли известному эвристическому алгоритму поиска с переменными окрестностями. Однако для ориентированных мультиграфов алгоритм на основе цепного фиксирования рёбер показал сопоставимые результаты с эвристиками на экземплярах задачи, имеющих решение, и лучшие результаты на экземплярах задачи, для которых гамильтонова разложения не существует.