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

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

В этой теме 2 ответа, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 2 мес. назад.

  • Автор
    Сообщения
  • #1987

    questioner
    Участник

    Необходимо проверить что граф имеет гамильтонов цикл и если имеет — найти любой из них (их может быть несколько).
    гамильтонов цикл — это замкнутый путь в графе, который включает все вершины графа по одному разу.

    Проверить наличие гамильтонова цикла в графе G(V, E) из V вершин и E ребер можно при помощи теоремы Дирака, которая утверждает, что если в неориентированном графе из более чем трех вершин, минимальная степень вершины больше (|V|)/2 — то граф является гамильтоговым.

    Пример гамитонова графа:
    Гамильтонов граф

    Нужна программа на языке Prolog, которая выполнит проверку по теореме Дирака, а затем найдет гамильтонов цикл.

  • #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, содержащий все вершины по одному разу, т.е. являющийся гамильтоновым.

  • #2011

    Чтобы найти гамильтонов цикл на Prolog можно чуть-чуть изменить правило поиска пути в глубину.
    В статье описывается ориентированный граф, поэтому нужно правило, проверяющее существование ребра (без учета направления):

    exist_edge(From, To):-
      edge(From, To); 
      edge(To, From).

    Нам не нужно собирать дуги — гораздо удобнее получить все вершины пути, поэтому именно вершины будем помещать в список, накапливающий путь:

    dfs(From, To, _, [From, To]):-
      exist_edge(From, To).
    dfs(From, To, Buffer, [From|Path]):-
      exist_edge(From, X),
      not(member(X, Buffer)),
      dfs(X, To, [From|Buffer], Path).

    Правило ищет путь между двумя вершинами, а не гамильтонов цикл. Если существует дуга, соединяющую текущую вершину с конечной — обе они добавляются к результату. В противном случае выбирается промежуточная вершина, в которую есть путь из текущей. Выполняется рекурсивный поиск пути из новой вершины. Все обработанные вершины добавляются в буфер чтобы исключить зацикливание. При выборе новой вершины выполняется проверка ее отсутствия в буфере. Так как нам нужно найти цикл — то в буфер изначально не помещается начальная вершина (это должно было бы делаться при вызове функции).

    hamiltonian_graph(Path):-
      get_nodes(Nodes), length(Nodes, NodesCount),
      dfs(Node, Node, [], Path),
      list_to_set(Path, PathNodesSet),
      length(PathNodesSet, NodesCount), !.

    Проверка наличия гамильтонового цикла сводится к поиску такого пути, что мощность множество его вершин совпадет с мощностью множества вершин всего графа.

Для ответа в этой теме необходимо авторизоваться.