ปัญหาการระบายสีกราฟ M สี (M-Coloring Problem)

บทนำ

กำหนดกราฟไม่มีทิศทางและ m สี ต้องการทราบว่าสามารถระบายสีโหนดด้วย m สีได้หรือไม่ โดยโหนดที่ติดกัน (Adjacent) ต้องไม่มีสีเดียวกัน หากเป็นไปได้ ให้แสดงสีของแต่ละโหนด

เริ่มจากโหนด 0 ลองระบายสีทีละโหนด ตรวจสอบความปลอดภก่อนระบาย (Safe Color = โหนดติดกันไม่มีสีซ้ำ)

อินพุตและเอาต์พุต

Input: เมทริกซ์ติดกันของกราฟ G(V,E) และ m = 3
Output: Assigned Colors are: 1 2 3 2
        (Node 0->Color 1, Node 1->Color 2, Node 2->Color 3, Node 3->Color 2)

อัลกอริทึม

isValid(vertex, colorList, col)

Input: โหนด, รายการสี, สีที่ลองระบาย
Output: True ถ้าระบายสีถูกต้อง

Begin
    for ทุกโหนด v ในกราฟ do
        if มีเส้นขอบ (v,i) และ col = colorList[i] then return false
    done
    return true
End

graphColoring(colors, colorList, vertex)

Input: จำนวนสีสูงสุด, รายการสีของโหนด, โหนดเริ่มต้น
Output: True ถ้าระบายสีสำเร็จ

Begin
    if ตรวจสอบครบโหนดแล้ว return true
    for สี col จาก 1 ถึง colors do
        if isValid(vertex, colorList, col) then
            colorList[vertex] = col
            if graphColoring(colors, colorList, vertex+1) return true
            colorList[vertex] = 0  // backtrack
    done
    return false
End

ตัวอย่างโค้ด (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); }

ผลลัพธ์

Assigned Colors are: 1 2 3 2