M-着色の問題

この問題では、無向グラフが表示されます。 m色もご用意しております。問題は、グラフの2つの隣接する頂点が同じ色にならないように、m個の異なる色のノードを割り当てることができるかどうかを見つけることです。解決策が存在する場合は、どの頂点にどの色が割り当てられているかを表示します。

頂点0から始めて、色を1つずつ異なるノードに割り当てようとします。ただし、割り当てる前に、色が安全かどうかを確認する必要があります。隣接する頂点に同じ色が含まれているかどうかにかかわらず、色は安全ではありません。

入力と出力

Input:
The adjacency matrix of a graph G(V, E) and an integer m, which indicates the maximum number of colors that can be used.


Let the maximum color m = 3.
Output:
This algorithm will return which node will be assigned with which color. If the solution is not possible, it will return false.
For this input the assigned colors are:
Node 0 -> color 1
Node 1 -> color 2
Node 2 -> color 3
Node 3 -> color 2

アルゴリズム

isValid（vertex、colorList、col）

入力- 頂点、チェックするcolorList、および割り当てようとしているcolor。

出力- 色の割り当てが有効な場合はtrue、それ以外の場合はfalse。

Begin
   for all vertices v of the graph, do
      if there is an edge between v and i, and col = colorList[i], then
         return false
   done
   return true
End

グラフ彩色（色、colorList、頂点）

入力- 最も可能性のある色、頂点がどの色で色付けされているリスト、および開始頂点。​​

出力- 色が割り当てられている場合はtrue、それ以外の場合はfalse。

Begin
   if all vertices are checked, then
      return true
   for all colors col from available colors, do
      if isValid(vertex, color, col), then
         add col to the colorList for vertex
         if graphColoring(colors, colorList, vertex+1) = true, then
            return true
         remove color for vertex
   done
   return false
End

例

#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) {    //check whether putting a color valid for v
   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)    //when all vertices are considered
      return true;

   for (int col = 1; col <= colors; col++) {
      if (isValid(vertex,color, col)) {     //check whether color col is valid or not
         color[vertex] = col;
         if (graphColoring (colors, color, vertex+1) == true)    //go for additional vertices
            return true;
                   
         color[vertex] = 0;
      }
   }
   return false; //when no colors can be assigned
}

bool checkSolution(int m) {
   int *color = new int[V];    //make color matrix for each vertex

   for (int i = 0; i < V; i++)
      color[i] = 0;      //initially set to 0

   if (graphColoring(m, color, 0) == false) {    //for vertex 0 check graph coloring
      cout << "Solution does not exist.";
      return false;
   }
   showColors(color);
   return true;
}

int main() {
   int colors = 3;      // Number of colors
   checkSolution (colors);
}

出力

Assigned Colors are:
1 2 3 2