Найти Гамильтонову цепь в непрерывном графе - Prolog

Формулировка задачи:

Найти Гамильтонов цепи в непрерывном графе

Решение задачи: «Найти Гамильтонову цепь в непрерывном графе»

Листинг программы

гамильтонова_цепь(Граф, Путь) :-
  число_вершин(Граф, N),
  вершина(Граф, Начальная_вершина),
  гамильтонова_цепь_рекурсивно(Граф, N, 1, [Начальная_вершина], Путь).
  
гамильтонова_цепь_рекурсивно(_, N, N, Путь, Путь) :- 
  !.
гамильтонова_цепь_рекурсивно(Граф, N, K, Текущий_путь, Путь) :- 
  Текущий_путь = [Текущая_вершина|Хвост],
  ребро(Граф, Текущая_вершина, Новая_вершина),
  not(member(Новая_вершина, Текущий_путь)),
  K1 is K + 1,
  гамильтонова_цепь_рекурсивно(Граф, N, K1, [Новая_вершина | Текущий_путь], Путь).
  
гамильтонов_цикл(Граф, Путь) :-
  число_вершин(Граф, N),
  вершина(Граф, Начальная_вершина),
  !,  %% <- для гамильтонова цикла неважно, с какой вершины его начинать
  гамильтонов_цикл_рекурсивно(Граф, Начальная_вершина, N, 1, [Начальная_вершина], Путь).
  
гамильтонов_цикл_рекурсивно(Граф, Начальная_вершина, N, N, Путь, Путь) :- 
  !,
  ребро(Граф, Текущая_вершина, Начальная_вершина).
гамильтонов_цикл_рекурсивно(Граф, Начальная_вершина, N, K, Текущий_путь, Путь) :- 
  Текущий_путь = [Текущая_вершина|Хвост],
  ребро(Граф, Текущая_вершина, Новая_вершина),
  not(member(Новая_вершина, Текущий_путь)),
  K1 is K + 1,
  гамильтонов_цикл_рекурсивно(Граф, Начальная_вершина, N, K1, [Новая_вершина | Текущий_путь], Путь).

Объяснение кода листинга программы

Гамильтонова цепь в непрерывном графе - это последовательность вершин, которую можно пройти таким образом, что для каждой вершины она содержит все смежные вершины (вершины, связанные с данной ребрами).
В коде используется два метода: гамильтонова_цепь и гамильтонов_цикл.
Метод гамильтонова_цепь используется для поиска Гамильтоновой цепи в непрерывном графе.
Метод гамильтонов_цикл используется для поиска Гамильтонова цикла в непрерывном графе.
В методе гамильтонова_цепь_рекурсивно происходит рекурсивный вызов метода для каждой вершины, которую нужно посетить.
В методе гамильтонов_цикл_рекурсивно происходит рекурсивный вызов метода для каждой вершины, которую нужно посетить.
В обоих методах используется базовый случай, когда количество вершин равно количеству ребер в цикле.
В обоих методах используется условие, чтобы проверить, является ли текущая вершина ребра частью текущего пути.
Если текущая вершина является ребра, то происходит рекурсивный вызов метода с новым хвостом и новым количеством ребер.
Если текущая вершина является вершиной, то происходит рекурсивный вызов метода с новым хвостом и без изменения количества ребер.
Для гамильтонова цикла неважно, с какой вершины начинать, поэтому используется оператор !.
В обоих методах используется стек для хранения вершин, которые нужно посетить.
В обоих методах используется список для хранения пути.
Количество ребер в цикле не должно превышать количество вершин в графе.
Для гамильтонова цикла необходимо, чтобы начальная вершина была связана с каждой другой вершиной.
В обоих методах используется рекурсия для обхода всех вершин графа.
В обоих методах используется условие, чтобы проверить, является ли текущая вершина ребра частью текущего пути.
Если текущая вершина является ребра, то происходит рекурсивный вызов метода с новым хвостом и новым количеством ребер.
Если текущая вершина является вершиной, то происходит рекурсивный вызов метода с новым хвостом и без изменения количества ребер.
В обоих методах используется стек для хранения вершин, которые нужно посетить.