การระบายสีกราฟ (Graph Coloring)

ปัญหาการระบายสีกราฟ (Graph Coloring) เป็นกรณีพิเศษของการติดป้ายกำกับกราฟ (Graph Labeling) โดยแต่ละโหนดจะถูกระบายสี แต่มีข้อจำกัดคือ ไม่สามารถใช้สีเดียวกันสำหรับโหนดที่ติดกันได้ (Adjacent Vertices)

การแก้ปัญหานี้ใช้ Greedy Algorithm แต่ไม่รับประกันว่าจะใช้สีน้อยที่สุด (Chromatic Number)

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
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

Output:
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

อัลกอริทึม

graphColoring(graph)

Input: กราฟที่กำหนด

Output: แต่ละโหนดพร้อมสีที่กำหนด

Begin
  ประกาศรายการสี
  ตั้งสี 0 ให้โหนดแรก
  กำหนดอาร์เรย์ colorUsed เพื่อติดตามสีที่ใช้แล้ว
  
  for ทุกโหนด i ยกเว้นโหนดแรก do
    ทำเครื่องหมาย i ว่ายังไม่ได้กำหนดสี
  done
  
  ตั้ง colorUsed = false สำหรับทุกสี
  
  for ทุกโหนด u ในกราฟ ยกเว้นโหนดแรก do
    for ทุกโหนด v ที่ติดกับ u do
      if color[v] ถูกกำหนดแล้ว then
        colorUsed[color[v]] := true
      end if
    done
    
    for ทุกสี col ในรายการสี do
      if สียังไม่ถูกใช้ then หยุดลูป
    done
    
    color[u] := col
    
    for ทุกโหนด v ที่ติดกับ u do
      if color[v] ถูกกำหนดแล้ว then
        colorUsed[color[v]] := false
      end if
    done
  done
  
  for ทุกโหนด u แสดงโหนดและสีที่ได้
End

ตัวอย่างโค้ด (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;
  
  bool colorUsed[NODE];
  for(int i = 1; i < NODE; i++) color[i] = -1;
  for(int i = 0; i < NODE; i++) colorUsed[i] = false;
  
  for(int u = 1; u < NODE; u++) {
    for(int v = 0; v < NODE; v++) {
      if(graph[u][v]) {
        if(color[v] != -1)
          colorUsed[color[v]] = true;
      }
    }
    
    int col;
    for(col = 0; col < NODE; col++)
      if(!colorUsed[col]) break;
    
    color[u] = col;
    
    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();
}

ผลลัพธ์

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