Un jardinier doit décorer un jardin privatif en répartissant 10 variétés de fleurs notées V1 à V10 dans différents parterres. Certaines de ces variétés ne peuvent pas être plantées ensemble pour des raisons diverses (tailles, couleurs, conditions climatiques, ...) et ces incompatibilités sont résumées dans le tableau ci-dessous (une croix indique qu'il y a incompatibilité entre deux variétés).
Fleur | V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 |
| V1 | x | x | x | |||||||
| V2 | x | x | x | x | ||||||
| V3 | x | x | x | x | ||||||
| V4 | x | x | x | x | x | |||||
| V5 | x | x | x | x | ||||||
| V6 | x | x | x | |||||||
| V7 | x | x | ||||||||
| V8 | x | x | x | |||||||
| V9 | x | x | ||||||||
| V10 | x | x |
Représenter par son graphe G la situation.
Trouver un sous-graphe complet d'ordre 4 et le dessiner.
Que peut-on en déduire pour la coloration du graphe G ?
Quel est le nombre minimum de parterres que le jardinier doit décorer ?
Classer les sommets de G par ordre de degré décroissant.
En déduire un encadrement de C, nombre chromatique de G.
Procéder à la coloration du graphe G.
Que peut-on en déduire pour le nombre C ? Justifier avec soin.
Proposer un ensemble de parterres avec une répartition adaptée des variétés de fleurs.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.