Baccalauréat 2013 MATHÉMATIQUES Série ES

sujet : Liban 2013

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

Le graphe ci-dessous représente les autoroutes entre les principales villes du Sud de la France :
Bordeaux (B), Clermont-Ferrand (C), Lyon (L), Marseille (M), Montpellier (P), Brive (R), Toulouse (T), Valence (V) et Biarritz (Z).

Graphe pondéré : L'illustration svg n'est pas visible par votre navigateur.
  1. Pour cette question, on justifiera chaque réponse.

    1. Déterminer l'ordre du graphe.

      Il y a 9 sommets donc l'ordre du graphe est 9.


    2. Déterminer si le graphe est connexe.

      La chaîne B-R-C-L-V-M-P-T-Z contient tous les sommets du graphe. Donc le graphe est connexe.


    3. Déterminer si le graphe est complet.

      Il n'y a pas d'arête ente les sommets B et C donc le graphe n'est pas complet.


  2. Un touriste atterrit à l'aéroport de Lyon et loue une voiture.
    Déterminer, en justifiant, s'il pourra visiter toutes les villes en empruntant une et une seule fois chaque autoroute.

    Il y a 4 sommets de degré impair, les sommets B, R, C et V. Donc il n'existe pas de chaîne eulérienne.

    Ce n'est pas possible de visiter toutes les villes en empruntant une et une seule fois chaque autoroute.


  3. Il décide finalement d'aller seulement de Lyon à Biarritz.
    On note N la matrice associée au graphe, les sommets étant rangés dans l'ordre alphabétique : B, C, L, M, P, R, T, V, Z.
    Voici les matrices N et N3 : N=000001101001011000 010000010000010010010100110110000100100011001 001110000100000100etN3=421136615205286113150210350122252141381521871660212832613188416115473121530112612

    1. En détaillant le calcul, déterminer le coefficient de la troisième ligne et dernière colonne de la matrice N4.

      N4=N3×N.
      Le coefficient a3,9 de la troisième ligne et dernière colonne de la matrice N4 est égal au produit de la matrice ligne de la troisième ligne de la matrice N3 par la matrice colonne de la dernière colonne de la matrice N :150210350×100000100=1×1+3×1=4

      Le coefficient de la troisième ligne et dernière colonne de la matrice N4 est égal à 4.


    2. En donner une interprétation.

      Le coefficient a3,9 de la matrice N4 donne le nombre de chaînes de longueur 4 reliant les sommets B et Z :

      Il y 4 possibilités d'aller de Lyon à à Biarritz en quatre étapes.


  4. Sur les arêtes du graphe sont maintenant indiqués les prix des péages en euro.

    Algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.
    1. À l'aide de l'algorithme de Dijkstra, déterminer le chemin que doit prendre le touriste pour minimiser le coût des péages de Lyon à Biarritz.

      LBCMPRTVZSommet sélectionné
      0

      L (0)

      10,7 (L)7,1 (L)

      V (7,1)

      10,7 (L) 22,8 (V)23,3 (V)

      C (10,7)

      22,8 (V)19,3 (C) 22,2 (C)

      P (19,3)

      22,8 (V)22,2 (C) 38,9 (P)

      R (22,2)

      33,7 (R)22,8 (V)36,8 (R)

      M (22,8)

      33,7 (R)36,8 (R)

      B (33,7)

      36,8 (R) 38,1 (B)

      T (36,8)

      38,1 (B)

      Z (38,1)


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

      Le chemin qui minimise le coût des péages de Lyon à Biarritz est Lyon(L) - Clermont-Ferrand (C) - Brive (R) - Bordeaux (B)- Biarritz (Z).


    2. Déterminer le coût, en euro, de ce trajet.

      Le coût des péages de ce trajet est de 38,1 €.



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.