グラフの色付けアルゴリズムの実装

Question

グラフの色付けアルゴリズムがNP完全な問題であることがわかりました。それでも、ヒューリスティックアプローチを使用して実装が可能かどうか、特にグラフ着色を区別するかどうかを知りたいです？可能であれば、それについて学ぶ適切なリソースはありますか？

Answer 1

幾分related postで説明したように：MiniZinc等

制約ソルバは、グラフ彩色問題の広い範囲を解決することができます。

このMiniZinc例はPetersen graphの着色を示しています

% 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 ];