Гамильтонов цикл — это закольцованный маршрут обхода каждой вершины заданного графа только один раз.
Гамильтонов цикл
Под гамильтоновым циклом в графе понимается маршрут прохождения всех вершин графа с однократным посещением каждой вершины. А гамильтонов путь — это не закольцованный путь, но также проходящий через все вершины графа.
Построение гамильтонова цикла считается очень сложной задачей, и на данный момент нет достоверного алгоритма решения такой проблемы. Скорее всего алгоритма, способного разрешить такую проблему, просто не существует, то есть эта задача принадлежит к кругу задач теории сложности алгоритмов, которые пока не решены. Можно сформулировать алгоритм её решения, который основан на переборе вариантов, но он будет иметь сложность порядка O(n!). Например, если пронумеровать все вершины графа, то номера вершин в их порядке в цикле Гамильтона, будут перетасованы некоторым образом от единицы до n. Можно перебрать все возможные n! вариантов и в каждом из них проверить принадлежность Гамильтонову циклу. Необходимо проверить, что все пары соседних вершин в анализируемом варианте и, кроме того, исходная и конечная вершины соединены рёбрами. Чтобы осуществить данный перебор вариантов, можно использовать, к примеру, популярный перебор с возвратом. Его возможно подкорректировать так, что будут отсеиваться однозначно неправильные случаи. К уже готовому участку пути добавятся только те вершины, которые имеют общее ребро с конечной вершиной и не были ранее посещены. Когда новая вершина добавлена к маршруту, нужно выполнить рекурсию. То есть запустить алгоритм из этой точки. Многие характеристики этого алгоритма аналогичны поиску в глубину, но есть и некоторое отличие. Отличие заключается в том, что если произошёл возврат на предыдущую вершину, то с точки возврата снимается метка о том, что вершина уже посещалась. Это позволяет алгоритму вернуться ещё раз на эту вершину, но из другой точки. Если для данного графа существует гамильтонов путь, то это однозначно случится, так как он проходит через все вершины.
Приведём пример. Предположим, что количество вершин в графе равно n и они нумеруются от нулевой до n−1, а граф может быть определён матрицей смежности А. В переменной Path расположен перечень вершин, вошедших в искомый маршрут. Функция hamilton получает как параметры нумерацию вершин, добавленных к маршруту, и делает возврат значения true, если прокладка гамильтонова пути выполнена. Если этого не произошло, то выполняется возврат признака false. Если путь успешно построен, то его сохраняют в переменной Path.
Алгоритм на языке С++
Рисунок 1. Программа. Автор24 — интернет-биржа студенческих работ
Алгоритм на языке PYTHON
Рисунок 2. Программа. Автор24 — интернет-биржа студенческих работ
Функция Hamilton в начале записывает вершину curr как конечную в списке Path. В случае равенства длины списка величине n, то есть все вершины вошли в путь Path, осуществляется проверка наличия ребра между исходной и конечной вершиной, и если это ребро обнаружено, то возвращается True (цикл найден). Это нужно только при построении гамильтонова цикла, если ищется путь, данная проверка не нужна. В случае отсутствия этого ребра, последняя вершина удаляется из Path и возвращается значение False (искомого цикла нет). Если длина списка меньше n, заносится метка посещения вершины curr, и процедура поиска пути идёт дальше. Последовательно осуществляется проход через все остальные вершины next и если есть соединение ребром вершин next и curr, при условии не посещения ранее вершины next, то выполняется рекурсия алгоритма из вершины next для нахождения пути к этой вершине. В случае завершения рекурсии из вершины next возвратом True, то алгоритм тоже возвращает True. Маршрут построен.
