Мне нужен алгоритм, который найдет минимальное количество цветов для раскраски графа и гарантирует, что ни одна из двух вершин не имеет одинаковый цвет

Question

Мне нужен алгоритм обратного отслеживания для раскраски графа, учитывая тот факт, что никакие смежные вершины не могут иметь одинаковый цвет. Мы говорим о неориентированном связном графе. Мне также нужен тот же алгоритм для определения минимального количества различных цветов, необходимых для раскраски графика. Это в основном подразумевает, что мне нужно найти число chromati c.

Я нашел, как раскрасить график с помощью метода возврата, но я не нашел, как найти число chromati c. Есть ли хорошо известный алгоритм для этого (с помощью backtracking я уже знаю о жадном подходе).

Answer 1

Используя сервер ограничений MiniZin c, вы можете express довольно легко решить такую ​​проблему:

%  Petersen Graph
set of int: Colors = 1..3;
set of int: Nodes = 1..10;
set of int: Edges = 1..15;
array[Edges] of Nodes: aFrom = [ 1, 2, 3, 4, 1, 1, 2, 3, 4,  5, 6,  7, 7,  8, 6 ];
array[Edges] of Nodes: aTo   = [ 2, 3, 4, 5, 5, 6, 7, 8, 9, 10, 8, 10, 9, 10, 9 ];

array[int] of string: colorName = [ "red", "green", "blue", "purple", "yellow", "brown", "black" ];

array[Nodes] of var Colors: nodeColor;

constraint
  forall(e in Edges) (
      nodeColor[aFrom[e]] != nodeColor[aTo[e]]
  );

solve satisfy;

output [ show(colorName[nodeColor[n]]) ++ "\n" | n in Nodes ]; 

Чтобы определить минимальное количество цветов, вы можете уменьшить Colors пока решение не найдено.