Baccalauréat 2018 MATHÉMATIQUES Série ES-L

sujet : Nouvelle Calédonie novembre 2018

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

Naïma fait partie d'une école de musique. En vue du spectacle de fin d'année, elle souhaite déposer à vélo des affiches publicitaires sur les panneaux de sa ville. Les pistes cyclables reliant ces panneaux sont représentées sur le graphe 𝒢 ci-dessous.
Le sommet E désigne son école de musique, le sommet S la salle de spectacle et les sommets A, B, C, et D les panneaux d'affichage.

Graphe G : L'illustration svg n'est pas visible par votre navigateur.
  1. Déterminer, en justifiant la réponse, si le graphe 𝒢 est :

    1. complet ;

      Les sommets A et B ne sont pas ajacents donc le graphe n'est pas complet.


    2. connexe.

      La chaîne fermée A - E - B - C - D - S - A contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne les reliant donc le graphe est connexe.


  2. Naïma pourra-t-elle déposer ses affiches sur tous les panneaux en allant de son école de musique à la salle de spectacle et en empruntant une et une seule fois chaque piste cyclable ?
    Justifier la réponse. Si un tel trajet existe, en citer un.

    Les degrés des sommets sont :

    Sommets ABCDES
    Degré242433
    Graphe G : L'illustration svg n'est pas visible par votre navigateur.

    Le graphe est connexe et il n'y a que deux sommets E et S de degré impair, il existe donc des chaînes eulérienne d'extrémités E et S.
    Naïma pourra déposer ses affiches sur tous les panneaux en allant de son école de musique à la salle de spectacle et en empruntant une et une seule fois chaque piste cyclable.
    Par exemple le trajet E - B - S - D - B - C - D - E - A - S.


  3. Donner la matrice d'adjacence M liée à ce graphe dans laquelle les sommets seront classés dans l'ordre suivant : E, A, B, C, D, S.

    La matrice d'adjacence du graphe est M=(011010100001100111001010101101011010)


  4. On donne la matrice incomplète M2 : M2=(3011302202012413101212123141301213).

    1. Déterminer les coefficients manquants de la matrice M2, en détaillant les calculs.

      Le coefficient a4,1 de la quatrième ligne et première colonne de la matrice M2 est égal au produit de la quatrième ligne de la matrice M par la première colonne de la matrice M :a4,1=(001010)×(011010)=(0×0+0×1+1×1+0×0+1×1+0×0)=(2)

      Le graphe 𝒢 n'est pas orienté par conséquent, la matrice M2 est symétrique par rapport à la diagonale. Il s'ensuit que le coefficient a1,4 de la première ligne et quatrième colonne de la matrice M2 est égal au coefficient a4,1.

      Ainsi, M2=(301213022020124131201212123141301213).


    2. Combien existe-t-il de chemins permettant de se rendre de l'école de musique à la salle de spectacle en empruntant exactement deux pistes cyclables ?

      Le coefficient a1,6 de la première ligne et sixième colonne de la matrice M2 est égal au nombre de chemins permettant de se rendre de l'école de musique E à la salle de spectacle S en empruntant exactement deux pistes cyclables.

      a1,6=3 donc il y a trois trajets permettant de se rendre de l'école de musique à la salle de spectacle en empruntant exactement deux pistes cyclables.


  5. Lorsqu'elle a déposé ses affiches, Naïma a relevé le temps de trajet entre chaque panneau d'affichage. Le graphe ci-dessous indique ces durées, exprimées en minutes.
    Indiquer, à l'aide d'un algorithme, le chemin permettant à Naïma de se rendre le plus rapidement possible de son école de musique à la salle de spectacle le soir de la représentation.
    Donner la durée de ce parcours.

    À l'aide de l'algorithme de Dijkstra, déterminons le trajet qui minimise le temps de parcours pour se rendre de l'école de musique à la salle de spectacle.

    Graphe pondéré G : L'illustration svg n'est pas visible par votre navigateur.
    EABCDSSommet sélectionné
    0

    E (0)

    9 (E)4 (E)7 (E)

    B (4)

    9 (E)6 (B)7 (E)
    5 (B)
    12 (B)

    D (5)

    9 (E)6 (B)12 (B)
    8 (D)

    C (6)

    9 (E)8 (D)

    S (8)


    Le sommet S étant marqué, pour lire la chaîne de poids minimal, on part de S et on "remonte" la chaîne en suivant les prédécesseurs. SDBE.

    Le trajet permettant à Naïma de se rendre le plus rapidement possible de son école de musique à la salle de spectacle est E - B - D - S pour une durée de 8 minutes.



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.