TES DS n°4 spé maths 27 janv. 2014

                                      INFO      DS n°4             27 janvier 2014            TES  spé

            EXERCICE        bac ES  

               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 ( B ) , Toulouse ( T ) , Valence ( V ) et Biarritz ( Z ).

       Grlib

            Pour cette question on justifiera chaque réponse:

    1. a. Déterminer l'ordre du graphe.

        b. Déterminer si le graphe est connexe.

        c. Déterminer si le graphe est complet.

    2. Un touriste atterrit à l'aéroport de Lyon et loue une voiture.

        Déterminer, en justifiant, s'il peut  visiter toutes les villes en emprutant

        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.       

         Deumat

       a. En détaillant le calcul, déterminer le coefficient de la troisième ligne

           et dernière colonne de la matrice N4 .

       b. En donner une interprétation.

    4.  Sur les arêtes du graphe sont maintenant indiqués les prix du péage en euros.

     Graphe  

       Grlib2

              a. A l'aide de l'algorithme de Dijstra, déterminer le chemin que doit prendre

                   le touriste pour minimiser le coût des péages de Lyon à Biarritz.                     

               b. Déterminer le coût, en euros , de ce trajet.         

----------------------------------------------------------------