Ответ в теме: Найти Гамильтонов цикл в графе

      Комментарии к записи Ответ в теме: Найти Гамильтонов цикл в графе отключены
#1990

Для проверки условия Дирака нужно получить количество вершин графа (|V|).
Чтобы определить количество вершин, нужно посчитать длину соответствующего множества. Определим предикат, возвращающий вершину — либо начало, либо конец дуги, получим все вершины при помощи findall, а затем — преобразуем список во множество.

node(Node):-
  edge(Node, _Destination);
  edge(_Source, Node).
  
get_nodes(SetOfNodes):-
  findall(Node, node(Node), Nodes),
  list_to_set(Nodes, SetOfNodes).

Функция проверки теоремы Дирака требует чтобы количество вершин было больше трех, а минимальная степень вершины была равна половине мощности множества вершин:

diracs_theorem:-
  get_nodes(Nodes), 
  length(Nodes, NodesCount), NodesCount > 3, 
  Minimal_degree is NodesCount / 2, write(Minimal_degree), nl,
  is_minimal_degree(Minimal_degree).

Функция проверки того, что в графе нет вершин со степень меньше заданного значения перебирает все вершины, вычисляет их степень и сравнивает с заданным значением. Если найдена вершина, нарушающая условие — функция завершается неудачей.

is_minimal_degree(Minimal_degree):-
  node(Node), degree(Node, Degree), Degree < Minimal_degree, !, fail;
  !.

В силу того, что граф является неориентированным — запись edge(a, b) эквивалентна записи edge(b, a). Функция получает списки входящих и исходящих дуг, вычисляет сумму их длин — это и будет являться степенью вершины. Я исходил из предположения что дуги не повторяются, если это может нарушаться — необходимо списки смежных вершин сложить и преобразовать результат в множество.

degree(Node, Degree):-
  findall(Destination, edge(Node, Destination), DestinationNodes), 
  length(DestinationNodes, DestinationLength),
  findall(Source, edge(Source, Node), SourceNodes), 
  length(SourceNodes, SourceLength),
  Degree is DestinationLength + SourceLength.

Если условие Дирака выполняется — то граф всегда является гамильтоновым, но существуют гамильтоновы графы, для которых условие нарушается. Таким является граф на вашей картинке — он состоит из трех вершин, следовательно минимальная степень должна быть равна трем, но степень вершин b, c, e и f равна двум. Тем не менее существует путь b, c, d, e, a, f, содержащий все вершины по одному разу, т.е. являющийся гамильтоновым.