Найти Эйлеров цикл в графе

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

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

    questioner
    Участник

    Нужна программа на языке Prolog, выполняющая поиск Эйлерова цикла в графе. Эйлеров цикл – это путь в графе, содержащий все дуги по одному разу. Я читал тему про поиск Гамильтонова цикла в графе, но не смог переделать код.

    Для графа, приведенного на рисунке таким путем является последовательность e->a->b->f->a->c->b->d->f->c->d->e.

    Вложения:
  • #2483

    При поиске Эйлерова цикла необходимо удалять пройденные дуги, т.к. второй раз по ним пройти все равно не получится, но за счет удаления возможно значительно оптимизировать программу. В связи с этим, ребра необходимо описывать как динамический предикат:
    :- dynamic edge/2.
    Если считать ребра неориентированными, то граф, соответствующий вашей картинке можно следующим образом:

    edge(a, b).
    edge(b, c).
    edge(c, d).
    edge(d, e).
    edge(e, a).
    
    edge(a, f).
    edge(b, f).
    edge(c, f).
    edge(f, d).
    
    edge(a, c).
    edge(b, d).

    В связи с тем, что ребра графа являются двунаправленными – для проверки существования ребра необходимо использовать предикат exist_edge, а при удалении ребра – выполнять попытку удаления ребра, направленного в противоположную сторону:

    remove_edge(From, To):-
      retract(edge(From, To)), !;
      retract(edge(To, From)).

    Алгоритм поиска в глубину при этом должен быть изменен:

    • для проверки существования ребра используется exist_edge;
    • пройденные ребра удаляются из графа, но если путь не подошел – то восстанавливаются для продолжения поиска с возвратами;
    • в связи с удалением ребер отпадает необходимость накапливать информацию о пройденных дугах (она была необходима для избежания зацикливания), а следовательно, становятся ненужными проверки принадлежности текущей вершины к списку пройденных.
    • dfs(From, To, [From, To]):-
        exist_edge(From, To).
      dfs(From, To, [From|Path]):-
        exist_edge(From, X),
        remove_edge(From, X),
        (
          dfs(X, To, Path);
          assert(edge(From, X)), fail
        ).

      В таком случае, поиск Эйлерова цикла в графе сводится к запуску поиска в ширину (из вершины Node в вершину Node, т.к. путь должен являться циклом), и проверки того, что найденный при поиске путь содержит все ребра:

      eulerian_graph(Path):-
        dfs(Node, Node, Path),
        
        findall(edge(From, To), edge(From, To), Edges),
        length(Edges, 1).

      Проверка пути заключается в сборе всех ребе и сравнения их количества с единицей (т.к. все остальные ребра при поиске будут удалены). При этом все ребра помещаются в список и определяется его длина при помощи функции length.

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