ArithmétiqueMéthode · Glossaire
algorithme de coloration
Un algorithme de coloration de graphe est un algorithme de théorie des graphes dont l'objectif est d'attribuer une couleur à chaque sommet d'un graphe non orienté, de sorte que deux sommets reliés par une arête (adjacents) reçoivent des couleurs différentes. Le nombre minimal de couleurs nécessaires pour colorier un graphe de la sorte est appelé le nombre chromatique du graphe. Parmi les algorithmes de coloration, l'algorithme de Welsh et Powell produit une coloration valide en utilisant un nombre de couleurs raisonnable (les sommets sont traités par ordre de degré décroissant), mais ne garantit pas que la coloration obtenue est minimale, c'est-à-dire qu'elle utilise exactement le nombre chromatique.
Sommaire
Ce que vous allez apprendre
- Définir une coloration valide et le nombre chromatique.
- Appliquer les étapes de Welsh et Powell dans un ordre explicite.
- Contrôler une coloration et reconnaître qu'elle peut ne pas être minimale.
- Repérer l'effet des égalités de degrés et le blocage causé par une boucle.
En clair
Imaginez des points reliés par des traits. Il faut peindre les points de sorte que les deux extrémités de chaque trait n'aient jamais la même couleur. Une couleur peut donc servir plusieurs fois, à condition que les points concernés ne soient pas voisins.
Un algorithme de coloration choisit ces couleurs selon une procédure précise. Il fournit toujours une répartition sans conflit lorsqu'une telle coloration existe. En revanche, une procédure rapide peut employer plus de couleurs que le minimum réellement nécessaire.
Définition
Un algorithme de coloration des sommets s'applique à un graphe non orienté. Les sommets forment un ensemble noté V et les arêtes un ensemble noté E. Une coloration attribue à chaque sommet v une couleur c(v). Elle est valide lorsque toute arête reliant deux sommets u et v vérifie . Les couleurs sont seulement des catégories : des nombres, des lettres ou des teintes peuvent les représenter.
Le plus petit nombre de couleurs d'une coloration valide est le nombre chromatique du graphe, noté χ(G). Une coloration qui utilise k couleurs prouve seulement que χ(G) ≤ k ; elle ne prouve pas que k est minimal. Welsh et Powell est une méthode gloutonne : elle traite d'abord les sommets de plus grand degré, c'est-à-dire ceux qui ont le plus de voisins, puis construit successivement des classes de sommets compatibles. Elle garantit la validité de la coloration obtenue, mais son résultat peut dépendre de l'ordre choisi entre sommets de même degré et dépasser χ(G).
Le principe
Pour appliquer Welsh et Powell :
1. Classez les sommets par degré décroissant ; fixez un ordre en cas d'égalité.
2. Donnez une nouvelle couleur au premier sommet non colorié de la liste.
3. Parcourez le reste de la liste et donnez cette couleur à chaque sommet non colorié qui n'est adjacent à aucun sommet déjà porteur de cette couleur.
4. Reprenez à l'étape 2 jusqu'à ce que tous les sommets soient coloriés.
1. Classez les sommets par degré décroissant ; fixez un ordre en cas d'égalité.
2. Donnez une nouvelle couleur au premier sommet non colorié de la liste.
3. Parcourez le reste de la liste et donnez cette couleur à chaque sommet non colorié qui n'est adjacent à aucun sommet déjà porteur de cette couleur.
4. Reprenez à l'étape 2 jusqu'à ce que tous les sommets soient coloriés.
Le point d'arrêt est atteint lorsque chaque sommet a reçu exactement une couleur. Un contrôle final vérifie que les extrémités de chaque arête ont des couleurs différentes.
Quand l'utiliser
La méthode demande un graphe non orienté dont les sommets et les arêtes sont connus. Le degré de chaque sommet doit pouvoir être compté, puis les égalités de degrés doivent être départagées par un ordre fixé. Le résultat est une coloration valide et un nombre de couleurs utilisé ; ce nombre constitue une borne supérieure du nombre chromatique, pas nécessairement sa valeur.
Un graphe qui possède une boucle, c'est-à-dire une arête reliant un sommet à lui-même, fournit un contre-cas concret : la contrainte imposerait au même sommet deux couleurs différentes. Aucune coloration valide des sommets n'existe alors au sens usuel. Il faut supprimer la boucle si elle ne représente pas un conflit pertinent, ou reformuler le modèle avant d'appliquer l'algorithme.
Un exemple, pas à pas
Considérons les sommets A1, A2, A3, B1, B2 et B3. Chaque Ai est relié aux Bj dont l'indice j diffère de i, sans autre arête. Tous ont donc le degré 2. Choisissons l'ordre A1, B1, A2, B2, A3, B3.
1. A1 reçoit la couleur 1 ; B1, qui ne lui est pas adjacent, reçoit aussi la couleur 1.
2. A2 est adjacent à B1 : il reçoit la couleur 2. B2 peut partager cette couleur.
3. A3 est adjacent à B1 et B2 : il reçoit la couleur 3. B3 la partage.
2. A2 est adjacent à B1 : il reçoit la couleur 2. B2 peut partager cette couleur.
3. A3 est adjacent à B1 et B2 : il reçoit la couleur 3. B3 la partage.
Les trois classes obtenues sont {A1, B1}, {A2, B2} et {A3, B3}. Aucune des six arêtes ne joint les sommets d'une même paire : la coloration est valide. Pourtant, deux couleurs suffisent en coloriant tous les A d'une couleur et tous les B d'une autre. Le nombre chromatique vaut donc 2, et cette exécution gloutonne n'est pas minimale.
En pratique
Pour répartir des activités incompatibles entre plusieurs créneaux, chaque activité devient un sommet et chaque incompatibilité une arête. La coloration donne des groupes sans conflit. Si les activités ont déjà des horaires imposés, un modèle d'ordonnancement est préférable, car la seule adjacency ne décrit plus toutes les contraintes.
Pour partager une ressource entre des objets qui se gênent, les couleurs représentent des canaux ou des catégories disponibles. Welsh et Powell fournit rapidement une affectation exploitable. Si le coût varie selon la couleur ou si certaines couleurs sont interdites à certains sommets, il faut employer une méthode de coloration avec contraintes plutôt que la version simple.
Pour chercher le minimum, la coloration gloutonne sert de première borne : le nombre de couleurs obtenu donne une solution valide à améliorer. Si prouver l'optimalité est indispensable, il faut compléter cette solution par une recherche exacte ou par une preuve qu'aucune coloration avec moins de couleurs n'existe.
À ne pas confondre
La coloration des sommets ne doit pas être confondue avec la coloration des arêtes. Dans la première, deux sommets reliés doivent différer ; dans la seconde, ce sont deux arêtes ayant une extrémité commune. Sur un triangle, les deux problèmes utilisent trois couleurs, mais leurs couleurs sont portées par des objets différents.
Une coloration n'est pas non plus un simple étiquetage de graphe. Un étiquetage peut attribuer des valeurs aux sommets sans interdire l'égalité entre voisins. Dès que deux sommets adjacents portent la même valeur, l'étiquetage peut rester valable pour son propre objectif, mais il ne constitue pas une coloration valide.
Limites et pièges
Le nombre de couleurs produit par Welsh et Powell doit être lu comme le résultat d'une exécution, non comme le nombre chromatique. Trois pièges permettent de tester cette distinction.
Une solution valide peut ne pas être minimale
Dans l'exemple à six sommets, la procédure utilise trois couleurs sans créer de conflit, alors qu'une coloration à deux couleurs existe. Le symptôme est l'existence d'une meilleure répartition. Il faut donc distinguer la validité, contrôlée arête par arête, de la minimalité, qui exige une preuve supplémentaire.
Les degrés égaux laissent un choix
Lorsque plusieurs sommets ont le même degré, la règle décroissante ne fixe pas leur ordre relatif. Deux départages peuvent donc conduire à des nombres de couleurs différents. Il faut annoncer l'ordre retenu, puis essayer d'autres départages si l'on cherche à réduire la coloration.
Une boucle bloque la règle
Avec une boucle, un sommet est adjacent à lui-même : aucune couleur ne peut satisfaire la contrainte. Le blocage apparaît avant même le choix d'un ordre. Il faut corriger ou reformuler le graphe, plutôt que d'ajouter toujours plus de couleurs.
Pour aller plus loin
La fiche coloration d'un graphe replace la procédure parmi les propriétés et les usages généraux d'une coloration.
La fiche nombre chromatique d'un graphe approfondit le minimum que l'algorithme glouton cherche à approcher sans toujours l'atteindre.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres