Постановка 1

Edge(v,u,2).

Edge(u,t,2).

Edge(t,u,5).

Edge(t,v,1).

R(c,d).

R(b,c,).

(b) – edge(s,t,3).

а в явній формі – термами:

(а) – graph([a,b,c,d], [r(a,b), r(b,d), r(b,c,), r(c,d)]),

(b) – dgraph([s,t,u,v], [edge(s,t,3), edge(t,v,1), edge(t,u,5), edge(u,t,2), edge(v,u,2)]),

де graph та dgraph – бінарні функтори.

Якщо в графі нема ізольованих вершин (тобто, кожна з них з’єднана хоча б з однією іншою), то в його представленні множину вершин можна опустити, оскільки вона неявно вже є в списку ребер.

Ще один спосіб подання графа - зв'язати з кожною вершиною список суміжних з нею вершин. Тоді граф стає списком пар, кожна з яких складається з вершини та її списку суміжності, наприклад у формі:

G1 = [ a->[b], b->[a, c, d], c->[b, d], d->[b, c]]

G2 = [s->[t/3], t->[u/5, v/l], u->[t/2], v->[u/2]],

де символи '->' та '/' - інфіксні функтори.

На тій же ідеї околиці вершини засноване ще одне практично важливе подання. Граф визначається відношенням neighborhood(A,NB), що зв'язує вершину зі списком її сусідів. Подібним чином представляють граф, розфарбовуючи карту. Неважко визначити процедури, що дозволяють переходити від одного подання до іншого.

edge(A,B):- neighborhood(A,NB),member(B,NB).

neighborhood(A,NB):- setof(B,edge(A,B),NB).

Практично завжди треба визначитись, є оброблюваний граф орієнтованим чи ні.

Яка із наведених форм представлення графів є ефективнішою, залежить від додатку та від операцій, виконуваних над графами. Серед типових операцій:

§ пошук шляху між двома заданими вершинами;

§ пошук підграфа, що має деякі задані властивості.

наявність зв'язку між вершинами графа

Дві вершини графа зв'язані, якщо існує послідовність ребер (дуг), що веде з першої вершини в другу.

Використаємо неявне подання стосовно до графа:

domains

top=symbol

predicates

edge (top, top) % аргументи позначають імена вершин

path(top,top) % дві вершини зв'язані, якщо між ними

існує шлях.

clauses

edge (a, b).

edge (c, d).

edge (a, c).

edge (d, e).

edge (b, d).

edge (f, g).

path (X, X).

path (X, Y):- edge (X, Z), path (Z, Y).

Дата добавления: 2014-01-04