EX2 bac ES 2015

             INFO  EXERCICE 2   Spé maths            ES  Juin  2015

             On considère le graphe  74lo   ci-dessous:                                            

                   68lo

    Partie A

          1. Déterminer en le justifiant si ce graphe:

               a: est connexe.

                    OUI. .

                En effet: Deux sommets quelconques sont reliés par au moins un chemin.

                 Le chemin BGHFCEDA par exemple passe par tous les sommets au moins une fois.

                b. admet une chaîne eulérienne.

                     Tableau des degré.                         

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

                  Le graphe ( simple ) étant connexe et n'ayant aucun sommet de degré impair,

                 d'après le Th d'Euler, admet un cycle eulérien.

                  Donc:

                     Conclusion: Oui, le graphe admet une chaîne eulérienne, fermée.

               2. On note M la matrice adjacence associée à ce graphe en prenant les sommets dans l'ordre alphabétique.

                     On note:

                          55lo

                     Donner , en le justifiant le nombre de chemins de longueur 3 reliant E à B.

                    On a, dans M3 , 5 à l'intersection de la 5 ième ligne avec la seconde colonne.

                    Donc:

                       Conclusion: il y a 5 chemins de ongueur 3 reliant E et B.

                   Partie B

             1. D'après l'étude effectuée dans la partie A, le club alpin est-il en mesure de proposer:

                   a. un itinéraire au départ du refuge A qui passerait par tous les refuges en enpruntant une

                           et une seule fois chacun des des sentiers? Si oui proposer un tel itinéraire.

                   OUI. 

                En effet:

                    On a vu qu'il existait un cycle eulérien. Donc il existe un itinéraire qui passe 

                 par tous les refuges en enpruntant une et une seule fois chacun des des sentiers.

                 Sur cet itinéraire on peut commencer du refuge que l'on veut en particulier on peut partir de A.

                  On peut citer : ABGHBFCEHFEDA 

                  b.des itinéraires de trois jours( un jour correspondant à une liaisonentre deux refuges) 

                     reliant le refuge E au refuge B ? Si oui combien peut-il en proposer?

                       D'après la question partie A question 2 on a vu qu'il existait 5 chemins de longueur 3 reliant E à B.

                  Conclusion :    Cela signifie qu'il existe 5 itinéraires de trois jours reliant le refuge E eu refuge B.

               2. Le graphe 74loest complété ci-dessous par la longueur en kilomètres de chacun des sentiers.

                73lo                   

                   Le club désire aussi proposer à ses membres l'itinéraire le plus court reliant A à H.

                  Déterminer cet itinéraire et en préciser la longueur en kilomètres.

         Faisons un tableau de Moore

       

      80lo 1

             On considère:    H < -----F   <----   B  <------ A

            Donc : ABFH est l'itinéraire  le plus court     

                          Durée : 32 jours

                           90lo

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