ASP Clingo - разбиение графика на n cliques

Question

Для данного графика мне нужно представить его, используя не более n клик. У меня проблема с этой задачей. Это похоже на n-раскраску графика, противоположного заданному графику (график b противоположный графу A, если если ребро (a, b) в графе A, чем ребро (a, b), не находится в графе B). Я написал следующий код:

#const n = 3. 
{ color(X,1..n) } = 1 :- node(X). 
:- not edge(X, Y), color(X,C), color(Y,C). 

:- edge(X, Y), color(X,A), color(Y,B), A != B. 

но это не работает для данного теста:

node(1). 
node(2). 
node(3). 
node(4). 
edge(1, 2). 
edge(2, 1). 
edge(2, 3). 
edge(3, 2). 
edge(3, 4). 
edge(4, 3). 

, например, цвет (1) == цвет (2) = цвет (3) == цвет (4). Когда я удаляю одну из этих формул, она также не работает.

Answer 1

Одним из решений может быть первым определить complementary graph, а затем выбрать цвет:

#const n = 3. 
% one color per node 
1 { color(X,1..n) } 1 :- node(X). 

% yield complementary graph, without reflexive edges. 
cedge(X,Y):- not edge(X,Y) ; node(X) ; node(Y) ; X<Y. 

% avoid models where two nodes linked in the complementary graph have the same color 
:- cedge(X,Y) ; color(X,C) ; color(Y,C).