Cvičenie 5
Riešenie úlohy Čísla odvzajte v moodli do 4.11.2014 18:09:59.
Graph coloring
Napíšte program, ktorého modely budú zodpovedať rôznym zafarbeniam grafu farbami col1..colN tak aby žíadne dva vrcholy spojené hranou nemali rovnakú farbu.
Graf je zadaný predikátmi node/1 a edge/2, možné farby predikátom color/1. Výsledné zafarbenie bude dané predikátom nodeColor( node, color ).
Mozny vstup:
2-graphcolor-input.lpcolor(c1). color(c2). color(c3). node(a). node(b). node(c). edge(a,b). edge(b,c). edge(a,c).2-graphcolor.sm
#hide. #show nodeColor(_,_). color(c1). color(c2). color(c3). node(a). node(b). node(c). edge(a,b). edge(b,c). edge(a,c). nodeColor(Node,Color) :- node(Node), color(Color), not notChosenColorForNode( Color, Node ). notChosenColorForNode( Color1, Node ) :- node(Node), color(Color1), color(Color2), nodeColor(Node,Color2), Color1 != Color2. :- node(Node1), node(Node2), color(Color), nodeColor(Node1,Color), nodeColor(Node2,Color), edge(Node1,Node2).2-graphcolor.dlv
color(c1). color(c2). color(c3). node(a). node(b). node(c). edge(a,b). edge(b,c). edge(a,c). nodeColor(Node,Color) :- node(Node), color(Color), not notChosenColorForNode( Color, Node ). notChosenColorForNode( Color1, Node ) :- node(Node), color(Color1), color(Color2), nodeColor(Node,Color2), Color1 != Color2. :- node(Node1), node(Node2), color(Color), nodeColor(Node1,Color), nodeColor(Node2,Color), edge(Node1,Node2).
Hamiltonovská kružnica
Zadaný je (neorientovaný) graf, pomocou predikátov edge/2 a node/1. Napíšte program ktorého modely budú zodpovedať možným hamiltonovským kružniciam na tomto grafe. Hrany vybrané do hamiltonovskej kružnice nech sú reprezentované predikátom ham/2.
Vstup:
ham-vstup.dlv%input: % d - a - e % | X | / | % c - b - f nd(a). nd(b). nd(c). nd(d). edge(A,B) :- nd(A), nd(B), A<B. node(A) :- nd(A). node(e). edge(a,e). edge(b,e). node(f). edge(b,f). edge(e,f).hamxx.dlv
%input: % d - a - e % | X | / | % c - b - f nd(a). nd(b). nd(c). nd(d). edge(A,B) :- nd(A), nd(B), A<B. node(A) :- nd(A). node(e). edge(a,e). edge(b,e). node(f). edge(b,f). edge(e,f). % choose ham(A,B) :- not -ham(A,B), edge(A,B). -ham(A,B) :- not ham(A,B), edge(A,B). % make it directed dir(A,B) :- ham(A,B). dir(B,A) :- ham(A,B). % every node must be reachable (from every node ;) reachableFrom(A,B) :- node(A), node(B), A==B. reachableFrom(A,B) :- reachableFrom(C,B), dir(A,C). :- node(A), node(B), not reachableFrom(A,B). % each node must have deg 2 in ham (or dir) degMoreThan3(N) :- dir(N,A), dir(N,B), dir(N,C), A!=B, B!=C, A!=C. deg2(N) :- dir(N,A), dir(N,B), A!=B, not degMoreThan3(N). :- node(N), not deg2(N).
Čísla
Vstupom sú niektoré cifry 5 ciferného čísla cez predikát cif(I,C) a predikát modulo(X), ktorý platí pre práve jedno číslo X. Úlohou je dorátať ostatné cifry tak, aby číslo bolo deliteľné X. (Môže byť viac riešení, pre každé chceme jeden model. Špeciálne ak by boli zadané na vstupe všetky cifry, tak výsledkom bude jeden stabilný model ak vstupné číslo je deliteľné X, alebo žiadny model, ak nie je deliteľné.)