INFO EX BAC LIBAN 2014 ES spé

            INFO  EXERCICE DE BAC ES  spé maths.     mai 2014    Liban

          On a schématisé ci-dessous le plan d'une MJC ( Maison de la jeunesse et de la culture )

        par un graphe dont les sommets sont les salles

          et les arêtes  sont les passages( portes, couloirs ou escaliers) entre les salles.

          On appelle  H le hall d'entrée et B le bureau du directeur.

        Graphe es liban

        En fin de journée un agent de service fait le tour de la MJC pour récupérer dans chaque salle 

       ( bureau du directeur et hall inclus ) les objets oubliés par les enfants.

     QUESTION 1.

         Préciser si le graphe est connexe en justifiant la réponse.

           OUI.

         En effet , deux sommets quelconques sont reliés par au moins un chemin.

     QUESTION 2.

        Déterminer, en justifiant, si l'agent de service peut passer par toutes les salles

        en utilisant une fois une seule chaque passage.

      OUI.

         Il y a en effet ici un graphe non orienté connexe ( simple ) qui

        possède exactement deux sommets de degrés impairs ( 3 ).

         Ces deux sommets sont F et D.

          Il existe donc au moins une  chaîne eulérienne reliant les sommets F et D.

      QUESTION 3.

         On range les sommets par ordre alphabétique.

         donner la matrice d'adjacence M associée au graphe.

           Matr m

    QUESTION 4.

         On donne:  

                              M4

         En déduire le nombre de chemins de longueur 4 entre les sommets B et H.

          6 se trouve à l'intersection de la seconde ligne et de la  7 ième colonne de M4 .

        Donc:

          Conclusion:   il y a 6 chemins de longueur 4 qui relient B et H

     QUESTION 5.

        On a indiqué sur le graphe ci-dessous le temps en minutes mis pour passer entre les différentes salles

         en ouvrant et fermant les portes à clé.

         Déterminer à l'aide d'un algorithme le temps minimal pour aller de B à H.

            Graphe es liban 2014

                Faisons le tableau de Moore-Dijkstra.

      Liban 2014es 1

          H ←  F( 5 )  ← E( 4 )  ←  C( 3 )  ← B(2 )  ← B

            Conclusion : Le chemin le plus court est :

            BCEFH      

           Ce n'était pas le seul chemin possible car on a fait un choix.

         Plus court graphe es liban 2014

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