Incident( X, y, g)

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

G = g(V, E),

то

Incident(X, y, g(V, e)):-

member(edge(X, Y), E);

member(edge(Y, X), E).

пошук Гамільтонова циклу

Є класичною задачею на графах щодо пошуку ациклічного шляху крізь всі вершини графа. Рішення цієї задачі з використанням відношення path визначають так:

gamilt( G, P) :-

path( _, _, G, P),

alltop( P, G).

alltop( P, G) :-

not (top( В, G)),

not (member(В, P)).

Тут top( В, G) означає: В - вершина графа G.

Вартість шляху

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

Щоб відношення path і path1 могли працювати із вартостями, їх модифікують, додаючи аргумент:

path( А, Z, G, Р, С)

path1( A, P1, C1, G, Р, С)

Тут С – вартість шляху Р, a C1 - вартість шляху Р1. У відношенні incident теж додано аргумент – вартість дуги:

Incident(X, y, с_xy, g(V, e)):-

member(edge(X, Y, С_XY), E);

member(edge(Y, X, С_XY), E).

Постановка 6.

Побудова шляху з обчисленням його вартості на графі G, заданому явно.

path( А, Z, G, Р, С):-

path1( A, [Z], 0, G, Р, С).

path1( A, [А | Р1], С, G, [А | Р1], С).

path1( A, [Y | Р1], С1, G, Р, С) :-

Incident( X, y, с_xy, g),

not(member(X, Р1)),

С2 іs С1 + С_XY,

path1( A, [X, Y | Р1], С2, G, Р, С).

Постановка 7.

Побудова шляху мінімальної вартості на графі G, заданому явно.

Шлях мінімальної вартості між вершинами A та B графа G можна побудувати, задавши для попередньої програми запит

path(A, В, G, Мin_path, Мin_cost),

not(path(A, В, G, _, С), С< Мin_cost)

Аналогічно, серед всіх шляхів між вершинами графа можна знайти шлях максимальної вартості, задавши ціль

path(_, _, G, Мax_path, Мax_cost),

not(path(_, _, G, _, С), С> Мax_cost)

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

Постановка 8.

Побудова на графі G, заданому неявно, мінімального min_path(Х,Y,L) за вартістю ребер шляху L між вершинами Х та Y.

domains

slist=string*

l=slist*

way=w(integer,slist) %Зберігає вартість шляху і шлях

wlist=way*

predicates

edge(string,string,integer).

e(string,string,integer).

member(string,slist).

min_path(string,string,slist).

prolong(way,way).

place(wlist,wlist,wlist).

placeone(way,wlist,wlist).

ucs(string,wlist,way).

clauses

edge(a,c,8).

edge(a, b, 3).

edge(c, d, 12).

edge(b, d, 0).

edge(e, d, 9).

e(A,B,C):-edge(A,B,C);edge(B,A,C).%граф не є орграф

min_path(A,B,P):-ucs(A,[w(0,[B])],w(_,P)).

ucs(A,[w(C,[A|Tail])|_],w(C,[A|Tail])):-!. %пошук

згідно вагової функції

ucs(A,[Path|Tail],R):-

findall(Z,prolong(Path,Z),NewPathes),!,

place(NewPathes,Tail,New),ucs(A,New,R). ucs(A,[_|Tail],R):-ucs(A,Tail,R).

prolong(w(C,[X|T]),w(C1,[Y,X|T])):- % подовження

шляху

e(X,Y,E),not(member(Y,T)),C1=C+E. place([],L,L). %нові шляхи розміщує згідно їхньої ваги

place([X|T],L,R):-placeone(X,L,L1),place(T,L1,R).

placeone(w(C,P),[w(C1,P1)|Tail],[w(C,P),w(C1,P1)|Tail]):-

C<=C1,!.

placeone(X,[H|Tail],[H|NewTail]):-

placeone(X,Tail,NewTail).

placeone(X,[],[X]).

Зауваження: вбудований предикат findall(X, P, L) породжує список L всіх об'єктів X, що задовольняють Р. Якщо P завершується неуспіхом, то й findall завершується неуспіхом.

Постановка 9.

Побудова на графі G, заданому неявно, найкоротшого short_path(Х,Y,L) за кількістю ребер шляху L між вершинами Х та Y.

domains

slist=string*

l=slist*

way=w(integer,slist) %Зберігає вартість шляху і шлях

