EX Bac ES Pondichéry 2013

                               Bac ES  2013   Pondichéry    

    EXERCICE:

                      Les parties A et B peuvent être traitées idépendamment.

                        On considère le graphe Γ ci-dessous:

                        Gr576    

        Partie A

                1. Ce graphe admet-il une chaîne eulérienne? Justifier la réponse.

                    Si oui donner une telle chaîne.

                     Réponse:

                          Faisons le tableau des degrés des sommets:                    

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

                       Ainsi le graphe qui est non orienté et  connexe ( simple ) a exactement

                      deux sommets de degré impair qui sont D et G. 

                      Conclusion:    D'après le Th. d'Euler il admet au moins une chaîne

                       eulérienne reliant les sommets D et G.

                       On peut citer :  DBACBEGFEDFCDG

               2. Ce graphe admet-il un cycle eulérien? Justifier la réponse. Si oui donner

                   un tel cycle.

                     Réponse:

                         Non. Comme le nombre de sommets de degré impair n'est pas nul

                         le Th. d'Euler indique qu'il n'y a pas de chaîne eulérienne.    

                3.  Donner la matrice Massociée au graphe Γ. Les sommets seront pris

                     dans l'ordre alphabétique:  A,B,C,D,E,F,G

                     Réponse:

                     La matrice M est:

                                           Matpondich

          Partie B

              Soit le graphe:

              Graphe pondichery   

        1. Déterminer le plus court chemin en minutes, reliant la gare B à la gare G.

             Justifier la réponse grace à un algorithme.

         2. Quelle est la longueur en minute de ce chemin?      

     Réponse:

                1.a. Le chemin le plus court en minutes est BCDFG .              

                        En effet:

                                  Tableau de Moore:

         Rep

                           Graphe pondichery2

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