INFO BAC BLANC 13 février 2015

            BAC BLANC  TES  spé 13 février 2015

          EXERCICE 

              Le graphe ci-dessous indique, sans respecter l'échelle, les parcours

               possibles entre les sept bâtiments d'une entreprise importante.

               Sur chaque arête, les temps de parcours sont indépendants

              du sens de parcours.

    Xqsd4789 1

           Les durées sont en minutes.

     1. En justifiant la réponse, montrer qu'il est possible que l'agent de sécurité

          passe une fois et une seule par tous les chemins de cette usine.

          Donner un exemple de trajet.

         Cela revient à justifier l'existence d'une cha^ne eulérienne.

      Tableau des degrés des sommets.

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

          Le graphe est simple.

       • Le graphe est connexe car deux sommets quelconques

        sont reliés par au moins un chemin.

      • Il admet deux sommets de degrés impairs.

              Conclusion:

          D'après le th d'Euler il admet une chaîne eulérienne qui relie E et G.

               On peut citer :GABCDEFGBECGE

    2. L'agent de sécurité peut-il revenir à son point de départ après avoir

            parcouru une fois et une seule tous les chemins? Justifier la réponse.

            Il n'y a pas de cycle eulérien car  le nombre de sommets de degré

          impair n'est pas zéro.

             Donc :

          Conclusion: C'est impossible

     3.Tous les matins l'agent de sécurité part du bâtiment A et se rend au bâtiment D.

       En utilisant un algorithme que l'on expliquera, déterminer le chemin qu'il doit suivre

       pour que son temps de parcours soit le plus court possible, et donner ce temps de parcours.

           Faisons un tableau de Moore.

    Zae14

    Conclusion:

    Le trajet le plus court est AGCED de 28 mn.

                 Xqsd47891

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