グラフ彩色問題

グラフ彩色問題(Graph coloring)とは、ある制約条件のもとでグラフの頂点または辺に色を割り当てる問題です。
ここでは、代表的な問題として隣接する頂点が同じ色にならないようにすべての頂点に色を割り当てる頂点彩色を取り上げます。
頂点彩色はスケジューリング問題や通信網の周波数割り当てなどに応用されます。

入力としてグラフと色の集合が与えられるものとします。
彩色を表現するために、決定変数を定義します。は頂点を色で塗る場合に、それ以外の場合にを取るように設定します。グラフ彩色問題の制約条件として以下の2つが挙げられます。

を用いて2つの制約条件はそれぞれ以下のように表すことができます。上記の式を満たす場合に最小値をとるように、 イジングモデルのエネルギー関数を以下のように定義します。

ここでは、グラフの頂点数と辺密度(可能な辺の数に対する割合)を設定して頂点彩色のシミュレーションを体験できます。