1

我的作业：图形着色 - 编写一个答案集程序来检查一个图形是否有 4 种颜色，如果有，答案集应该包含着色。如果没有着色，则不会有答案集。该程序应包含进行 4 色着色的代码和一个示例图形表示。

我有这个（来自 ASP Graph Coloring Wikipedia），但我不明白它是如何工作的——有人可以解释一下这段代码吗？

c(1..n).                                           
1 {color(X,I) : c(I)} 1 :- v(X).             
:- color(X,I), color(Y,I), e(X,Y), c(I).

v(1..100). % 1,...,100 are vertices
e(1,55). % there is an edge from 1 to 55
4

1 回答 1

0

代码说：

c(1..n).

你有事实c(1), c(2), ...c(n)代表颜色。n在您的情况下，之前已给出n=4。

1 {color(X,I) : c(I)} 1 :- v(X).

对于每个顶点都v(X)存在一个color从X可能c（颜色）到可能的分配。
a {...} b表示...发生在a和b次之间。
所以这意味着：每个顶点都只有一种颜色。不多也不少。

:- color(X,I), color(Y,I), e(X,Y), c(I).

以约束开头的规则:-：缺少的头部表示身体暗示虚假，因此身体也必须是虚假的。上面写着：
不可能有边e从哪里X到Y哪里X并且Y颜色相同I。
或者换句话说：相邻的顶点有不同的颜色。

要获得示例图，请添加所需的顶点和边缘。

于 2020-11-07T20:11:54.397 回答