INFO DS n°4 TES spé maths 27/1/2014

                           INFO      DS n°4             27 janvier 2014            TES  spé

            EXERCICE     

              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

    1. a. Donnons l'ordre du graphe.

            Il y a 9 sommets.

            Donc:

           Conclusion : Le graphe est d'ordre 9 .

         b. Regardons si le graphe est connexe.

             Entre deux sommets quelconques il y a toujours au moins un chemin.

             Donc:

             Conclusion. Le graphe est bien connexe.

         c. Regardons si le graphe est complet.

              Il n'y a pas d'arête entre R et P.

               Donc:

        Conclusion : Le graphe n'est pas cmplet.

  2. Regardons si un touriste peut, à partir de lyon,

            visiter toutes les villes en utilisant 

            une seule fois chaque autoroute.

             Cela revient à voir s'il y a un chemin eulérien à partir de L.

      Le graphe est non orienté( simple ) et connexe.

       D'après le Th d'Euler, un tel chemin eulérien n'existe que  quand 

      le graphe a un nombre de sommets de degré impair qui est 0 ou 2.

       Or ici il quatre sommets de degré impair.

          En effet:

      Tableau des degrés des sommets.

Sommets  B C L M P R T V Z
degré 3 3 2 2 4 3 4 3 2

             Donc:

              Il n'y a pas de chemin eulérien.

            Conclusion: Non. Le touriste ne peut pas envisager cela.

    3. a Détaillons le calcul pour le coefficient de N4 situé à la 3ième ligne et 9 ième colonne.

                  Deumat

            On utilise N × N3   mais  on n'utilise pas la calculatrice.

           On recherche à la main le terme de N4 demandé.

            Le terme est :   

             1 × 3 + 1 ×1 = 4

           En effet:  La ligne 3 est choisie dans N

                La colonne 9 est choisie dans N3

             0  1  0  0  0  0  0  1  0    ×  Colonne    =   1 × 3 + 1 ×1 = 4 

               Ligne 3 de N            colonne 9 de N3                                                         

  b. Interprétons ce 4.

             Comme c'est le terme de N4   de rang  ( 3 ;  9) cela veut dire

          qu'il y a  4 chemins de longueur 4 qui vont de L à Z.

   4.

     Graphe  

       Grlib2

              a. Donnons le chemin le moins cher pour aller de Lyon à Biarritz.

                        Tableau de Moore-Dijstra

Liban 1

             Ainsi :

        Z ← B(38,1) ← R( 33,7) ←C( 22,2)←L( 10,7) ←L 

           Conclusion:

              Le chemin le moins coûteux est: 

                LCRBZ   

   b. Le coût est de de 38,10 €

          Chcour

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