ArithmétiqueObjet mathématique · Glossaire
coloration d'un graphe
Dans un graphe simple, sans boucle ni arêtes multiples, une coloration attribue une couleur à chaque sommet de sorte que deux sommets reliés par une arête aient toujours des couleurs différentes. Le nombre chromatique est le plus petit nombre de couleurs permettant une telle coloration ; il mesure combien de catégories sont indispensables pour satisfaire toutes les contraintes d’adjacence.
Sommaire
Ce que vous allez apprendre
- Reconnaître une coloration valide en contrôlant chaque arête.
- Déterminer que le cycle à cinq sommets a pour nombre chromatique 3.
- Interpréter correctement les théorèmes des quatre couleurs et de Brooks.
En clair
Imaginez cinq points disposés en cercle, chaque point étant relié à ses deux voisins. On veut étiqueter ces points sans donner la même étiquette à deux voisins.
Deux couleurs alternent bien sur les quatre premiers points, mais le cinquième touche à la fois le premier et le quatrième. Une troisième couleur résout le conflit. La coloration d'un graphe formalise ce jeu de contraintes, et le nombre chromatique indique le minimum de couleurs nécessaire.
Définition
Une coloration des sommets d'un graphe simple attribue une couleur, ou plus généralement une étiquette, à chacun de ses sommets. Elle est valide lorsque les extrémités de chaque arête portent des couleurs différentes. Une k-coloration valide utilise au plus k couleurs.
Pour un graphe noté G, le nombre chromatique, noté χ(G), est le plus petit nombre entier de couleurs qui autorise une coloration valide. Autrement dit : . Le choix des noms ou de l'apparence des couleurs ne change pas cette valeur ; seules comptent les égalités et différences d'étiquettes entre sommets adjacents.
Dans le cadre de la source, le graphe est simple : il ne possède ni boucle ni arêtes multiples. Tout graphe planaire possède une coloration valide avec au plus quatre couleurs. Pour un graphe connexe qui n'est ni complet ni un cycle impair, le théorème de Brooks borne χ(G) par le degré maximal, c'est-à-dire le plus grand nombre d'arêtes incidentes à un même sommet.
De quoi c'est fait
Quatre éléments structurent le problème. Les sommets sont les objets à colorer. Les arêtes indiquent quelles paires de sommets sont adjacentes et doivent donc recevoir des couleurs distinctes. La palette fixe les étiquettes disponibles. Enfin, la fonction de coloration associe une étiquette de la palette à chaque sommet.
Les arêtes imposent les contraintes à la fonction de coloration ; la taille de la palette détermine si ces contraintes peuvent être toutes satisfaites. Les sommets et les arêtes définissent le graphe, tandis que leur position sur la page, la forme des traits et les teintes choisies ne le définissent pas. Ces données suffisent à vérifier une coloration et à rechercher le nombre chromatique.
Un exemple, pas à pas
On considère cinq sommets A, B, C, D et E, reliés par les cinq arêtes AB, BC, CD, DE et EA. Chaque sommet a donc exactement deux voisins. On cherche le nombre chromatique de ce cycle à cinq sommets.
1. Avec deux couleurs, attribuons rouge à A. Les contraintes imposent alors successivement jaune à B, rouge à C, jaune à D et rouge à E.
2. Cette tentative échoue : E et A sont adjacents par l'arête EA, mais tous deux sont rouges. L'alternance avec deux couleurs ne peut donc pas fermer ce cycle impair.
3. Conservons A et C en rouge, B et D en jaune, puis attribuons noir à E. Sur chacune des cinq arêtes, les couleurs des extrémités diffèrent.
La coloration à trois couleurs existe, tandis que l'étape précédente exclut toute coloration à deux couleurs. Le résultat exact est donc χ(G) = 3. Le contrôle se refait en parcourant AB, BC, CD, DE puis EA et en comparant chaque paire d'étiquettes. La figure matérialise ce contrôle arête par arête.
En pratique
Pour construire un emploi du temps fictif, on peut représenter chaque examen par un sommet et relier deux examens ayant un participant commun. Une couleur représente alors un créneau. Si l'objectif est seulement de tester un planning proposé, il suffit de contrôler les arêtes ; si l'on veut minimiser les créneaux, il faut rechercher le nombre chromatique.
Pour une carte modélisée par un graphe planaire, chaque région devient un sommet et chaque voisinage une arête. Une coloration valide sépare les régions voisines. Le théorème des quatre couleurs garantit qu'une palette de quatre couleurs suffit, sans affirmer que quatre sont toujours nécessaires.
Pour auditer une coloration, on dresse la liste des arêtes et on compare leurs deux extrémités. Cette vérification locale prouve la validité d'une proposition. Elle ne prouve sa minimalité que si l'on montre aussi qu'une palette plus petite conduit nécessairement à un conflit.
À ne pas confondre
La coloration des sommets ne doit pas être confondue avec la coloration des arêtes. Dans la première, les objets étiquetés sont les sommets et l'on compare les extrémités de chaque arête. Dans la seconde, les objets étiquetés sont les arêtes et l'on compare celles qui partagent un sommet. Sur le cycle A–B–C–D–E–A, demander la couleur de A tranche immédiatement : cette question appartient à une coloration des sommets.
Une coloration valide n'est pas le nombre chromatique. La première est une attribution particulière qui respecte les contraintes ; le second est un minimum portant sur toutes les attributions possibles. Une coloration du cycle à cinq sommets avec quatre couleurs peut être valide, mais elle ne donne pas son nombre chromatique, qui vaut 3.
Limites et pièges
Boucle ou arêtes multiples. La définition de référence porte sur les graphes simples. Une boucle relierait un sommet à lui-même et exigerait que sa couleur diffère d'elle-même, ce qui est impossible. En présence de telles données, il faut d'abord préciser le modèle de graphe utilisé.
Graphe non connexe. Le théorème de Brooks cité suppose le graphe connexe. Pour plusieurs composantes séparées, on colore chaque composante et le nombre chromatique de l'ensemble est le plus grand de leurs nombres chromatiques, car aucune arête ne relie deux composantes.
Exceptions de Brooks. La borne par le degré maximal ne s'applique pas telle quelle aux graphes complets ni aux cycles impairs. Le cycle à cinq sommets a un degré maximal égal à 2, mais son nombre chromatique vaut 3 : c'est le cas charnière visible dans l'exemple.
Au plus quatre. Le théorème des quatre couleurs garantit une 4-coloration pour tout graphe planaire ; il n'impose pas χ(G) = 4. Le cycle à cinq sommets est planaire et nécessite seulement trois couleurs. Pour connaître le minimum, il faut donc établir séparément une borne inférieure et une coloration qui l'atteint.
Pour aller plus loin
Le graphe planaire précise le cadre dans lequel toute coloration peut se limiter à quatre couleurs.
Le Graphe complet éclaire l'une des deux exceptions explicites du théorème de Brooks.
L'article Colorier les pavés du plan prolonge la réflexion vers un problème de coloration du plan.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres