グラフ彩色問題とは？貪欲法による解法アルゴリズムを解説

グラフ彩色問題とは

グラフ彩色（グラフ・カラーリング）問題は、グラフ理論におけるグラフラベリング（ラベル付け）の特殊なケースです。この問題では、グラフの各頂点（ノード）に対していずれかの色を割り当てていきます。ただし、彩色には重要な制約があり、隣接する2つの頂点に同じ色を割り当てることはできません。

この問題を解くには、一般的に貪欲法（グリーディアルゴリズム）が用いられます。ただし、貪欲法はその時点で最も有利な選択を繰り返す手法であるため、必ずしも最小色数での彩色が保証されるわけではない点に注意が必要です。

入力と出力

入力としてグラフの隣接行列を受け取り、出力として各ノードに割り当てられた色番号を表示します。以下は5つの頂点を持つグラフの例です。

入力:
グラフの隣接行列
0 0 1 0 1
0 0 1 1 1
1 1 0 1 0
0 1 1 0 1
1 1 0 1 0

出力:
Node: 0, Assigned with Color: 0
Node: 1, Assigned with Color: 0
Node: 2, Assigned with Color: 1
Node: 3, Assigned with Color: 2
Node: 4, Assigned with Color: 1

アルゴリズム

使用する関数は以下の形式です。

graphColoring(graph)

入力 − 与えられたグラフ。

出力 − 色が割り当てられた各ノード。

手順:
    色のリストを宣言する
    最初のノードに色 0 を設定する
    使用中の色と未使用の色を管理するための配列 colorUsed を定義する

    最初の頂点を除くすべての頂点 i について
        頂点 i を「未割り当て」としてマークする

    すべての頂点について colorUsed を false に初期化する
    最初の頂点を除くグラフ上のすべての頂点 u について
        u に隣接するすべての頂点 v について
            もし color[v] が割り当て済みならば
                colorUsed[color[v]] := true（その色を使用不可にする）

        色リスト内のすべての色 col について
            もしその色が未使用ならば
                ループを抜ける

        color[u] := col（見つかった色を割り当てる）
        u に隣接する各頂点 v について
            もし color[v] が割り当て済みならば
                colorUsed[color[v]] := false（次回の反復のために使用状態を解除）

    グラフ上のすべての頂点 u について
        ノードとその色を表示する
終了

サンプルプログラム（C++）

以下は、上記のアルゴリズムをC++で実装した例です。6つの頂点からなるグラフに対して、貪欲法により彩色を行います。

#include<iostream>
#define NODE 6
using namespace std;

int graph[NODE][NODE] = {
   {0, 1, 1, 1, 0, 0},
   {1, 0, 0, 1, 1, 0},
   {1, 0, 0, 1, 0, 1},
   {1, 1, 1, 0, 1, 1},
   {0, 1, 0, 1, 0, 1},
   {0, 0, 1, 1, 1, 0}
};

void graphColoring() {
   int color[NODE];
   color[0] = 0;          // 最初のノードに最初の色を割り当てる
   bool colorUsed[NODE];  // 色が使用済みかどうかを確認するための配列

   for(int i = 1; i<NODE; i++)
      color[i] = -1;      // 他のすべての頂点を未割り当てで初期化

   for(int i = 0; i<NODE; i++)
      colorUsed[i] = false;  // 初期状態ではどの色も選択されていない

   for(int u = 1; u<NODE; u++) {  // 残りの NODE - 1 個の頂点について処理
      for(int v = 0; v<NODE; v++) {
         if(graph[u][v]){
            if(color[v] != -1)     // 色が割り当て済みなら使用不可にする
               colorUsed[color[v]] = true;
         }
      }

      int col;
      for(col = 0; col<NODE; col++)
         if(!colorUsed[col])       // 未割り当ての色を探す
            break;

      color[u] = col;              // 見つかった色を割り当てる

      for(int v = 0; v<NODE; v++) { // 次の反復のために使用状態を false に戻す
         if(graph[u][v]) {
            if(color[v] != -1)
               colorUsed[color[v]] = false;
         }
      }
   }

   for(int u = 0; u<NODE; u++)
      cout << "Node: " << u << ", Assigned with Color: " << color[u] << endl;
}

int main() {
   graphColoring();
}

実行結果

Node: 0, Assigned with Color: 0
Node: 1, Assigned with Color: 0
Node: 2, Assigned with Color: 1
Node: 3, Assigned with Color: 2
Node: 4, Assigned with Color: 1