Baccalauréat session 2011 MATHÉMATIQUES Série ES

sujet : Nouvelle Calédonie novembre 2011

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

Joanne est éducatrice canin : elle donne des leçons d'éducation le samedi après-midi.

Neuf chiots sont présents : Allegro, Bronx, Chouchou, Delco, Euclide, Falbala, Galipette, Homère et Indigo.

Joanne souhaite réaliser des exercices d'apprentissage par petits groupes de deux ou trois chiens.
Falbala ne pense qu'à jouer si elle est trop proche de Bronx, Chouchou ou Euclide.
De même, Delco est très inattentif si Bronx ou Falbala sont à proximité !
Indigo ne supporte pas le caractère trop fougueux de Galipette.
Enfin le turbulent Allegro ne supporte la présence d'aucun autre chiot, sauf Euclide et Homère.

  1. Représenter cette situation à l'aide d'un graphe G dont les sommets sont les noms des chiots et relier entre eux les chiots que l'on ne peut pas mettre ensemble pour ce travail de groupe.

    Nommons respectivement A, B, C, D, E, F, G, H et I les chiots Allegro, Bronx, Chouchou, Delco, Euclide, Falbala, Galipette, Homère et Indigo. Le graphe d'ordre 9 traduisant les incompatibilités entre les chiots est :

    Graphe G : L'illustration svg n'est pas visible par votre navigateur.
  2. Le graphe G est-il connexe ? Expliquer.

    Le sommet H du graphe est isolé donc le graphe G n'est pas connexe.


  3. Déterminer un sous graphe complet d'ordre maximal du graphe G.
    Que peut-on en déduire pour le nombre chromatique du graphe G ?

    A-B-D-F est un sous graphe complet d'ordre 4 donc le nombre chromatique du graphe G est supérieur ou égal à 4.


  4. Donner la valeur du nombre chromatique du graphe G.

    Cherchons une coloration du graphe G à l'aide de l'algorithme de Welsh et Powell :

    Les sommets étant classés dans l'ordre des degrés décroissant : A, F, B, D, C, G, I, E et H, on attribue successivement la couleur 1 à A, la couleur 2 à F, la couleur 3 à B, la couleur 4 à D, la couleur 3 à C, la couleur 2 à G, la couleur 3 à I, la couleur 1 à E et enfin la couleur 1 à H.

    Soit χ le nombre chromatique du graphe nous savons d'après la question précédente que χ4. Or une coloration du graphe avec quatre couleurs est possible donc χ=4.

    Le nombre chromatique du graphe G est 4.


  5. Peut-on proposer une répartition des chiots en groupes de deux à trois chiots pouvant travailler ensemble ?

    La coloration précédente, nous donne une répartition de chiots pouvant travailler ensemble mais avec Delco isolé. Il suffit par exemple de mettre Homère avec Delco et une répartition des chiots en groupes de deux à trois chiots pouvant travailler ensemble est possible.

    Une répartition possible des chiots pouvant travailler ensemble est : groupe 1 Allegro et Euclide; groupe 2 Bronx, Chouchou et Indigo ; groupe 3 Delco et Homère ; groupe 4 Falbala et Galipette.



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.