Algorithme de coloration du tracé Welsh-Powell

La coloration graphique est un problème clé dans les technologies de l'information et a de nombreuses applications dans des domaines tels que la planification, l'attribution de registres et la coloration de cartes. L'algorithme de Welsh-Powell est un moyen efficace de colorer un graphique, garantissant que les sommets proches ont une variété de nuances tout en utilisant moins de couleurs. Dans cet article, nous examinerons 2 façons de créer l'algorithme de Welsh-Powell à l'aide d'algorithmes C++.

Méthode à utiliser

• Tri séquentiel des sommets

• Tri maximal du premier sommet

Tri séquentiel des sommets

Dans la première technique, les couleurs sont attribuées aux sommets par ordre décroissant de leurs degrés. Cette technique garantit que les sommets de plus grande étendue qui ont généralement plus de voisins sont colorés en premier.

Algorithme

• Déterminez le niveau de chaque sommet du graphique.

• Déterminez le degré des sommets et triez-les par ordre décroissant.

• Définissez la couleur attribuée pour chaque position de sommet dans le tableau.

• Répétez l'étape 2 pour les sommets dans l'ordre déterminé ici.

• Attribuez à chaque sommet la couleur minimale qui n'est pas encore utilisée par ses sommets voisins.

Exemple

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Graph structure
struct Graph {
    int V;  // Number of vertices
    vector<vector<int>> adj;  // Adjacency list

    // Constructor
    Graph(int v) : V(v), adj(v) {}

    // Function to add an edge between two vertices
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
};

// Function to compare vertices based on weight
bool compareWeights(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
}

// Function to perform graph coloring using Welsh-Powell algorithm
void graphColoring(Graph& graph) {
    int V = graph.V;
    vector<pair<int, int>> vertexWeights;

    // Assign weights to each vertex based on their degree
    for (int v = 0; v < V; v++) {
        int weight = graph.adj[v].size();
        vertexWeights.push_back(make_pair(v, weight));
    }

    // Sort vertices in descending order of weights
    sort(vertexWeights.begin(), vertexWeights.end(), compareWeights);

    // Array to store colors assigned to vertices
    vector<int> color(V, -1);

    // Assign colors to vertices in the sorted order
    for (int i = 0; i < V; i++) {
        int v = vertexWeights[i].first;

        // Find the smallest unused color for the current vertex
        vector<bool> usedColors(V, false);
        for (int adjVertex : graph.adj[v]) {
            if (color[adjVertex] != -1)
                usedColors[color[adjVertex]] = true;
        }

        // Assign the smallest unused color to the current vertex
        for (int c = 0; c < V; c++) {
            if (!usedColors[c]) {
                color[v] = c;
                break;
            }
        }
    }

    // Print the coloring result
    for (int v = 0; v < V; v++) {
        cout << "Vertex " << v << " is assigned color " << color[v] << endl;
    }
}

int main() {
    // Create a sample graph
    Graph graph(6);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(4, 5);

    // Perform graph coloring
    graphColoring(graph);

    return 0;
}

Sortie

Vertex 0 is assigned color 2
Vertex 1 is assigned color 0
Vertex 2 is assigned color 1
Vertex 3 is assigned color 2
Vertex 4 is assigned color 0
Vertex 5 is assigned color 1

Tri maximal du premier sommet

Semblable à la première méthode, la deuxième méthode consiste à disposer les sommets par ordre décroissant en fonction de leur degré. Cette approche colore d'abord le sommet du plus haut degré, puis colore de manière récursive ses voisins non colorés, plutôt que d'attribuer des couleurs de manière séquentielle.

Algorithme

• Déterminez le degré de chaque sommet du graphique.

• Déterminez le degré des sommets et triez-les par ordre décroissant.

• Définissez la couleur attribuée pour chaque position de sommet dans le tableau.

• Commencez l'ombrage à partir du sommet avec le degré maximum.

• Sélectionnez la plus petite couleur disponible pour chaque voisin du sommet actuellement non coloré.

Exemple

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

using namespace std;

class Graph {
private:
    int numVertices;
    vector<unordered_set<int>> adjacencyList;

public:
    Graph(int vertices) {
        numVertices = vertices;
        adjacencyList.resize(numVertices);
    }

    void addEdge(int src, int dest) {
        adjacencyList[src].insert(dest);
        adjacencyList[dest].insert(src);
    }

    int getNumVertices() {
        return numVertices;
    }

    unordered_set<int>& getNeighbors(int vertex) {
        return adjacencyList[vertex];
    }
};

void welshPowellLargestFirst(Graph graph) {
    int numVertices = graph.getNumVertices();
    vector<int> colors(numVertices, -1);

    vector<pair<int, int>> largestFirst;
    for (int i = 0; i < numVertices; i++) {
        largestFirst.push_back(make_pair(graph.getNeighbors(i).size(), i));
    }

    sort(largestFirst.rbegin(), largestFirst.rend()); 
    int numColors = 0;
    for (const auto& vertexPair : largestFirst) {
        int vertex = vertexPair.second;

        if (colors[vertex] != -1) {
            continue; // Vertex already colored
        }

        colors[vertex] = numColors;

        for (int neighbor : graph.getNeighbors(vertex)) {
            if (colors[neighbor] == -1) {
                colors[neighbor] = numColors;
            }
        }

        numColors++;
    }

    // Print assigned colors
    for (int i = 0; i < numVertices; i++) {
        cout << "Vertex " << i << " - Color: " << colors[i] << endl;
    }
}

int main() {
    Graph graph(7);

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(0, 3);
    graph.addEdge(1, 4);
    graph.addEdge(1, 5);
    graph.addEdge(2, 6);
    graph.addEdge(3, 6);

    welshPowellLargestFirst(graph);

    return 0;
}

Sortie

Vertex 0 - Color: 0
Vertex 1 - Color: 0
Vertex 2 - Color: 1
Vertex 3 - Color: 1
Vertex 4 - Color: 0
Vertex 5 - Color: 0
Vertex 6 - Color: 1

Conclusion

Cet article de blog analyse deux manières différentes de créer la technique de coloration du diagramme Welsh Powell à l'aide d'algorithmes C++. Chaque méthode adopte une stratégie différente lors du tri des sommets et de l'attribution des couleurs, ce qui donne lieu à une méthode de coloration graphique efficace et optimisée. En utilisant ces techniques, nous pouvons réduire efficacement le nombre de couleurs requises tout en garantissant que les sommets proches contiennent des couleurs différentes. Grâce à son adaptabilité et sa simplicité, l'algorithme de Welsh-Powell reste un outil utile dans diverses applications d'ombrage de graphiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!