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

sujet : liban

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

  1. Dans un parc, il y a cinq bancs reliés entre eux par des allées.

    On modélise les bancs par les sommets A, B, C, D, E et les allées par les arêtes du graphe G ci-dessous :

    Graphe G : L'illustration svg n'est pas visible par votre navigateur.
    1. On désire peindre les bancs de façon que deux bancs reliés par une allée soient toujours de couleurs différentes.
      Donner un encadrement du nombre minimal de couleurs nécessaires et justifier.
      Déterminer ce nombre.

      Déterminer le nombre chromatique du graphe G.

    2. Est-il possible de parcourir toutes les allées de ce parc sans passer deux fois par la même allée ?

      Parcourir toutes les allées de ce parc sans passer deux fois par la même allée signifie que le graphe G comporte une chaîne eulérienne.

  2. Une exposition est organisée dans le parc. La fréquentation devenant trop importante, on décide d'instaurer un plan de circulation : certaines allées deviennent à sens unique, d'autres restent à double sens. Par exemple la circulation dans l'allée située entre les bancs B et C pourra se faire de B vers C et de C vers B, alors que la circulation dans l'allée située entre les bancs A et B ne pourra se faire que de A vers B. Le graphe ci-dessous modélise cette nouvelle situation :

    Graphe G' : L'illustration svg n'est pas visible par votre navigateur.
    1. Donner la matrice M associée au graphe G' (On ordonnera les sommets par ordre alphabétique).

    2. On donne M5=(1696104571154661151510610655142)
      Combien y a-t-il de chemins de longueur 5 permettant de se rendre du sommet D au sommet B ? Les donner tous.

      Utiliser la propriété donnant le nombre de chaînes de longueur n reliant deux sommets d'un graphe :

      Le terme aij situé à l'intersection de la ligne i et de la colonne j de la matrice Mn, donne le nombre de chaînes de longueur n reliant le sommet Xi et le sommet Xj du graphe.

    3. Montrer qu'il existe un seul cycle de longueur 5 passant par le sommet A.
      Quel est ce cycle ?
      En est-il de même pour le sommet B ?

      Un cycle est une chaîne fermée dont toutes les arêtes sont distinctes.
      Un cycle passant par le sommet A est identique à un cycle partant de A.


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.