Bài toán M tô màu (M-Coloring Problem)

Giới thiệu

Cho đồ thị vô hướng và m màu. Tô màu các đỉnh sao cho hai đỉnh kề không cùng màu. In ra màu của mỗi đỉnh nếu có lời giải.

Từ đỉnh 0, thử gán màu lần lượt. Trước khi gán kiểm tra an toàn: màu không trùng với đỉnh kề.

Đầu vào và Đầu ra

Đầu vào: Ma trận kề đồ thị G(V,E) và số màu m = 3. 
Đầu ra: Màu gán cho các đỉnh:
Node 0 -> color 1
Node 1 -> color 2
Node 2 -> color 3
Node 3 -> color 2

Thuật toán

isValid(vertex, colorList, col)

Begin
  với mọi đỉnh v của đồ thị làm:
    nếu có cạnh (v, i) VÀ col = colorList[i] thì return false
  done
  return true
End

graphColoring(colors, colorList, vertex)

Begin
  nếu tất cả đỉnh đã xét thì return true
  với màu col từ 1 đến colors làm:
    nếu isValid(vertex, colorList, col) thì
      colorList[vertex] := col
      nếu graphColoring(colors, colorList, vertex+1) thì return true
      xóa màu cho vertex
  done
  return false
End

Ví dụ (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) {
  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)) {
      color[vertex] = col;
      if (graphColoring(colors, color, vertex+1)) 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;
  if (!graphColoring(m, color, 0)) { cout << "Solution does not exist."; return false; }
  showColors(color); return true;
}

int main() { int colors = 3; checkSolution(colors); }

Kết quả đầu ra

Assigned Colors are: 1 2 3 2