Булева формула для алгоритма раскраски графа

Вы ищете способ раскрасить все вершины графа в один из трех доступных цветов так, чтобы никакие две соседние вершины не были одного цвета.

Таким образом, существует три типа условий:

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 предоставляет список узлов, где каждый узел имеет id и соседи.

Дизъюнкции выводятся в виде строк, каждая на отдельной строке:

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.

Вы получаете уравнение для каждого ребра и соединяете их с помощью и (ci — цвет, используемый для вершины i):

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

Логическая формула проверяет только то, нашли ли вы допустимую раскраску для графика, а не минимальное количество цветов.