8.1.Двоично дърво.Представяне.Основни операции
8.2.Граф.Представяне.Основни операции
8.3.Пролог и КС-граматики
8.4.Пресмятане на стойност на аритметичен израз
8.5.Интерпретатор на подмножество на езика Пролог
8.2. Граф. Представяне. Основни операции
Логическо описание
Графът се определя като множество от върхове заедно е множество от ребра. Всяко ребро се задава
чрез двойка върхове. Ако ребрата са ориентирани се наричат дъги. Задават се чрез наредени
двойки от върхове, а графът се нарича ориентиран.
Ребрата (дъгите) могат да се свързват с етикети от произволен вид (имена, числа), в зависимост
от конкретната задача.
Представяне
Най-често се използват следните начини за представяне:
-Всяко ребро се записва като отделно твърдение (link)
-Целият граф се представя като един обект
В този случай графът ще представяме като структура с главен функтор graph при неориентираните графи
и ograph - при ориентираните графи и два аргумента, които са списъци. Първият аргумент е списък,
съдържащ върховете на графа, а вторият - ребрата. Всяко ребро се представя чрез структура.
Основни операции
Основни операции за работа с граф са:
-проверка, дали елемент е връх на граф
-проверка, дали има ребро между два върха на граф
-включване на ребро
-изключване на ребро
-включване на връх
-изключване на връх
-проверка, дали съществува път между два върха на граф
-намиране на път между два върха на граф
-намиране на път с определена дължина между два върха на граф.
Задача 1: Даден е неориентиран граф G. Да се дефинира отношение way, което установява дали има път
от връх X до връх Y на G.
Пример: За неоринтирания граф G,искаме да проверим, дали съществува път от върха а до върха с.
way(X, X) :- !.
way(X, Y) :- (link(X, Z); link(Z, X)),
way(Z, Y).
За съжаление тази програма не работи винаги вярно. За да се избегне зациклянето може да се въведе
трети аргумент на отношението way - помощен списък Т, в който да се записват върховете, които са
преминати в процеса на търсене на път. За следващ ще се избере такъв, който не се съдържа в
списъка Т. Отначало Т ще бъде празния списък.
Тогава отношението way получава вида:
way(X, X, T) :- !.
way(X, Y, T) :- (link(X, Z); link(Z, X)),
not member(Z, T),
way(Z, Y, [X|T]).
Тази реализация на way се нарича търсене в дълбочина.Програмата има недостатъка, че когато тя
успешно завърши изпълнението си, не е известен пътят между двата зададени върха.
Задача 2: Даден е неориентираният граф G. Да се дефинира отношение foundway, което в случай, че има
път между два върха на G, намира пътя.
Решение: Отново ще разглеждаме само ациклични пътища. Ще дефинираме отношението foundway(S, E, W),
което е истина, ако от връх S до връх Е има път и W съдържа един път от S до E. За целта ще дефинираме
помощно отношение way1, което ще определим по подобен на отношението way начин. Ще добавим на way1 още
един аргумент, който ще съдържа намерения път.
foundway(S, E, W) :- way1(S, E, [], R),
reverse(R, W).
way1(X, X, T, [X|T]).
way1(X, Y, T, R) :- (link(X, Z); link(Z, X)),
not member(Z, T),
way1(Z, Y, [X|T], R).
Същата задача, но за граф, представен като един обект:
way1(A, [Y|W], G, P) :- rib(X, Y, G),
not member(X, W),
way1(A, [X, Y|W], G, P).
Отношението rib(X, Y, G) означава, че в неориентирания граф има ребро от X до Y. Тъй като графът е
представен като един обект от вида graph(V, R), то rib може да се дефинира така:
rib(X, Y, graph(V, R)) :- member(p(X, Y), R);
member(p(Y, X), R).
Получаваме програмата:
way(A, Z, G, P) :- way1(A, [Z], G, P).
way1(A, [A|W], G, [A|W]).
way1(A, [Y|W], G, P):- rib(X, Y, G),
not member(X, W),
way1(A, [X, Y|W], G, P).
Като се използва отношението way, могат да се намерят всички възможни пътища между два върха на
даден граф G.
Дефиниция: Хамилтонов цикъл в граф се нарича ацикличен път, минаващ през всички върхове на
на графа.
Задача 3: Да се дефинира отношение hamilton(G, W), което намира хамилтонов цикъл W в графа G, ако
такъв съществува.
Решение: W е хамилтонов цикъл в G, ако W е път между два върха на G и всеки връх на G принадлежи
на W.
hamilton(G, W) :- way(A, B, G, W),
not (top(C, G), not member(C, W)).
Отношението way(A, B, G, W) намира произволен път W от A до B в G, а целта
not (top(C, G), not member(C, W)) проверява дали всеки връх С на графа G се съдържа в пътя W.
Тази цел е съкратен запис на предиката
top(C, G) => member(C, W), т.е.
~top(C, G) V member(C, W), т.е.
~(top(C, G) & member(C, W)).
Отношението top(X, G), определящо дали Х е връх на графа G, може да се дефинира по следния начин:
top(X, graph(V, R)) :- member(X, V).
Ако всяко ребро на графа е свързано със стойност, възможно е да се търсят пътища с определена
стойност.
Дефиниция: Стойността на път е равна на сумата от стойностите на влизащите в него ребра.
Задача 4: Да се модифицира Задача 2, така че освен път между два върха, да се намира и стойността
му , в случай, че път съществува.
Решение: Ще въведем още аргументи на отношенията way и way1. Нека way има вида way(A, Z, G, P, S),
като новият аргумент S означава стойността на пътя Р, а way1 - way1(A, P1, S1, G, P, S),
като S1 е стойността на пътя P.
way(A, Z, G, P, S) :- way1(A, [Z], 0, G, P, S).
way1(A, [A|W], S1, G, [A|W], S1).
way1(A, [Y|W], S1, G, P, S) :- rib(X, Y, Sxy, G),
not member(X, W),
S2 is S1 + Sxy,
way1(A, [X, Y|W], S2, G, P, S).
Отношението rib има още един аргумент - стойността Sxy на реброто и може да се дефинира така:
rib(X, Y, Sxy, graph(V, R)) :- member(p(X, Y, Sxy), R);
member(p(Y, X, Sxy), R).
Дефиниция: Път в граф, който преминава през всяко ребро на графа точно веднъж се нарича Ойлеров.
Дефиниция: Граф е свързан, ако за всеки два върха А и В от него, съществува път, свързващ А и В,
а в случай, че графът е ориентиран - съществува път с начало А и край В.
Дефиниция: Покриващо дърво за графа G = (V, R) е свързан граф Т = (V, R'), където R' е такова
подмножество на R, че в Т няма цикли.
Задача 5: Даден е свързан неориентиран граф G, представен чрез списък от съставящите го ребра. Да се
напише програма, която намира покриващо дърво Т на G.
Решение: Ще дефинираме отношението cov_tree(G, T), определящо покриващо дърво Т на графа G.
Т е покриващо дърво на графа G, ако:
-Т е подмножество на G и
-Т е дърво и
-Т "покрива" G, т.е. всеки връх на G се съдържа в Т.
Множеството от ребра Т е дърво, ако:
-Т е свързан граф и
-Т не съдържа цикли.
cov_tree(G, T) :- subset(G, T),
tree(T),
cover(T, G).
subset([], []).
subset([X|L], S) :- subset(L, L1),
(S = L1; S = [X|L1]).
tree(T) :- connected(T),
not have_a_cycle(T).
connected(T) :- not (top(A, T), top(B, T),
not way(A, B, T, _)).
have_a_cycle(T) :- rib(A, B, T),
way(A, B, T, [A, X, Y|_]).
/* дължината на пътя е по-голяма от 1 */
cover(T, G) :- not (top(A, G),
not top(A, T)).
