Tô màu đồ thị (Graph Coloring)

Bài toán tô màu đồ thị là trường hợp đặc biệt của gán nhãn đồ thị. Trong bài toán này, mỗi nút được tô một số màu. Tuy nhiên việc tô màu có ràng buộc: không được dùng cùng một màu cho hai đỉnh kề nhau.

Để giải quyết bài toán này, ta cần dùng thuật toán tham lam (greedy), nhưng nó không đảm bảo sử dụng số lượng màu tối thiểu.

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

Đầu vào: Ma trận kề của đồ thị.
0 0 1 0 1
0 0 1 1 1
1 1 1 0 1
0 1 0 1 0
1 1 0 1 0
Đầu ra:
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

Thuật toán

graphColoring(graph)
Đầu vào: Đồ thị cho trước.
Đầu ra: Mỗi nút với một số màu được gán cho nó.
Bắt đầu
  khai báo danh sách màu
  ban đầu đặt màu 0 cho nút đầu tiên
  định nghĩa mảng colorUsed để theo dõi màu nào đã dùng, màu nào chưa bao giờ dùng
  với mọi đỉnh i trừ nút đầu tiên, thực hiện
    đánh dấu i là chưa gán màu nào
  kết thúc
  đánh dấu colorUsed là false cho tất cả đỉnh
  với mọi đỉnh u trong đồ thị trừ đỉnh đầu tiên, thực hiện
    với mọi đỉnh v kề với u, thực hiện
      nếu color[v] chưa gán thì
        đánh dấu colorUsed[color[v]] := true
      kết thúc
    kết thúc
    với mọi màu col trong danh sách màu, thực hiện
      nếu màu chưa được dùng thì
        dừng vòng lặp
      kết thúc
    kết thúc
    color[u] := col
    với mỗi đỉnh v kề với u, thực hiện
      nếu color[v] chưa gán thì
        colorUsed[color[v]] := false
      kết thúc
    kết thúc
  kết thúc
  với mọi đỉnh u trong đồ thị, thực hiện
    hiển thị nút và màu của nó
  kết thúc
Kết thúc

Ví dụ (C++)

#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; // Gán màu đầu tiên cho nút đầu tiên
  bool colorUsed[NODE]; // Dùng để kiểm tra màu đã dùng hay chưa
  
  for(int i = 1; i < NODE; i++)
    color[i] = -1; // khởi tạo tất cả đỉnh khác chưa gán màu
  
  for(int i = 0; i < NODE; i++)
    colorUsed[i] = false; // ban đầu không màu nào được chọn
  
  for(int u = 1; u < NODE; u++) {
    // cho tất cả NODE - 1 đỉnh khác
    for(int v = 0; v < NODE; v++) {
      if(graph[u][v]) {
        if(color[v] != -1) // khi một màu đã gán, làm cho nó không khả dụng
          colorUsed[color[v]] = true;
      }
    }
    
    int col;
    for(col = 0; col < NODE; col++)
      if(!colorUsed[col]) // tìm một màu chưa được gán
        break;
    
    color[u] = col; // gán màu tìm được vào danh sách
    
    // cho vòng lặp tiếp theo làm tính khả dụng màu về false
    for(int v = 0; v < NODE; v++) {
      if(graph[u][v]) {
        if(color[v] != -1)
          colorUsed[color[v]] = false;
      }
    }
  }
  
  for(int u = 0; u < NODE; u++)
    cout << "Color: " << u << ", Assigned with Color: " << color[u] << endl;
}

int main() {
  graphColoring();
}

Đầu ra

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