Le nombre chromatique est le nombre minimal de couleurs qu'on doit utiliser pour colorer tous les sommets d'un graphe en s'assurant que deux sommets adjacents ne soient pas de la même couleur.
On utilise les concepts de graphe coloré et de nombre chromatique pour résoudre les problèmes de planification pour lesquels on doit tenir compte de certaines incompatibilités.
Les situations suivantes sont des exemples de cas où il peut être utile de trouver le nombre chromatique : la planification d'horaire, le regroupement d'espèces d'animaux ou de plantes, la coloration des États sur une carte du monde, etc.
Étapes de résolution d'un problème avec l'utilisation du nombre chromatique :
-
Tracer le graphe représentant la situation où les sommets sont les éléments à considérer et où les arêtes illustrent les incompatibilités entre les éléments.
-
Dresser la liste des sommets du graphe en ordre décroissant de degré (l'ordre n'a pas d'importance pour deux sommets ayant le même degré).
-
Colorier le premier sommet de la liste (celui dont le degré est le plus élevé) d'une couleur de son choix.
-
En suivant la liste, attribuer la même couleur aux autres sommets qui ne sont pas reliés au premier sommet ni entre eux.
-
Répéter les étapes 3 et 4 avec une nouvelle couleur chaque fois jusqu'à ce que les sommets soient tous colorés.
-
Calculer le nombre de couleurs utilisées pour donner le nombre chromatique et répondre à la question.
Les organisateurs d’un festival de musique doivent planifier l’horaire des représentations des différents groupes à l’affiche, mais il ont plusieurs contraintes à respecter.
-
Le groupe Les Amateurs ne peut pas jouer en même temps que Les Bons à rien parce que les 2 groupes ont le même batteur.
-
Le chanteur Calvin Harry ne peut pas faire sa prestation en même temps que Dany Lavoto puisque les deux utilisent le même équipement de scène.
-
Calvin Harry et Janis Jackson ne veulent pas se produire sur scène en même temps puisqu’ils partagent sensiblement le même public.
-
Les artistes suivants : Calvin Harry, Janis Jackson, Éléonore Rugby et Dany Lavoto refusent de faire leur spectacle en même temps que Les Valeureux Pingouins parce qu’ils jugent que ceux-ci sont trop populaires et qu’il n’y aurait donc plus assez de spectateurs pour leur propre spectacle.
-
Finalement, Janis Jackson ne veut pas jouer en même temps que Les Bons à rien parce qu’elle veut absolument assister à leur spectacle.
À la lumière de toutes ces contraintes, quel est le nombre minimal de scènes et de soirs qui seront nécessaires pour présenter tous ces spectacles lors de ce festival?
-
Tracer le graphe représentant la situation où les sommets sont les éléments à considérer et où les arêtes illustrent les incompatibilités entre les éléments
|
Légende |
|---|
|
A : Les Amateurs |
-
Dresser la liste des sommets du graphe en ordre décroissant de degré
VP (4), CH (3), JJ (3), DL (2), B (2), A (1), ER (1)
-
Colorier le premier sommet de la liste d'une couleur de son choix
Le sommet VP est le sommet ayant le plus grand degré, soit 4. On le colore en bleu.
-
En suivant la liste, attribuer la même couleur aux autres sommets qui ne sont pas reliés au premier sommet ni entre eux
Les seuls sommets qui ne sont pas reliés à VP et qui sont reliés entre eux sont A et B. On colore alors B puisqu'il est le prochain sur la liste.
-
Répéter les étapes 3 et 4 avec une nouvelle couleur chaque fois jusqu'à ce que les sommets soient tous colorés
Les prochains sommets de plus haut degré sont CH et JJ. On choisit CH qu'on colore en vert. On peut également attribuer la couleur verte aux sommets A et ER, qui ne sont pas reliés entre eux ni à CH.
Finalement, les 2 derniers sommets qui ne sont pas encore colorés ne sont pas reliés entre eux. On peut donc leur attribuer la même couleur sans problème. On choisit arbitrairement le rouge.
Voici donc le graphe représentant la situation :
|
Légende |
|---|
|
A : Les Amateurs |
-
Calculer le nombre de couleurs utilisées pour donner le nombre chromatique et répondre à la question
Nous avons utilisé 3 couleurs différentes. Le nombre chromatique de ce graphe est donc 3. Mais qu'est-ce que cela signifie dans la mise en situation?
Les groupes qui ont été colorés d'une même couleur vont pouvoir présenter leur spectacle lors du même soir. Comme le nombre chromatique est 3, cela signifie qu'il faudra 3 soirs pour présenter tous les spectacles. Comme il y a 3 sommets verts (et seulement 2 en bleu et 2 en rouge), cela signifie qu'il faudra 3 scènes pour présenter simultanément les spectacles des Amateurs, de Calvin Harry et d'Éléonore Rugby.
Remarque : À l'étape 5, si on avait choisi le sommet JJ au lieu du sommet CH, on aurait obtenu le même nombre de soirs, mais un nombre différent de scènes.