Solveur de Coloration de Graphe

Pseudocode

La coloration gloutonne tient en trois lignes et produit toujours une coloration valide. Ce qu'elle ne produit pas nécessairement, c'est une coloration minimale, et l'ordre des sommets décide à quel point elle s'en approche.

ColorationGloutonne(graphe, ordre):
    couleur = {}
    pour chaque sommet v dans ordre:
        prises = { couleur[n] : n voisin de v, deja colorie }
        c = plus petit entier positif absent de prises
        couleur[v] = c
    renvoyer couleur

// Welsh-Powell: trier par degre decroissant
// DSatur: choisir a repetition le sommet non colorie ayant
//         le plus de voisins de couleurs distinctes (saturation),
//         en departageant par le degre

Le glouton n'utilise jamais plus que degré maximal plus un couleurs, car lorsque tu atteins un sommet il possède au plus autant de voisins et donc au plus autant de couleurs interdites. C'est une garantie réelle, mais elle peut rester très loin du nombre chromatique véritable. DSatur est l'amélioration pratique: choisir ensuite le sommet le plus contraint est exactement l'heuristique qui évite de se peindre dans un coin.

Exemple détaillé, étape par étape

Colorie un cycle de cinq sommets de façon gloutonne en ordre alphabétique, puis compare le résultat au nombre chromatique réel.

Graphe d'exemple: Cycle non orienté A-B, B-C, C-D, D-E et E-A.

1. Colorier A. Aucun voisin n'est encore colorié, A prend donc la couleur 1.
2. Colorier B. B est adjacent à A, de couleur 1, la plus petite disponible est donc la couleur 2.
3. Colorier C. C est adjacent à B (couleur 2) et à D encore non colorié. La couleur 1 est libre, C prend donc 1.
4. Colorier D. D est adjacent à C (couleur 1) et à E non colorié. La couleur 2 est libre, D prend donc 2.
5. Colorier E impose une troisième. E est adjacent à D (couleur 2) et à A (couleur 1). Les deux couleurs existantes sont prises, E réclame donc la couleur 3.

La coloration est A 1, B 2, C 1, D 2, E 3, soit trois couleurs, et une recherche exhaustive confirme que le nombre chromatique d'un cycle de cinq vaut bien 3. Le glouton s'est ici trouvé optimal. La raison pour laquelle trois sont nécessaires tient à la longueur impaire du cycle: les couleurs doivent alterner le long d'un cycle, et un cycle impair te ramène au départ en exigeant une couleur différente de celle qui s'y trouve déjà. Tout cycle pair se contente de 2.

Complexité et son origine

Temps: O(V + E) glouton, NP-difficile exact · Espace: O(V)

La coloration gloutonne examine chaque sommet une fois et inspecte chaque arête deux fois, une depuis chaque extrémité, elle est donc en O(V + E) avec O(V) d'espace pour le tableau des couleurs. Ce coût achète une coloration valide utilisant au plus degré maximal plus un couleurs, jamais un minimum garanti. Calculer le nombre chromatique réel est NP-difficile, et même l'approcher à un facteur V puissance 1 moins epsilon près est NP-difficile, ce qui est inhabituellement fort: pour la plupart des problèmes il existe une approximation décente, et pour la coloration essentiellement aucune. La 2-colorabilité fait exception et reste facile, puisqu'elle est exactement le test de bipartition en O(V + E). Décider la 3-colorabilité est déjà NP-complet.

Quand utiliser Coloration de Graphe, et quand l'éviter

Choisis selon le nombre de couleurs que tu anticipes et selon que tu exiges ou non le minimum véritable.

Pièges fréquents

• Supposer que le glouton donne le nombre chromatique. Il donne une coloration valide, pas minimale, et l'écart peut être important. Sur le graphe couronne aux parties {a1,a2,a3} et {b1,b2,b3} où ai est relié à bj dès que i diffère de j, l'ordre entrelacé a1,b1,a2,b2,a3,b3 fait utiliser 3 couleurs au glouton alors que le graphe est biparti et que 2 suffisent. Le même graphe dans l'ordre a1,a2,a3,b1,b2,b3 en utilise 2.
• Négliger le poids de l ordre des sommets. Il existe toujours un ordre atteignant le nombre chromatique véritable, et le trouver est aussi difficile que le problème de coloration lui-même. C'est pourquoi DSatur choisit dynamiquement au fil de l'exécution plutôt que de figer un ordre au départ.
• Confondre nombre chromatique et nombre de clique. Une clique de taille k impose au moins k couleurs, le nombre de clique est donc une borne inférieure, mais les deux peuvent différer. Les cycles impairs de longueur 5 ou plus exigent 3 couleurs sans contenir le moindre triangle.
• Espérer qu une bonne approximation existe. Contrairement à beaucoup de problèmes NP-difficiles, la coloration de graphes n'admet aucune approximation connue à facteur constant et de forts résultats de difficulté rendent son existence improbable. Les heuristiques peuvent bien se comporter en pratique sans offrir de garantie au pire cas.
• Oublier que les boucles la rendent impossible. Un sommet adjacent à lui-même ne peut jamais recevoir une couleur différente de la sienne, un graphe comportant une boucle n'admet donc aucune coloration propre. Rejette ces entrées avant de commencer.

Questions fréquentes

Qu'est-ce que la coloration de graphes?

La coloration de graphes attribue une couleur à chaque sommet de sorte que deux sommets adjacents n'en partagent jamais. Le plus petit nombre de couleurs qui fonctionne est le nombre chromatique du graphe. Elle modélise tout problème où des éléments en conflit doivent être séparés, comme planifier des examens pour qu'aucun étudiant n'en subisse deux simultanément.

Qu'est-ce que le nombre chromatique d'un graphe?

Le nombre minimal de couleurs nécessaire à une coloration propre. Un graphe biparti a un nombre chromatique de 2 ou moins, un cycle impair en a 3, et un graphe complet à n sommets en a n. Le calculer en général est NP-difficile, bien qu'une clique de taille k fournisse une borne inférieure immédiate de k.

L'algorithme glouton utilise-t-il toujours le moins de couleurs?

Non. Il produit toujours une coloration valide utilisant au plus degré maximal plus un couleurs, mais cela peut dépasser le nombre chromatique. Sur le graphe couronne, un graphe biparti ne nécessitant que 2 couleurs, un ordre malheureux en fait utiliser 3 au glouton. Il existe toujours un ordre atteignant l'optimum, mais le trouver est aussi difficile que le problème initial.

Quelle est la différence entre coloration gloutonne et DSatur?

Le glouton fixe un ordre de sommets à l'avance et colorie dans cet ordre. DSatur choisit le sommet suivant dynamiquement, prenant toujours celui qui compte le plus de voisins de couleurs distinctes et départageant par le degré. Cette attention au sommet le plus contraint rend DSatur optimal sur les graphes bipartis et bien meilleur en général, au prix de O(V au carré) au lieu de O(V + E).

À quoi sert la coloration de graphes?

À l'allocation de registres dans les compilateurs, où les registres sont les couleurs et les variables qui interfèrent sont adjacentes. Également aux plannings d'examens et d'équipes, à l'attribution de fréquences radio évitant les interférences entre émetteurs proches, à la résolution de sudokus et à la séparation de tâches conflictuelles dans tout problème d'allocation de ressources.