Лекция: Ребро(a,1,2).

Ребро(b,2, З).

Ребро(c,1, З).

Ребро(d,2,4).

Ребро(e,4,5).

Ребро(f, З,5).

Маршрут из вершины Vi в Vj — чередующаяся последовательность вершин и ребер, начинающаяся в вершине Vi и заканчивающаяся

в вершине Vj и в которой любая пара соседних элементов инцидентна

( вершина V и ребро E инцидентны, если E = (V,W) или E = (W,V)).

Рассмотрим задачу поиска эйлеровой цепи и эйлерового цикла.

Эйлерова цепь — маршрут, содержащий все ребра графа в точности

один раз. Эйлеров цикл — эйлерова цепь, у которой начальная и ко-

нечная вершины совпадают.

Напишем правила для поиска эйлеровой цепи в графе, описав предикат

найти_путь(Текущая, Пройденные),

где первый аргумент — Текущая — вершина, а второй — список Пройденные, хранящий номера пройденных в процессе поиска ребер.

Правило 1: Если найден путь, длина которого равна общему количеству

ребер, то искомый путь найден и его надо напечатать.

найти_путь(Текущая, Пройденные):- длина(Пройденные,6),

Write(Пройденные).

Правило 2: Если остались еще не пройденные ребра, то надо взять

ребро, исходящее из текущей вершины и не принадлежащее списку

пройденных.

найти_путь(Текущая, Пройденные):-

длина(Пройденные,N),N<6, ребро(Ребро, Текущая, Новая),

Не_принадлежит(Ребро, Пройденные),

найти_путь(Новая,[Ребро|Пройденные]).

(предикат 'не_принадлежит' написать самостоятельно).