M-착색 문제

이 문제에서는 무방향 그래프가 제공됩니다. m 색상도 제공됩니다. 문제는 그래프의 인접한 두 정점이 동일한 색상을 가지지 않도록 m개의 다른 색상을 가진 노드를 할당하는 것이 가능한지 찾는 것입니다. 솔루션이 존재하는 경우 어떤 정점에 어떤 색상이 할당되었는지 표시합니다.

정점 0부터 시작하여 다른 노드에 하나씩 색상을 할당하려고 합니다. 하지만 할당하기 전에 색상이 안전한지 확인해야 합니다. 인접한 정점에 같은 색상이 포함되어 있으면 색상은 안전하지 않습니다.

입력 및 출력

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, 할당하려는 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

graphColoring(색상, 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