Алгоритмы на графах и их пролог программы

ЦЕЛЬ: Дать представление об основных задачах на графах.

В настоящее время возросла роль графовых моделей в различных практических приложениях таких, как автоматизированные системы управления, экспертные системы, системы искусственного интеллекта и т.п.

Графом называют систему объектов G = (V,E), где V={V1,...,Vm} - множество вершин, а E = {E1 = (Vi1,Vj1),...,En = (Vin,Vjn)} - множество ребер.

Если пара (Vik,Vjk) упорядочена, то граф называют ориентированным, в противном случае граф - неориентированный или просто граф.

Например,

V={1,2,3,4,5}

E={a=(1,2),

b=(2,3),

c=(1,3),

d=(2,4),

e=(4,5),

f=(3,5)}

Граф в прологе удобно задавать с помощью предиката 'ребро'. В общем случае этот предикат выглядит следующим образом

ребро(Имя_ребра, Вершина_начало_ребра, Вершина_конец_ребра, Вес_ребра).

В частных случаях некоторые аргументы предиката 'ребро' могут отсутствовать. Так для графа, нарисованного выше, имеем

Ребро(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: Если найден путь, длина которого равна общему количеству

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