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.
Les sommets du graphe sont les 10 variétés de fleurs, deux variétés incompatibles sont reliées par une arête.
Trouver un sous-graphe complet d'ordre 4 et le dessiner.
V2, V4, V5, V8 est un un sous-graphe complet d'ordre 4.
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 ?
Le graphe admet un sous graphe complet d'ordre 4, son nombre chromatique est donc supérieur ou égal à 4.
Le jardinier devra donc décorer au moins 4 parterres.
Classer les sommets de G par ordre de degré décroissant.
Sommets | V4 | V2 | V3 | V5 | V1 | V6 | V8 | V7 | V9 | V10 |
Degré | 5 | 4 | 4 | 4 | 3 | 3 | 3 | 2 | 2 | 2 |
En déduire un encadrement de C, nombre chromatique de G.
Le plus grand des degrés des sommets est 5 alors, le nombre chromatique .
Donc .
Procéder à la coloration du graphe G.
On effectue un coloriage à l'aide de l'algorithme "glouton"
couleur 1 les sommets : V4, V1 et V7
couleur 2 les sommets : V2, V6 et V9
couleur 3 les sommets : V3, V5 et V10
couleur 4 le sommet : V8
Que peut-on en déduire pour le nombre C ? Justifier avec soin.
et quatre couleurs ont suffit pour colorer le graphe G. Donc .
Proposer un ensemble de parterres avec une répartition adaptée des variétés de fleurs.
La coloration précédente permet d'obtenir quatre parterres avec une répartition adaptée des variétés de fleurs :
Parterre 1 les variétés : V4, V1 et V7. Parterre 2 les variétés : V2, V6 et V9. Parterre 3 les variétés : V3, V5 et V10. Parterre 4 la variété : V8.
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.