Baccalauréat juin 2006 MATHÉMATIQUES Série ES

sujet : Antilles-Guyane

Corrigé de l'exercice 2 : candidats ayant suivi l'enseignement de spécialité

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
  1. 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.

    Graphe : L'illustration svg n'est pas visible par votre navigateur.
    1. Trouver un sous-graphe complet d'ordre 4 et le dessiner.

      V2, V4, V5, V8 est un un sous-graphe complet d'ordre 4.

      Graphe, sous graphe complet : L'illustration svg n'est pas visible par votre navigateur.
    2. 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.


    1. 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
    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 C6.

      Donc 4C6.


    1. 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

      Graphe, sous graphe complet : L'illustration svg n'est pas visible par votre navigateur.
    2. Que peut-on en déduire pour le nombre C ? Justifier avec soin.

      4C6 et quatre couleurs ont suffit pour colorer le graphe G. Donc C=4.


    3. 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.



Rechercher des exercices regoupés par thème


[ Accueil ]


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.