Лекция: АЛГОРИТМЫ НА ГРАФАХ И ИХ ПРОЛОГ ПРОГРАММЫ

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

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

Графом называют систему объектов 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)}

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

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