循環グラフの彩色指数(クロマティックインデックス)を求めるC++プログラム

彩色指数(クロマティックインデックス)とは、与えられたグラフの辺彩色に必要な色数の最大値のことです。本記事では、循環グラフの彩色指数を求めるC++プログラムを紹介します。

アルゴリズム

このプログラムの処理の流れは以下のとおりです。

開始
    頂点数「n」と辺数「e」を入力として受け取る。
    グラフの「e」個の辺について、頂点ペアをedge[][]に入力する。
    関数ChromaticIndex()でグラフの辺を彩色する:
    A) 現在の辺に色cを割り当てる。
    B) 隣接する辺の中に同じ色が存在する場合、その色を破棄し、
       flagラベルに戻って次の色で再試行する。
    C) 循環グラフの彩色指数を出力する。
    各辺の色を出力する。
終了

サンプルコード

以下が実際のC++による実装例です。貪欲法(greedy法)を用いて、各辺に対して隣接辺と衝突しない最小の色を順番に割り当てていきます。

#include<iostream>
using namespace std;
int ChromaticIndex(int ed[][3], int e) {
   int i, c, j, max = -1;
   // 各辺「i」に有効な色を割り当てる
   for(i = 0; i < e; i++) {
      c = 1;
      flag:
         // 現在の辺に色を割り当てる
         ed[i][2] = c;
         for(j = 0; j < e; j++) {
            if(j == i)
               continue;
               // 辺iに隣接する辺の色をチェックする
               if(ed[j][0] == ed[i][0] || ed[j][0] == ed[i][1] || ed[j][1] == ed[i][0] || ed[j][1] == ed[i][1]) {
                  if(ed[j][2] == ed[i][2]) {
                     c++;
                     goto flag;
                  }
               }
         }
   }
   // 彩色指数を求めて返す
   for(i = 0; i < e; i++) {
      if(max < ed[i][2])
         max = ed[i][2];
   }
   return max;
}
int main() {
   int i, v, e, j, max = -1;
   cout<<"Enter the number of vertices of the graph: ";
   cin>>v;
   cout<<"Enter the number of edges of the graph: ";
   cin>>e;
   int ed[e][3];
   for(i = 0; i < e; i++) {
      cout<<"\nEnter the vertex pair for edge "<<i+1;
      cout<<"\nV(1): ";
      cin>>ed[i][0];
      cout<<"V(2): ";
      cin>>ed[i][1];
      ed[i][2] = -1;
   }
   cout<<"\n\nThe chromatic index of the given graph is: "<<ChromaticIndex(ed , e);
   for(i = 0; i < e; i++)
      cout<<"\nThe color of the edge between vertex n(1):"<<ed[i][0]<<" and n(2):"<<ed[i][1]<<" is: color"<<ed[i][2]<<".";
      return 0;
}

コードの解説

• ChromaticIndex関数:各辺に対して色1から順に割り当てを試みます。隣接する辺(頂点を共有する辺)に同じ色が使われている場合は、次の色を試します。
• edge配列:ed[i][0]とed[i][1]には辺の両端の頂点を、ed[i][2]には割り当てられた色を格納します。
• 最大色数の計算:すべての辺の彩色が完了した後、使用された色の最大値が彩色指数となります。

実行結果

Enter the number of vertices of the graph:4
Enter the number of edges of the graph: 5
Enter the vertex pair for edge 1
V(1): 2
V(2):1
Enter the vertex pair for edge 2
V(1): 3
V(2): 2
Enter the vertex pair for edge 3
V(1): 3
V(2): 1
Enter the vertex pair for edge 4
V(1): 4
V(2): 2
Enter the vertex pair for edge 5
V(1):1
V(2): 3
The chromatic index of the given graph is: 4
The color of the edge between vertex n(1):2 and n(2):1 is: color1.
The color of the edge between vertex n(1):3 and n(2):2 is: color2.
The color of the edge between vertex n(1):3 and n(2):1 is: color3.
The color of the edge between vertex n(1):4 and n(2):2 is: color3.
The color of the edge between vertex n(1):1 and n(2):3 is: color4.

まとめ

このプログラムでは、貪欲法によってグラフの辺彩色を行い、その結果得られる色数の最大値である彩色指数を求めています。上記の実行例では、4つの頂点と5つの辺を持つグラフに対して、彩色指数は4となりました。なお、ヴィジングの定理によれば、単純グラフの彩色指数は最大次数Δに対してΔまたはΔ+1のいずれかになることが知られています。