将无向图转换为 CNF SAT 以进行 3 着色

Question

现在，为了将其转化为 CNF SAT 问题，我的理解是：

每个节点必须至少有一种颜色。
每个节点最多只能有一种颜色。
连接的节点不能有相同的颜色。

但是我无法继续前进，因为我无法理解 return。如果我们有一个函数 Convert(graph)，其中图有 3 个节点，即 nodes = (0,1,2) 和 3 个边，即 edges = [(0,1), (0,2), (1,2)]，可能有 colors = (1,2,3)； 对于这种特殊情况，转换为 CNF SAT 表格的输出应该是什么样的？谢谢

Answer 1

这里是一个简单的直接编码：

对于每个节点，引入 k 个变量（k = 颜色数），以及一个简单列出这些变量的子句（强制至少选择一种颜色）。

对于每条边(X,Y)和颜色c，引入一个二元子句，防止X和Y同时具有颜色c，即-Xc -Yc.

对于此图，DIMACS 格式的总 CNF 可能如下所示：

p cnf 9 12
1 2 3 0
4 5 6 0
7 8 9 0
-1 -4 0
-2 -5 0
-3 -6 0
-4 -7 0
-5 -8 0
-6 -9 0
-1 -7 0
-2 -8 0
-3 -9 0

解算器可能会给出（例如，显然还有更多可能性）1 -2 -3 -4 -5 6 -7 8 -9 0意味着节点 0 得到颜色 1，节点 1 得到颜色 3，节点 2 得到颜色 2。

顺便说一下，没有使用约束“每个节点最多只能有一种颜色”。琐碎的 post-processing 可以解决这个问题。对于一些图表和一些颜色，你可能会得到一个节点被分配了多种颜色的结果（只有当它不与邻居共享这些颜色的 any 时，通常如果可能的话它仍然不会发生，因为求解器没有动力去做），您可以简单地选择其中任何一个。如果这不可接受，请为与节点关联的每对变量添加一个二元子句以禁止它们同时设置，例如 -1 -2 0、-1 -3 0 等等。

有更高级的编码可以更好地扩展到更大的图。

将无向图转换为 CNF SAT 以进行 3 着色

Converting Undirected Graph to CNF SAT for 3-Coloring

python

sat