ArithmétiqueMéthode · Glossaire
algorithme de Welsh et Powell
En théorie des graphes, l'algorithme de Welsh et Powell est un algorithme glouton de coloration propre des sommets d'un graphe. Il ordonne d'abord les sommets par degré décroissant, puis leur attribue séquentiellement la plus petite couleur disponible ne créant pas de conflit avec les sommets adjacents déjà colorés. Cette heuristique produit une coloration correcte utilisant un nombre de couleurs raisonnable, sans toutefois garantir que ce nombre est minimal (c'est-à-dire égal au nombre chromatique du graphe).
Sommaire
Ce que vous allez apprendre
- Ordonner les sommets et attribuer les couleurs étape par étape.
- Vérifier une coloration sur un graphe de six sommets.
- Distinguer coloration propre, coloration minimale et nombre chromatique.
- Repérer l’effet des ex æquo, des composantes séparées et des boucles.
En clair
Imaginez six activités, certaines incompatibles entre elles, à répartir dans des créneaux. Chaque activité devient un sommet, chaque incompatibilité une arête et chaque créneau une couleur. Deux sommets reliés doivent recevoir des couleurs différentes.
Welsh et Powell commence par les sommets qui ont le plus de voisins. Il les traite ensuite un à un et choisit chaque fois la première couleur qui ne crée aucun conflit. Le procédé donne vite une répartition valable, mais pas toujours la plus économe en couleurs.
Définition
L’algorithme de Welsh et Powell est une heuristique gloutonne de coloration propre des sommets d’un graphe simple. Une coloration est propre lorsque deux sommets reliés par une arête portent toujours des couleurs différentes. Le degré d’un sommet est le nombre d’arêtes qui le relient à ses voisins.
La méthode classe d’abord tous les sommets par degré décroissant. Si plusieurs sommets ont le même degré, un ordre de départ doit les départager. Elle parcourt ensuite cette liste et attribue à chaque sommet la couleur de plus petit rang absente chez ses voisins déjà colorés. Une couleur supplémentaire est ouverte seulement si toutes les couleurs déjà utilisées sont interdites.
Le résultat est toujours une coloration propre, y compris pour un graphe non connexe. En revanche, le nombre de couleurs obtenu peut dépendre de l’ordre choisi entre sommets de même degré. Il constitue une borne supérieure du nombre chromatique, qui est le minimum de couleurs nécessaire pour colorer proprement le graphe, et non sa valeur garantie.
Le principe
Pour un graphe simple fini, la procédure s’arrête lorsque tous les sommets sont colorés.
1. Ordonner les sommets par degré décroissant et fixer explicitement l’ordre des ex æquo.
2. Prendre le premier sommet non coloré de cette liste.
3. Lui attribuer la couleur de plus petit rang qui n’apparaît chez aucun de ses voisins déjà colorés.
4. Répéter les étapes 2 et 3 jusqu’au dernier sommet.
2. Prendre le premier sommet non coloré de cette liste.
3. Lui attribuer la couleur de plus petit rang qui n’apparaît chez aucun de ses voisins déjà colorés.
4. Répéter les étapes 2 et 3 jusqu’au dernier sommet.
À chaque attribution, la règle exclut exactement les couleurs créant un conflit avec une arête déjà examinée.
Quand l'utiliser
La méthode s’applique à un graphe fini dont les sommets et les arêtes sont connus. Il faut pouvoir compter le degré de chaque sommet, fixer un ordre total en cas d’égalité et tester quels sommets sont adjacents. Le graphe peut être connexe ou comporter plusieurs composantes.
Une boucle, c’est-à-dire une arête reliant un sommet à lui-même, rend impossible une coloration propre de ce sommet : aucune couleur ne peut être différente d’elle-même. Il faut alors signaler l’absence de solution dans ce modèle, plutôt qu’exécuter la procédure comme si le graphe était simple. Des arêtes multiples entre deux mêmes sommets ne changent pas la contrainte de couleur ; elles peuvent être ramenées à une seule arête pour cette tâche.
Un exemple, pas à pas
Considérons les sommets A, B, C, D, E et F. Les dix arêtes sont AB, AC, AD, AE, BC, BD, BF, CE, DF et EF. Les degrés valent 4 pour A et B, puis 3 pour C, D, E et F. En départageant les égalités par ordre alphabétique, la liste est A, B, C, D, E, F.
1. A reçoit la couleur 1.
2. B, voisin de A, reçoit la couleur 2.
3. C, voisin de A et de B, reçoit la couleur 3.
4. D est voisin de A et de B, mais pas de C : il reçoit la couleur 3.
5. E est voisin de A et de C, mais pas de B : il reçoit la couleur 2.
6. F est voisin de B, D et E : il reçoit la couleur 1.
2. B, voisin de A, reçoit la couleur 2.
3. C, voisin de A et de B, reçoit la couleur 3.
4. D est voisin de A et de B, mais pas de C : il reçoit la couleur 3.
5. E est voisin de A et de C, mais pas de B : il reçoit la couleur 2.
6. F est voisin de B, D et E : il reçoit la couleur 1.
La coloration obtenue est {A, F} en couleur 1, {B, E} en couleur 2 et {C, D} en couleur 3. Le contrôle consiste à relire les dix arêtes : aucune n’a deux extrémités de même couleur. De plus, A, B et C forment un triangle ; trois couleurs sont donc nécessaires dans cet exemple.
En pratique
Pour construire rapidement un emploi du temps, on représente les activités incompatibles par des sommets adjacents. La couleur choisie devient un créneau. Welsh et Powell convient lorsqu’une solution valide doit être obtenue vite ; une méthode exacte est préférable si le nombre minimal de créneaux est impératif.
Pour affecter des fréquences à des émetteurs qui se brouillent mutuellement, une couleur représente une fréquence. La méthode fournit une première affectation sans conflit. Si les fréquences sont rares ou coûteuses, cette première solution doit ensuite être optimisée ou comparée à une recherche exacte.
Dans un programme, il est utile de fixer la règle de départage des degrés égaux. Deux exécutions deviennent alors reproductibles, et le nombre de couleurs obtenu peut être comparé à celui d’autres ordres gloutons.
À ne pas confondre
Coloration propre et coloration minimale. Une coloration propre interdit seulement une même couleur aux extrémités de chaque arête. Elle est minimale si aucune coloration propre utilisant moins de couleurs n’existe. Welsh et Powell garantit la première propriété, pas la seconde.
Degré maximal et nombre chromatique. Le degré maximal compte les voisins du sommet le plus connecté ; le nombre chromatique compte le minimum de couleurs nécessaire au graphe entier. Dans une étoile ayant au moins deux arêtes, le centre a un degré élevé, mais deux couleurs suffisent.
Coloration des sommets et coloration des arêtes. Ici, les couleurs portent sur les sommets et deux sommets adjacents doivent différer. Dans une coloration des arêtes, ce sont deux arêtes partageant un sommet qui doivent différer ; la procédure et le problème ne sont donc pas les mêmes.
Limites et pièges
Optimalité non garantie. Une coloration correcte utilisant k couleurs prouve seulement que le nombre chromatique est au plus k. Pour certifier le minimum, il faut aussi une borne inférieure égale à k, comme le triangle A–B–C dans l’exemple, ou employer une méthode exacte.
Ex æquo sensibles. Lorsque plusieurs sommets ont le même degré, leur ordre peut changer la coloration et parfois le nombre final de couleurs. Il faut annoncer la règle de départage et, si l’enjeu le justifie, essayer plusieurs ordres.
Composantes séparées. Dans un graphe non connexe, les mêmes couleurs peuvent être réutilisées d’une composante à l’autre. Additionner les nombres de couleurs des composantes surestime donc le besoin ; on retient le maximum obtenu sur une composante.
Boucles. Une boucle interdit toute coloration propre, quel que soit l’ordre. Le symptôme est un sommet déclaré adjacent à lui-même ; il faut corriger le modèle ou conclure que cette instance n’admet pas de coloration propre.
Pour aller plus loin
algorithme de coloration replace Welsh et Powell parmi les procédures qui construisent une coloration et permet d’en comparer les stratégies.
nombre chromatique d'un graphe précise le minimum que l’heuristique cherche à approcher sans le certifier en général.
algorithme donne le cadre général d’une suite finie d’instructions, utile pour distinguer procédure, résultat et garantie.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres