圖著色所需的最少顏色數

圖著色所需的最少顏色數是一個基本的圖論問題，它包括對頂點進行著色，使得沒有兩個相鄰的頂點具有相同的顏色。確定有效著色所需的最小顏色數量。貪婪著色是一種簡單且常用的技術，它根據頂點的鄰居逐個對頂點進行著色。回溯法也會仔細分析所有顏色分配。基於DSatur的圖著色優先考慮具有最高度和飽和度的頂點。

使用的方法

  • 貪婪著色

  • 回溯法

  • 圖著色

貪婪著色方法

貪婪著色技術使圖著色變得容易。它對第一個頂點進行著色，然後迭代其餘的頂點。它透過檢查其相鄰頂點來為每個頂點分配最小的顏色。這種“貪婪”技術會做出區域性最優的判斷，而不會考慮顏色消耗。貪婪著色易於應用，通常效果很好，儘管它可能無法提供最少的顏色數量。

演算法

  • 將大小為“numVertices”的陣列“colours”的所有成員初始化為-1。

  • 對第一個圖頂點0著色。

  • 對於從1到numVertices-1的每個頂點“v”，執行以下操作

    • 將相鄰頂點的顏色儲存在一個空集合“usedColors”中。

      迭代“v”的相鄰頂點

    • 將相鄰頂點的非零顏色新增到“usedColors”中。

    • 從0開始遞增，直到“usedColors”不包含最小的顏色。

    • 在“colours”陣列中為“v”賦予最小的顏色。

  • 找到“colours”陣列中使用的最大顏色，並返回+1作為“minColors”。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

// Structure to represent an edge in the graph
struct Edge {
    int src, dest;
};

// Function to add an edge to the graph
void addEdge(std::vector<std::vector<int>>& graph, int src, int dest) {
    graph[src].push_back(dest);
    graph[dest].push_back(src);
}

// Greedy Coloring Algorithm
int greedyColoring(const std::vector<std::vector<int>>& graph, int numVertices) {
    std::vector<int> colors(numVertices, -1);
    colors[0] = 0;

    for (int vertex = 1; vertex < numVertices; ++vertex) {
        std::unordered_set<int> usedColors;
        for (int neighbor : graph[vertex]) {
            if (colors[neighbor] != -1) {
                usedColors.insert(colors[neighbor]);
            }
        }

        int availableColor = 0;
        while (usedColors.count(availableColor) != 0) {
            ++availableColor;
        }

        colors[vertex] = availableColor;
    }

    return *std::max_element(colors.begin(), colors.end()) + 1;
}

int main() {
    // Example usage
    int numVertices = 6;
    std::vector<Edge> edges = {
        {0, 1},
        {0, 2},
        {1, 2},
        {1, 3},
        {2, 3},
        {3, 4},
        {4, 5}
    };
    int numEdges = edges.size();

    std::vector<std::vector<int>> graph(numVertices);
    for (const auto& edge : edges) {
        addEdge(graph, edge.src, edge.dest);
    }

    int minColorsGreedy = greedyColoring(graph, numVertices);
   
    std::cout << "Minimum number of colors (Greedy Coloring): " << minColorsGreedy << std::endl;
   
    return 0;
}

輸出

Minimum number of colors (Greedy Coloring): 3

回溯法

回溯法是一種查詢所有可行解的方法。在圖著色中，回溯法遞迴地為頂點分配顏色。當出現問題時，它會撤消顏色分配並考慮替代方案。回溯法可以確保對圖著色所需的最小顏色數量，儘管由於其徹底的搜尋，對於大型圖來說，它的計算成本很高。

演算法

  • 將大小為“numVertices”的陣列“colours”的所有成員初始化為-1。

  • 對於從1到numVertices的“numColors”

  • 如果graphColoringUtil(graph, numColors, colours, 0)返回true，則返回“numColors”作為“minColors”。

  • 如果沒有找到可接受的著色，則返回“numVertices”作為“minColors”。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

// Structure to represent an edge in the graph
struct Edge {
    int src, dest;
};

// Function to add an edge to the graph
void addEdge(std::vector<std::vector<int>>& graph, int src, int dest) {
    graph[src].push_back(dest);
    graph[dest].push_back(src);
}


// Backtracking Algorithm
bool isSafe(int vertex, const std::vector<std::vector<int>>& graph, const std::vector<int>& colors, int color) {
    for (int neighbor : graph[vertex]) {
        if (colors[neighbor] == color) {
            return false;
        }
    }
    return true;
}

bool graphColoringUtil(const std::vector<std::vector<int>>& graph, int numColors, std::vector<int>& colors, int vertex) {
    if (vertex == colors.size()) {
        return true;
    }

    for (int color = 0; color < numColors; ++color) {
        if (isSafe(vertex, graph, colors, color)) {
            colors[vertex] = color;
            if (graphColoringUtil(graph, numColors, colors, vertex + 1)) {
                return true;
            }
            colors[vertex] = -1;
        }
    }

    return false;
}

int backtrackingColoring(const std::vector<std::vector<int>>& graph, int numVertices) {
    std::vector<int> colors(numVertices, -1);

    for (int numColors = 1; numColors <= numVertices; ++numColors) {
        if (graphColoringUtil(graph, numColors, colors, 0)) {
            return numColors;
        }
    }

    return numVertices;
}

int main() {
    // Example usage
    int numVertices = 6;
    std::vector<Edge> edges = {
        {0, 1},
        {0, 2},
        {1, 2},
        {1, 3},
        {2, 3},
        {3, 4},
        {4, 5}
    };
    int numEdges = edges.size();

    std::vector<std::vector<int>> graph(numVertices);
    for (const auto& edge : edges) {
        addEdge(graph, edge.src, edge.dest);
    }

    int minColorsBacktracking = backtrackingColoring(graph, numVertices);
    std::cout << "Minimum number of colors (Backtracking): " << minColorsBacktracking << std::endl;

    return 0;
}

輸出

Minimum number of colors (Backtracking): 3

圖著色方法

複雜的圖著色啟發式演算法DSatur（最大飽和度）減少了顏色使用。首先對度數最高的頂點著色。接下來檢查飽和度，即每個頂點的鄰居使用的顏色數量。為了打破平局，DSatur會對飽和度最高的頂點著色。

這種方法根據頂點的度數和飽和度來最佳化顏色組合。

演算法

  • 將大小為“numVertices”的陣列“colours”初始化為-1。

  • 將大小為“numVertices”的“saturation”陣列初始化為0。

  • 使“saturationMap”為空。

  • 對圖中度數最高的頂點0著色。

  • 更新所選頂點的相鄰頂點的飽和度和saturationMap。

示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>

// Structure to represent an edge in the graph
struct Edge {
    int src, dest;
};

// Function to add an edge to the graph
void addEdge(std::vector<std::vector<int>>& graph, int src, int dest) {
    graph[src].push_back(dest);
    graph[dest].push_back(src);
}

// Graph Coloring using DSatur Algorithm
int getMaxDegreeVertex(const std::vector<std::vector<int>>& graph, const std::vector<int>& saturation) {
    int maxDegree = -1;
    int maxDegreeVertex = -1;

    for (int vertex = 0; vertex < graph.size(); ++vertex) {
        if (saturation[vertex] == -1 && graph[vertex].size() > maxDegree) {
            maxDegree = graph[vertex].size();
            maxDegreeVertex = vertex;
        }
    }

    return maxDegreeVertex;
}

int dsaturColoring(const std::vector<std::vector<int>>& graph, int numVertices) {
    std::vector<int> colors(numVertices, -1);
    std::vector<int> saturation(numVertices, -1);
    std::unordered_map<int, int> saturationMap;

    colors[0] = 0;

    for (int vertex = 1; vertex < numVertices; ++vertex) {
        for (int neighbor : graph[vertex]) {
            if (colors[neighbor] != -1) {
                saturation[vertex]++;
                saturationMap[colors[neighbor]]++;
            }
        }
    }

    while (*std::max_element(colors.begin(), colors.end()) == -1) {
        int maxDegreeVertex = getMaxDegreeVertex(graph, saturation);

        std::unordered_set<int> usedColors;
        for (int neighbor : graph[maxDegreeVertex]) {
            if (colors[neighbor] != -1) {
                usedColors.insert(colors[neighbor]);
            }
        }

        int availableColor = 0;
        while (usedColors.count(availableColor) != 0) {
            ++availableColor;
        }

        colors[maxDegreeVertex] = availableColor;

        for (int neighbor : graph[maxDegreeVertex]) {
            if (colors[neighbor] == -1) {
                saturation[neighbor]++;
            }
        }

        saturationMap.clear();
        for (int vertex = 0; vertex < numVertices; ++vertex) {
            if (colors[vertex] == -1) {
                saturationMap[saturation[vertex]]++;
            }
        }

        int maxSaturation = -1;
        for (auto& entry : saturationMap) {
            if (entry.second > maxSaturation) {
                maxSaturation = entry.second;
            }
        }

        std::vector<int> maxSaturationVertices;
        for (int vertex = 0; vertex < numVertices; ++vertex) {
            if (colors[vertex] == -1 && saturation[vertex] == maxSaturation) {
                maxSaturationVertices.push_back(vertex);
            }
        }

        if (maxSaturationVertices.size() > 1) {
            int maxDegree = -1;
            for (int vertex : maxSaturationVertices) {
                if (graph[vertex].size() > maxDegree) {
                    maxDegree = graph[vertex].size();
                    maxDegreeVertex = vertex;
                }
            }
        }
        else {
            maxDegreeVertex = maxSaturationVertices[0];
        }
    }

    return *std::max_element(colors.begin(), colors.end()) + 1;
}

int main() {
    // Example usage
    int numVertices = 6;
    std::vector<Edge> edges = {
        {0, 1},
        {0, 2},
        {1, 2},
        {1, 3},
        {2, 3},
        {3, 4},
        {4, 5}
    };
    int numEdges = edges.size();

    std::vector<std::vector<int>> graph(numVertices);
    for (const auto& edge : edges) {
        addEdge(graph, edge.src, edge.dest);
    }


    int minColorsDSatur = dsaturColoring(graph, numVertices);

    std::cout << "Minimum number of colors (DSatur): " << minColorsDSatur << std::endl;

    return 0;
}

輸出

Minimum number of colors (DSatur): 1

結論

總而言之，圖論中的最小顏色問題有很多應用。我們討論了貪婪著色、回溯法和DSatur圖著色來解決這個問題。貪婪著色很簡單，但它並不總是使用最少的顏色。回溯法可以確保最佳答案，但對於更大的網路來說，計算成本很高。DSatur的複雜啟發式演算法考慮頂點的度數和飽和度來最佳化圖著色。

更新於：2023年7月17日

693 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告