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.lp

color(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é.)