图形着色算法的布尔公式

Question

我有一个有 5 个顶点的图。

Graph g1 = new Graph(5);
        g1.addEdge(0, 1);
        g1.addEdge(0, 2);
        g1.addEdge(1, 2);
        g1.addEdge(1, 3);
        g1.addEdge(3, 2);
        g1.addEdge(3, 4);
        g1.addEdge(4, 2);
        System.out.println("Coloring of graph 1");
        g1.greedyColoring();

我需要将为该图着色的问题表达为布尔表达式。

假设 a、b 和 c 是三种颜色，字面值 ai 表示顶点 i 具有颜色 a。那么上面的图就可以这样着色：

a0, b1, c2, a3, b4

我怎样才能得到一个布尔公式，当满足时，它提供了为该图着色的解决方案？

Answer 1

您正在寻找对图中的所有顶点进行着色，每个顶点都具有三种可用颜色中的一种，以便没有两个相邻节点具有相同的颜色。

因此存在三种类型的条件：

1.两个相邻节点不能有相同的颜色

例如，边 (0, 1) 将意味着这三个约束：

• 节点 0 和 1 不能同时具有颜色 a
• 节点 0 和 1 不能同时具有颜色 b
• 节点 0 和 1 不能同时具有颜色 c

翻译成布尔表达式：

¬a0 ∨ ¬a1
¬b0 ∨ ¬b1
¬c0 ∨ ¬c1

您需要为所有边生成这样的析取三元组。所以总共你将有 3 x 7 = 21 个布尔析取：

¬a0 ∨ ¬a1    ¬a0 ∨ ¬a2    ¬a1 ∨ ¬a2    ¬a1 ∨ ¬a3    ¬a3 ∨ ¬a2    ¬a3 ∨ ¬a4    ¬a4 ∨ ¬a2
¬b0 ∨ ¬b1    ¬b0 ∨ ¬b2    ¬b1 ∨ ¬b2    ¬b1 ∨ ¬b3    ¬b3 ∨ ¬b2    ¬b3 ∨ ¬b4    ¬b4 ∨ ¬b2
¬c0 ∨ ¬c1    ¬c0 ∨ ¬c2    ¬c1 ∨ ¬c2    ¬c1 ∨ ¬c3    ¬c3 ∨ ¬c2    ¬c3 ∨ ¬c4    ¬c4 ∨ ¬c2

###2。所有节点都必须有颜色

例如，对于节点 0，我们将有这个约束：

• 节点 0 必须具有颜色 a、b 或 c

翻译成布尔表达式：

a0 ∨ b0 ∨ c0

您需要对所有节点执行相同的操作，因此总共您将有 5 个这样的表达式：

a0 ∨ b0 ∨ c0
a1 ∨ b1 ∨ c1
a2 ∨ b2 ∨ c2
a3 ∨ b3 ∨ c3
a4 ∨ b4 ∨ c4

3.任何节点都不能获得超过一种颜色

例如，对于节点 0，我们将有：

• 节点 0 不能同时具有颜色 a 和 b
• 节点 0 不能同时具有颜色 a 和 c
• 节点 0 不能同时具有颜色 b 和 c

翻译成布尔表达式：

¬a0 ∨ ¬b0
¬a0 ∨ ¬c0
¬b0 ∨ ¬c0

您需要对所有节点执行相同的操作，因此总共您将拥有 3 * 5 = 15 个此类表达式：

¬a0 ∨ ¬b0    ¬a1 ∨ ¬b1    ¬a2 ∨ ¬b2    ¬a3 ∨ ¬b3    ¬a4 ∨ ¬b4
¬a0 ∨ ¬c0    ¬a1 ∨ ¬c1    ¬a2 ∨ ¬c2    ¬a3 ∨ ¬c3    ¬a4 ∨ ¬c4
¬b0 ∨ ¬c0    ¬b1 ∨ ¬c1    ¬b2 ∨ ¬c2    ¬b3 ∨ ¬c3    ¬b4 ∨ ¬c4

结论

上述所有析取（其中有 21 + 5 + 15 = 41 个）都必须为真（共轭）。这样的问题是一个布尔可满足性问题，更具体地说是3-SAT，并且是一个 NP 完全问题。

生成布尔表达式的代码

以下代码假设 Graph 对象将公开一个 nodes 列表，其中每个 node 都有一个 id 和 neighbors。

析取作为字符串输出，每个都在单独的行上：

Graph g1 = new Graph(5);
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(1, 3);
g1.addEdge(3, 2);
g1.addEdge(3, 4);
g1.addEdge(4, 2);
char colors[] = {'a', 'b', 'c'};
// Type 1
for (Node node : g1.nodes) {
    for (Node neighbor : node.neighbors) {
        for (char color : colors) {
            System.out.println(String.format("¬%1$c%2$d ∨ ¬%1$c%3$d", color, node.id, neighbor.id));
        }
    }
}
// Type 2
for (Node node : g1.nodes) {
    String expr[] = new String[colors.length];
    int i = 0;
    for (char color : colors) {
        expr[i++] = String.format("%s%d", color, node.id);
    }
    System.out.println(String.join(" ∨ ", expr));
}
// Type 3
for (Node node : g1.nodes) {
    for (char color1 : colors) {
        for (char color2 : colors) {
            if (color1 < color2) {
                System.out.println(String.format("¬%1$c%3$d ∨ ¬%2$c%3$d", color1, color2, node.id));
            }
        }
    }
}

Answer 2

您得到每条边的方程并将它们与 和 连接（ci 是顶点 i 使用的颜色）：

c0 != c1 && c0 != c2 && c1 != c2 && c1 != c3 && c2 != c3 && c2 != c4 && c3 != c4

布尔公式仅检查您是否找到了图形的有效着色，而不检查颜色数量是否最小化。