ASP Clingo - 将图拆分为 n 个小集团

Question

对于给定的图形，我需要最多使用 n 个派系来表示它。我有这个任务的问题。这类似于图的 n 着色，它与给定图相反（图 b 与图 A 相反，如果图 A 中的边（a，b）比边（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).

ASP Clingo - 将图拆分为 n 个小集团

ASP Clingo - splitting graph to n cliques

np

answer-set-programming

clingo