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

Для данного графа мне нужно представить его, используя не более 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). Когда я удаляю одну из этих формул, она также не работает.


np answer-set-programming clingo
person domandinho    schedule 16.12.2016    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Одним из решений может быть сначала определение дополнительного графа, а затем выбор цветов:

#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).
person aluriak    schedule 30.01.2017