Matières
Niveaux
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?