时间戳

首页 > 解决方案 > 我需要一种算法，既能找到最少的颜色来为图形着色，又能确保没有两个相邻顶点具有相同的颜色

algorithm - 我需要一种算法，既能找到最少的颜色来为图形着色，又能确保没有两个相邻顶点具有相同的颜色

问题描述

我需要一个回溯算法，通过尊重没有相邻顶点可以具有相同颜色的事实来为图形着色。我们正在谈论一个无向连通图。我还需要相同的算法来确定为图形着色所需的不同颜色的最少数量。这基本上意味着我需要找到色数。

我已经找到了如何使用回溯方法为图形着色，但我还没有找到如何找到色数。是否有众所周知的算法（使用回溯，我已经知道一种贪婪的方法）。

标签： algorithmgraph

解决方案

使用MiniZinc约束服务器，您可以很容易地表达这样一个问题：

%  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直到找不到解决方案。

推荐阅读