Zadanie 1 (Artur Zaroda)

Zdefiniuj predykat drzewo(W,K,T) odnoszacy sukces, jesli z grafu
nieskierowanego o wierzcholkach W i krawedziach K mozna zbudowac
drzewo binarne T umieszczajac w jego wezlach wszystkie wierzcholki grafu
(kazdy wierzcholek w jednym wezle) tak, by wezly zawierajace wierzcholki
X i Y sasiadowaly (jeden byl ojcem a drugi synem) w T wtedy i tylko wtedy,
gdy w grafie istnieje miedzy nimi krawedz.

Zbior wierzcholkow W jest reprezentowany przez liste bez powtorzen,
zbior krawedzi K to lista bez powtorzen zawierajaca termy kr(X,Y)
oznaczajace krawedz nieskierowana laczaca X i Y a drzewo T jest
zbudowane przy pomocy stalej nil i symbolu funkcyjnego tree(L,W,P)
oznaczajacego wezel o wartosci W z poddrzewami L i P.

Predykat powinien dzialac dla zapytan, w ktorych pierwsze dwa
argumenty sa w pelni ustalone, trzeci moze byc ustalony w dowolnym
stopniu.

Przyklady sukcesow:

?-drzewo([11,22,33],[kr(11,22),kr(11,33)],tree(tree(nil,33,nil),11,tree(nil,22,nil))).
?-drzewo([11,22,33],[kr(11,22),kr(11,33)],tree(nil,33,tree(tree(nil,22,nil),11,nil))).
?-drzewo([11,22,33,44],[kr(11,22),kr(11,33),kr(11,44)],tree(tree(tree(nil,33,nil),11,tree(nil,44,nil)),22,nil)).

Przyklady porazek:

?-drzewo([11,22,33],[kr(11,22)],_).
?-drzewo([11,22,33,44],[kr(11,22),kr(33,44)],_).
?-drzewo([11,22,33],[kr(11,22),kr(22,33),kr(11,33)],_).
?-drzewo([11,22,33,44],[kr(11,22),kr(11,33),kr(11,44)],tree(_,11,_)).
?-drzewo([11,22,33,44,55],[kr(11,22),kr(11,33),kr(11,44),kr(11,55)],_).


Zadanie 2 (Artur Zaroda)

Drzewa reprezentujemy przy pomocy symbolu funkcyjnego tree(L,W,P)
oznaczajacego wezel o wartosci W z poddrzewami L i P, oraz stalej
nil oznaczajacej drzewo puste.

Zdefiniuj predykat odwrotnie(T,S) odnoszacy sukces, jesli wszystkie
wartosci z wezlow drzewa binarnego T znajduja sie w wezlach drzewa
binarnego S a sciezka, ktora prowadzi od korzenia do kazdej wartosci
w drzewie S ma "odwrocony ksztalt" w stosunku do sciezki od korzenia
do wystapienia tej wartosci w T.

Jesli np. do jakiejs wartosci w T mozna dojsc od korzenia tego drzewa
przechodzac w lewo a nastepnie dwa razy w prawo, to w S powinna ona
znalezc sie w wezle, ktory odnajdziemy idac od korzenia dwa razy
w prawo a nastepnie w lewo.

Predykat powinien dzialac dla zapytan, w ktorych pierwszy argument
jest w pelni ustalony. Drugi moze byc ustalony w dowolnym stopniu.

Przyklady sukcesow:

?-odwrotnie(nil,nil).
?-odwrotnie(tree(nil,11,tree(tree(nil,33,nil),22,nil)),tree(tree(nil,_,tree(nil,33,nil)),11,tree(nil,22,nil))).
?-odwrotnie(tree(nil,11,tree(nil,22,tree(tree(nil,44,nil),33,nil))),tree(tree(nil,_,tree(nil,_,tree(nil,44,nil))),11,tree(nil,22,tree(nil,33,nil)))).
?-odwrotnie(tree(tree(tree(nil,ll,nil),lx,tree(nil,lp,nil)),xx,tree(tree(nil,pl,nil),px,tree(nil,pp,nil))),tree(tree(tree(nil,ll,nil),lx,tree(nil,pl,nil)),xx,tree(tree(nil,lp,nil),px,tree(nil,pp,nil)))).


Zadanie 3 (Nguyen Anh Lin)

Niepuste drzewa zmiennego rzedu sa reprezentowane w postaci 
tree(W, L), gdzie W jest wartoscia w korzeniu a L jest lista podrzew 
(korzenia). Przyklad takiego drzewa to:
tree(1,[tree(2,[tree(3,[])]),tree(4,[]),tree(5,[])])
Napisac predykat buduj_drzewo(G,D), ktory dla ustalonego grafu 
skierowanego G zwraca wszystkie drzewa D takie, ze zbior krawedzi (od ojca 
do syna) drzewa D jest taki sam jak zbior krawedzi grafu G, lub odnosi 
porazke jesli nie ma takich podrzew.

Przyklady:
buduj_drzewo([kr(1,2],kr(2,3),kr(1,4),kr(1,5)], D) zwraca miedzy innymi drzewo podane wyzej.
buduj_drzewo([kr(1,2),kr(3,4)], D) odnosi porazke.
buduj_drzewo([kr(1,2),kr(2,1)], D) odnosi porazke.