wlist=way*

predicates

edge(string,string,integer).

e(string,string,integer).

member(string,slist).

short_path(string,string,slist).

weight(string,l,slist).

n(slist,slist).

append(l,l,l).

clauses

edge(a,c,8).

edge(a, b, 3).

edge(c, d, 12).

edge(b, d, 0).

edge(e, d, 9).

e(A,B,C):-edge(A,B,C);edge(B,A,C). %граф не є орграф

short_path(A,B,P):-weight(A,[[B]],P).

weight(A,[[A|T]|_],[A|T]):-!.

weight(A,[H|Tail],Ans):- findall(B,n(H,B),Temp),!,

append(Tail,Temp,New),weight(A,New,Ans).

weight(A,[_|Tail],Ans):-weight(A,Tail,Ans).

append([],B,B).

append([H|Tail],B,[H|NewTail]):-

append(Tail,B,NewTail).

n([H|Tail],[B,H|Tail]):- e(H,B,_),not(member(B,Tail)).

Постановка 10.

Встановлення циклічності cyclic графа перевіркою умови: граф є циклічним, якщо кількість M його дуг більша за кількість N вершин, зменшених на одиницю.

domains

slist=string*

l=slist*

way=w(integer,slist) %зберігає вартість шляху і шлях

wlist=way*

predicates

edge(string,string,integer).

e(string,string,integer).

member(string,slist).

lenght(slist,integer).

cyclic.

q(slist,integer).

clauses

edge(a,c,8).

edge(a, b, 3).

edge(c, d, 12).

edge(b, d, 0).

edge(e, d, 9).

e(A,B,C):-edge(A,B,C);edge(B,A,C).% граф не орграф

cyclic:-findall(X,e(X,_,_),L),q(L,N),lenght(L,M),M>(N-1).

lenght([],0).

lenght([_|Tail],L) :- lenght(Tail,L1),L=L1+1.

q([],0).

q([H|Tail],N):-member(H,Tail),!,q(Tail,N).

q([_|Tail],N):-q(Tail,N1),N=N1+1.

Находим список всех ребер, считаем число N вершин, число M ребер, и проверяем віполнимость критерия.

Побудова остовного дерева

Граф є зв'язним, якщо між будь-якими двома його вершинами існує шлях. Нехай G = <V, Е> - зв'язний граф з множинами вершин V і ребep Е, тоді остовне дерево графа G - це зв'язний граф Т = <V, Е'>, де Е' - підмножина множини Е така, що

(1) Т - зв'язний граф,

(2) у Т нема циклів.

Виконання цих двох умов гарантує, що Т є деревом. Для графа рис. 1(а) існує три остовних дерева, що відповідають наступним трьом спискам ребер:

tree1 = [а-b, b-c, c-d]

tree2 = [а-b, b-d, d-c]

tree3 = [а-b, b-d, b-c]

де терми форми X-Y позначають ребра між вершинами Х і Y. За корінь можна взяти довільну з вершин списку. Остовні дерева становлять інтерес, наприклад у задачах проектування мереж зв'язку, оскільки дозволяють мінімальним число ліній встановити зв'язок між будь-якими двома вузлами, що відповідають вершинам графа.

Постановка 11.

Визначимо процедуру tree_column(G,Т), де Т - остовне дерево зв'язного графа G, побудови остовного дерева в такий спосіб:

• почати з порожньої множини ребер і поступово додавати такі нові ребра, що не утворюють цикли;

• цей процес продовжувати, поки можна приєднувати ребра;

• отримана множина ребер буде остовним деревом.

Відсутність циклів забезпечується правилом:

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

Програма використовує відношення (розширити): expand(Tree1, Tree, G), всі аргументи якого є множинами ребер у формі: [а-b, b-с, b-d, c-d]

tree_column(G, Tree):- %Тree - остовне дерево

member(Edge, G),

expand([Edge], Tree, G).

expand(Tree1, Tree, G) :-

conedge(Tree1, Tree2, G),

expand(Tree2, Tree, G).

expand(Tree, Tree, G) :- % Додавання будь-якого

ребра приводить до циклу

not(conedge(Tree,_, G)).

conedge(Tree,[A-В|Tree],G):- %Додавання ребра

incident(А, В, G), % А і В - суміжні вершини

top(А, Tree), % А втримується в Tree

not(top(В, Tree)). % А-В не породжує циклу