Постановка 11

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

Q([],0).

Edge(e, d, 9).

Edge(b, d, 0).

Edge(c, d, 12).

Edge(a, b, 3).

Edge(a,c,8).

Clauses

Q(slist,integer).

Cyclic.

Lenght(slist,integer).

Member(string,slist).

E(string,string,integer).

Edge(string,string,integer).

Predicates

Domains

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

Append(Tail,B,NewTail).

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

Edge(e, d, 9).

Edge(b, d, 0).

Edge(c, d, 12).

Edge(a, b, 3).

Edge(a,c,8).

Clauses

Append(l,l,l).

N(slist,slist).

Weight(string,l,slist).

Short_path(string,string,slist).

Member(string,slist).

E(string,string,integer).

Edge(string,string,integer).

Predicates

Domains

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

Placeone(X,Tail,NewTail).

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

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

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

slist=string*

l=slist*

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

wlist=way*

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),!,

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

append([],B,B).

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

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

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

slist=string*

l=slist*

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

wlist=way*

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([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. За корінь можна взяти довільну з вершин списку. Остовні дерева становлять інтерес, наприклад у задачах проектування мереж зв'язку, оскільки дозволяють мінімальним число ліній встановити зв'язок між будь-якими двома вузлами, що відповідають вершинам графа.

Визначимо процедуру 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):-

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