M色グラフ彩色問題（M-Coloring Problem）とは？バックトラッキングによる解法をC++コード付きで解説

この問題では、無向グラフと使用可能な m 種類の色が与えられます。課題は、グラフ上で隣接する2つの頂点が同じ色にならないように、m 色ですべてのノードへ色を割り当てられるかどうかを判定することです。解が存在する場合は、どの頂点にどの色が割り当てられたかを出力します。

頂点0から順に、各ノードへ1つずつ色を試していきます。ただし、色を割り当てる前に、その色が「安全」かどうかを必ず確認する必要があります。隣接する頂点のいずれかに同じ色が既に使われている場合、その色は安全ではないと判断されます。

この手法はバックトラッキングと呼ばれる探索アルゴリズムの一種です。ある色の選択によって後続の頂点で行き詰まった場合は、直前の選択を取り消し（バックトラック）、別の色を試します。なお、グラフ彩色問題はNP完全問題として知られており、最悪計算量は O(m^V)、空間計算量は O(V) となります。

入力と出力

入力:
グラフ G(V, E) の隣接行列と、使用できる色の最大数を表す整数 m。


最大色数 m = 3 とします。
出力:
このアルゴリズムは、どのノードにどの色を割り当てるかを返します。解が存在しない場合は false を返します。
この入力に対する色の割り当て結果は以下の通りです。
Node 0 -> 色 1
Node 1 -> 色 2
Node 2 -> 色 3
Node 3 -> 色 2

アルゴリズム

isValid(vertex, colorList, col)

入力 − 対象の頂点、チェック対象の colorList、割り当てようとしている色。

出力 − 色の割り当てが有効であれば true、そうでなければ false。

Begin
    グラフ内のすべての頂点 v について繰り返す
        v と i の間に辺が存在し、かつ col = colorList[i] である場合
            return false
    繰り返し終了
    return true
End

graphColoring(colors, colorList, vertex)

入力 − 使用可能な最大色数、各頂点にどの色が割り当てられているかを記録するリスト、処理を開始する頂点。

出力 − すべての頂点への色割り当てが成功すれば true、そうでなければ false。

Begin
    すべての頂点を処理し終えた場合
        return true
    使用可能なすべての色 col について繰り返す
        isValid(vertex, color, col) が true の場合
            頂点 vertex の色として col を colorList に追加
            graphColoring(colors, colorList, vertex+1) が true の場合
                return true
            頂点 vertex の色を取り消す
    繰り返し終了
    return false
End

C++による実装例

#include<iostream>
#define V 4
using namespace std;

bool graph[V][V] = {
   {0, 1, 1, 1},
   {1, 0, 1, 0},
   {1, 1, 0, 1},
   {1, 0, 1, 0},
};

void showColors(int color[]) {
   cout << "Assigned Colors are: " << endl;
   for (int i = 0; i < V; i++)
      cout << color[i] << " ";
   cout << endl;
}

bool isValid(int v, int color[], int c) {     //頂点vへの色cの割り当てが有効かどうかを確認
   for (int i = 0; i < V; i++)
      if (graph[v][i] && c == color[i])
         return false;
   return true;
}

bool graphColoring(int colors, int color[], int vertex) {
   if (vertex == V)     //すべての頂点を処理し終えたとき
      return true;

   for (int col = 1; col <= colors; col++) {
      if (isValid(vertex, color, col)) {     //色colが有効かどうかを確認
         color[vertex] = col;
         if (graphColoring(colors, color, vertex + 1) == true)     //残りの頂点へ処理を進める
            return true;

         color[vertex] = 0;
      }
   }
   return false; //割り当て可能な色が存在しない場合
}

bool checkSolution(int m) {
   int *color = new int[V];     //各頂点用の色配列を作成

   for (int i = 0; i < V; i++)
      color[i] = 0;         //初期値はすべて0に設定

   if (graphColoring(m, color, 0) == false) {     //頂点0からグラフ彩色を開始
      cout << "Solution does not exist.";
      return false;
   }
   showColors(color);
   return true;
}

int main() {
   int colors = 3;       //色の数
   checkSolution(colors);
}

出力

Assigned Colors are:
1 2 3 2

この結果から、頂点0には色1、頂点1には色2、頂点2には色3、頂点3には色2が割り当てられており、隣接する頂点同士が異なる色になっていることが確認できます。

まとめ

M色グラフ彩色問題は、バックトラッキングを用いることで体系的に解くことができます。isValid 関数で色の安全性を検証しながら、再帰的に頂点へ色を割り当て、失敗したら一つ前の状態に戻って別の候補を試す、という流れが基本です。地図の塗り分け、スケジューリング、レジスタ割り付けなど、さまざまな実務的な問題にも応用される重要なアルゴリズムです。