图着色算法的布尔公式
Boolean formula for a graph colouring algorithm
我有一个有 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();
我需要将coloring this graph的问题表达为布尔表达式
假设a,b,c是三种颜色,文字ai表示顶点 i 具有颜色 a。那么上图可以这样着色:
a0, b1, c2, a3, b4
我怎样才能得到一个布尔公式,当满足该公式时,它会提供一个为该图着色的解决方案?
你得到每条边的方程式并将它们连接起来(ci 是用于顶点 i 的颜色):
c0 != c1 && c0 != c2 && c1 != c2 && c1 != c3 && c2 != c3 && c2 != c4 && c3 != c4
布尔公式只检查您是否找到了图形的有效着色,而不检查颜色数是否已最小化。
您要为图形中的所有顶点着色,每个顶点使用三种可用颜色中的一种,这样没有两个相邻节点具有相同的颜色。
因此有三种类型的条件:
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个)都需要为真(共轭)。这样的问题是Boolean satisfiability problem, and more particularly 3-SAT,是一个NP-Complete问题
生成布尔表达式的代码
以下代码假定 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));
}
}
}
}
在 repl.it 上查看 运行。
我有一个有 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();
我需要将coloring this graph的问题表达为布尔表达式
假设a,b,c是三种颜色,文字ai表示顶点 i 具有颜色 a。那么上图可以这样着色:
a0, b1, c2, a3, b4
我怎样才能得到一个布尔公式,当满足该公式时,它会提供一个为该图着色的解决方案?
你得到每条边的方程式并将它们连接起来(ci 是用于顶点 i 的颜色):
c0 != c1 && c0 != c2 && c1 != c2 && c1 != c3 && c2 != c3 && c2 != c4 && c3 != c4
布尔公式只检查您是否找到了图形的有效着色,而不检查颜色数是否已最小化。
您要为图形中的所有顶点着色,每个顶点使用三种可用颜色中的一种,这样没有两个相邻节点具有相同的颜色。
因此有三种类型的条件:
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个)都需要为真(共轭)。这样的问题是Boolean satisfiability problem, and more particularly 3-SAT,是一个NP-Complete问题
生成布尔表达式的代码
以下代码假定 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));
}
}
}
}
在 repl.it 上查看 运行。