Bài toán tô màu

Psudo code Welsh-Powell:

procedure Welsh-Powell(Graph G)
    Sort vertices of G in decreasing order by degree
    Initialize an array Color[1..|V|] with 0 (indicating no color assigned)
    Let currentColor = 1

    for each vertex v in G
        if Color[v] = 0 then
            Color[v] = currentColor
            for each uncolored vertex u adjacent to v
                if Color[u] = 0 then
                    Color[u] = currentColor
            currentColor = currentColor + 1

    return Color

Giải thích:

• Đầu tiên, sắp xếp các đỉnh của đồ thị G theo thứ tự giảm dần của bậc (degree).
• Khởi tạo một mảng Color để lưu trữ màu của từng đỉnh, ban đầu các đỉnh đều chưa được tô màu (Color[v] = 0).
• Dùng biến currentColor để theo dõi màu hiện tại đang sử dụng.
• Duyệt qua từng đỉnh v của G:
  • Nếu đỉnh v chưa được tô màu (Color[v] = 0), tô nó bằng màu hiện tại (currentColor).
  • Sau đó, duyệt qua các đỉnh kề u của v và tô chúng cùng màu nếu chưa được tô.
  • Tăng currentColor lên 1 để sử dụng màu khác cho các đỉnh tiếp theo.
• Thuật toán trả về mảng Color, trong đó mỗi phần tử là màu tương ứng của từng đỉnh.

code C++:

#include <bits/stdc++.h>
using namespace std;

// Hàm để sắp xếp các đỉnh theo bậc giảm dần
vector<int> sortVerticesByDegree(const vector<vector<int>>& graph) {
    int V = graph.size();
    vector<int> degree(V);

    // Tính bậc của từng đỉnh
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (graph[i][j]) ++degree[i];
        }
    }

    // Sắp xếp các đỉnh theo bậc giảm dần
    vector<int> sortedVertices(V);
    for (int i = 0; i < V; ++i) {
        sortedVertices[i] = i; // Khởi tạo các đỉnh theo thứ tự ban đầu
    }
    sort(sortedVertices.begin(), sortedVertices.end(), [&degree](int a, int b) {
        return degree[a] > degree[b];
    });

    return sortedVertices;
}

// Hàm thực hiện thuật toán Welsh-Powell
void welshPowellColoring(const vector<vector<int>>& graph) {
    int V = graph.size();
    int result[100]; // Mảng lưu màu của các đỉnh, giả sử số đỉnh tối đa là 100
    fill(result, result + V, -1); // Khởi tạo mảng result với -1 (chưa tô màu)

    // Sắp xếp các đỉnh theo bậc giảm dần
    vector<int> sortedVertices = sortVerticesByDegree(graph);

    // Mảng để đánh dấu các màu đã sử dụng
    bool usedColors[100] = {false}; // Giả sử số màu tối đa là 100

    // Gán màu cho các đỉnh theo thứ tự đã sắp xếp
    for (int u : sortedVertices) {
        // Đánh dấu các màu đã sử dụng bởi các đỉnh kề
        for (int v = 0; v < V; ++v) {
            if (graph[u][v] && result[v] != -1) {
                usedColors[result[v]] = true;
            }
        }

        // Tìm màu đầu tiên có thể sử dụng
        int color;
        for (color = 0; color < V; ++color) {
            if (!usedColors[color]) {
                break;
            }
        }

        // Gán màu cho đỉnh u
        result[u] = color;

        // Đặt lại đánh dấu màu đã sử dụng
        fill(usedColors, usedColors + V, false);
    }

    // In kết quả
    for (int i = 0; i < V; ++i) {
        cout << "Dinh " << i << " -> Mau " << result[i] << endl;
    }
}

int main() {
    // Ma trận kề của đồ thị
    vector<vector<int>> graph = {
        {0, 1, 1, 0, 0, 0},
        {1, 0, 1, 1, 0, 0},
        {1, 1, 0, 1, 1, 0},
        {0, 1, 1, 0, 1, 1},
        {0, 0, 1, 1, 0, 1},
        {0, 0, 0, 1, 1, 0}
    };

    welshPowellColoring(graph);

    return 0;
}