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)). % А-В не породжує циклу