INFO TEST 9 décembre 2013

                       INFO  TEST                   TES    Spé Math                       9  décembre  2013

    EXERCICE 1

     On s'intéresse aux principales rues permettant de relier différents

      lieux de la ville où habite Pauline:

         Mairie ( M )             Centre commercial ( C )

         Bibliothèque ( B )            Piscine ( P )        Lycée ( L )

    Le tableau ci-dessous donne les rues existant entre les lieux.

   B  C  L  M  P
B     X    X  X
C  X    X  X  
L    X    X  
M  X  X  X    X
P  X      X  

    1.a. Dessiner un graphe représentant cette situation.

       REPONSE:

         On peut considérer:

           Conclusion:

    Cld14

       b. Est-il possible de trouver un trajet passant une et une seule fois par toutes les rues de ce plan?

          Justifier la réponse. Si, oui, proposer un tel trajet

           REPONSE:

          Tableau des degrés des sommets:

Sommets    B      C      L     M      P     
Degrés   3   3  2   4   2  14   

     • Le graphe est connexe ( simple ) car deux sommets quelconques sont reliés par au moins un chemin.

     • Le nombre de sommets de degré impair est 0 ou 2 ici 2.

          Donc, d'après le Th. d'euler il y a au moins une chaîne eulérienne entre les sommets B et C

           qui sont de degré impairs.

                 Conclusion: OUI . Il y a un trajet passant une et une seule fois par toutes les rues de ce plan.

      On peut proposer le trajet :

                                         BPMLCMBC

        c. Un distributeur de publicité veut passer dans toutes ces rues une fois et une seule.

                   Peut-il partir d'un lieu et revenir à son point de départ? Justifier la réponse.

           REPONSE:

         NON.

          Comme le nombre de sommets de degré impair n'est pas 0 il n'y a pas de cycle eulérien.

           Le distributeur ne peut donc revenir à son lieu de départ.

       2. Devant chaque lieu, il existe un rond-point que le service des jardins de la ville fleurit.

           Ce service municipal aimerait que les deux parterres des ronds-points

            reliés par une rue ne soient pas fleuris par les mêmes fleurs.

             Combien de types différents de fleurs doit-il prévoir?

              Justifier avec soin la réponse.

            REPONSE:

            On peut remplacer le type de fleur par une couleur.

           cela revient à trouver le nombre chromatique δ.

            L'ordre du plus grand sous graphe complet est m = 3 

            BPM par exemple est un sous graphe complet d'ordre 3.

            Le plus haut degré est   Δ = 4 .

             Donc  :         3 ≤  δ  ≤ 5   

Sommets     M       B     C      L     P       
Degrés     4   3    3   2   2    14 
Couleurs   Rouge   Vert  Bleu  Vert  Bleu  

Cld145

         Conclusion:

                      Trois types de fleurs sont nécessaires.

     3. Pauline habite en D.

      Le graphe ci-contre présente le sens de circulation dans chacune des  rues et le temps

      de parcours entre les différents lieux. 

       Par un algorithme, proposer un trajet le plus court possible permettant à Pauline

      de se rendre en voiture de son domicile D à la piscine P.

        REPONSE:

               Bn11

                Tableau de Moore:

    Linka145

           Linka3

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

             EXERCICE 2:

     Une grande ville a mis en place une location de vélos avec sept stations A, B, C , D, E , F , G, 

     reliées entre elles par des pistes cyclables. Les temps de parcours sont donnés sur le graphe ci-dessous.

                   Kalinka012

         1. Romain décide de visiter la ville en empruntant que des pistes cyclables.

      a. A-t-il la possibilité d'éffectuer un parcours empruntant une fois et une seule

            toutes les pistes cyclables? Justifier la réponse.

         REPONSE:

            Tableau des degrés des sommets.

Sommets   A   B   C   D   E   F   G 
 Degrés  3  4  4  3  4  4  2

           • Le graphe est connexe( simple) car deux sommets quelconques sont reliés

              par au moins un chemin.

            • Le nombre de sommets de degré impair est 2.

            ce sont les sommets A et D.

         Donc d'après le Th. d'euler il existe une chaîne eulérienne au moins qui relie les sommets A et D.

           Conclusion. OUI. Romain peut faire un parcours en empruntant une et

                une seule fois les pistes cyclables.

     b. A la fin du parcours précédent, pourra-t-il rendre son vélo à la station où i l'a pris?

            Justifier la réponse.

               REPONSE: NON

             En effet le nombre de sommets de degré impair n'est pas 0. Il n'y a donc pas de cycle eulérien.

    2. Il a emprunté un vélo à la station F et l'a rendu à la station E en passant par deux stations.

          Il veut connaître le nombre de trajets différents qu'il peut avoir suivi.

            soit M la matrice adjacente, en prenant l'ordre alphabétique .

         Romain doit-il  calculer  M2, M3  ou  M4   pour connaîte le nombre de trajets?

        A l'intersection de quelle ligne et de quelle colonne doit-il lire le résultat?

    REPONSE:

                La matrice M est :

                     Mt2145

           Romain a utilisé un chemin de longueur 3 car il y a 4 stations sur son trajet 

           dont celle de départ F et celle d'arrivée E. Il y a deux autres stations.

           Il faut donc dans la matrice M considérer le terme de rang ( 6 ; 5 ).

          On a :

                   Covana14

                           Conclusion : Il y a 11 trajets possibles pour Romain.

    3. Depuis son hôtel en A, Romain envisage de rejoindre en vélo le plus rapidement

         possible la gare située en G.

           A l'aide d'un algorithme , déterminer un tel parcours et le temps nécessaire

           pour l'effectuer.

           REPONSE:

             Tableau de Moore:

       Digic16

               Ainsi :

             Conclusion:

      Nvb14

         Tord17

            4. La ville a peint les stations en couleurs de sorte que deux stations reliées par une piste

               cyclabe ne soient pas de la même couleur.

              Proposer une coloration des stations avec le minimum de couleurs.

               REPONSE:

                 Tableau :

 Sommets    B     C     E     F     A     D     G  
Degrés décroissants  4 4 4 4 3 3 2
Couleurs   Rouge   Orange  Vert  Rouge  Vert Orange  Vert

             •  L'ordre du plus grand sous graphe complet est m = 3

               comme par exemple  ABC.

              • Le degré le plus élevé est Δ = 4

         Donc le nombre chromatique est δ  est tel que   3 ≤   δ ≤   5 

        On peut ici considérer trois couleurs.

       Col16