Coloration d’un graphe

Merci !

Exercices
Classe(s) : Tle ES

Dans la famille Chipy, on compte six filles : Astrid, Bérangère, Charlotte, Daphné, Eva et Flavie. Elles se chamaillent très souvent, c’est notamment le cas d’Astrid et Flavie, de Bérangère et Daphné, d’Eva et Astrid, de Daphné et Astrid et de Flavie et Daphné, que les parents ne peuvent pas laisser dans la même chambre.

1. Dessiner un graphe dans lequel les sommets représentent les enfants et les arêtes les incompatibilités d’humeur entre ces enfants.

2. Pour les vacances, les parents ont réservé un appartement avec trois chambres pour les enfants. En utilisant l’algorithme de coloration, montrer qu’il est possible de répartir les enfants dans ces chambres en évitant les conflits.

3. Est-il possible de faire mieux, c’est-à-dire de réserver un appartement avec seulement deux chambres pour les enfants ? Pourquoi ?

Pour la question 3, cela revient à montrer que le nombre chromatique du graphe est 3. Voir si nécessaire le savoir-faire 4.