Bac Blanc Spé ES 1 mars 2013

                           INFO  EXERCICE Spé maths    Bac Blanc     1 mars 2013

         EXERCICE            5   Points    

                       Candidats ayant suivi l'enseignement de spécialité

                                    Un orcheste doit effectuer une tournée passant par les villes A,B,C,D,E,F,G,H 

                                      en utilisant le réseau autoroutier.

                                      Le graphe  Γ  ci-dessous représente les différentes villes de la tournée et les autoroutes

                                       reliant ces villes ( une ville est représentée par un point , une autoroute par une arête ):

                                                   grb-bl1mars2013.png

                     1. Est-il possible d'organiser une tournée en passant au moins une fois par chaque ville,

                            tout en empruntant une fois et une seule chaque tronçon d'autoroute ?

                          (La réponse sera justifiée). Si oui citer un trajet de ce type.

                           Réponse:

                           Une telle tournée constitue  une chaîne eulérienne.

                           Nous disposons du  Th. d'Euler:

                          << Un graphe connexe admet une chaîne eulérienne si et seulemen si le nombre

                          de sommets de degré impairvaut 0 ou 2. >>

                             • Ici le graphe non orienté est bien connexe car  il existe toujours au moins

                               une chaîne entre deux sommet distints.

                            •   Faisons l'inventaire des degrés des sommets.

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

                                        On a donc deux sommets B et E de degré impair seulement.

                            Conclusion :    Oui. Il existe une chaîne eulérienne reliant B et E.

                             On peut considérer:

                               B-A-C-B-D-C-E-G-H-F-D-H-E

                 2. On appelle M la matrice associée au graphe Γ ( les sommets étant pris dans l'ordre alphabétique ).

                      On donne la matrice  M3  .

                          matricemcube.png

                      Combien esxiste-t-il de chemins de longueur 3 allant de B à H? Préciser ces chemins.

                       Réponse:

                      Dans la matrice M3 le terme de rang ( 2; 8 ) est 3.

                           Conclusion:  il y a 3 chemins de longueur 3 allant de B à H.

                        Précisons ces trois chemins:

                              B-C-D-H            B-D-F-H           B-C-E-H  

               3. Des contrainte du calendrier imposent en fait d'organiser un concert dans la ville F

                  immédiatemment après un concert dans la ville A.              

                                 gr2b-bl1mars2013.png

                            Le graphe Γ  est complété ici par les longueurs en kilomètres de chaque tronçon

                           ( les longueurs des segments ne sont pas proportionnelles aux distances).

                                     gr3b-bl1mars2013.png

                          Déterminer , en utilisant un algorithme dont on citera le nom, le trajet autoroutier

                           le plus court ( en kilomètres ) pour aller de a à F.

                          Préciser la longueur en kilomètres de ce trajet.

                           Réponse:

                          Utilisons l'algorithme deMoore - Dijkstra pour proposer

                             un trajet de longueur minimale.

                           gr4b-bl1mars2013.png

                           F  ←  H(1200)  ←E( 1000)  ←C (700) ←A(500) ←A

                           Le trajet le plus court est : A-C-E-H-F   de 1200 km

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