INFO Problèmes 2 bac ES spé

                          INFO    PROBLME n ° 2               spé   TS                   10 Octobr 2012

             PROBLEME 2              

             1. Un touriste veut visiter la ville en n'enpruntant  que des pistes cyclables.
                             Grapheexbactes

                a.Le touriste a-t-il  la possibilité d'effectuer un parcours en empruntant une et une seule

                   fois toutes les pistes cyclabes? 
       
                     REPONSE:
              
                  Cela revient à voir s'il y a une chaîne eulérienne.
               
                  Donnons le tableau des degrés ds sommets:
 Sommets         A    B    C      D     E     F     G 
Degrés   3    4  4   3    4  4  2
  
                       Il y a deux sommets seulement de degré impair et le graphe est connexe.
  
                        Donc d'après le Th d'Euler  il existe bien une chaîne eulérienne
 
                       allant de l'un à l'autre c-à-d reliant A et D.

                      Conclusion : OUI. Il est possible  d'effectuer un parcours
 
                      en empruntant une et une seule fois toutes les pistes cyclabes? 

              b. A la fin du parcours précédent, pourra-t-il rendre son vélo à la station où il l'a emprunté?
          
                     REPONSE:

                    Cela revient à regarder s'il y a un cycle eulérien.
 
                    Or les degrés des sommets ne sont pas tous pairs.
 
                    Donc d'après le Th d'euler il n'y a pas de cycle eulérien.

                 Conclusion . Non . Le touriste ne pourra pas rendre son vélo à la station où il l'a emprunté.     
         2.     Doit-il calculer M2 , M3 ou  M4 pour connaître le nombre de trajets?

                   REPONSE:

                    Comme le touriste est allé de F à E en passant par deux stations intermédiaires,

                     son chemin est de longueur 3.

                    Conclusion:   C'est la matrice M3  qui  lui permettra de trouver le nombre de chemins de longueur 3

                    entre F et E.
 
                          F est le 6 ième sommet  et G st le 7 ième sommet.

                           C'est donc le terme de rang ( 6 ; 7 ) de la matrice M3 qui lui indiquera  le

                          nombre de chaînes de f à G de longueur 3.

                             ( c-à-d   6 ième ligne et 7 ième colonne )
            3.  En utilisant un algorithme, déterminer un tel parcours et
 
                     le temps nécessaire pour l'effectuer.
 
                   REPONSE: 
                                 Tableaumoore1 1

                        On retient:
 
                         G    (  27 D) -----   D ( 22B) ------- B(  7 A)  ---   A( 0 )
 
                         Donc le trajet le plus court est :


                                A ------  B   --------D  ---------G      de durée   2 7 mn
                      
                                                     Grapheexbactes2

             4.  Proposer une coloration des stations avec le minimum de couleurs.

                    REPONSE:

                                   Ordonnons ls sommets suivant les  degrés décroissants:

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

                         L'ordre du plus grand sous graphe complet est:    m = 3
                        
                         Le degré le plus élevé est :    Δ = 4

                       Donc le nombre chromatique est tel que :  m ≤ λ ≤ Δ + 1
                
                            c-à-d           3   ≤ λ ≤  5

  Sommets     B       C     E      F        A    D    G   
Couleurs   VERT  BLEU ROUGE  VERT ROUGE BLEU ROUGE


                  Le nombre chromatique est :    λ = 3

                 Conclusion : On a besoin de 3 couleurs.

                       
                             Grapheexbactes1
------------------------------------------------------------------------------------------------------------------------