INFO TEST TES Spé décembre 2011

                              INFO TEST       spé maths      2012

             EXERCICE 

                On considère le graphe G dont la matrice d'adjacence  M est ci-dessous.


             Matrextes

                1. Quel est son ordre ?    

                   Il est d'ordre 6 car la matrice M est carrée d'ordre 6.   

                 Il a donc 6 sommets.        

              2. Le graphe G est-il orienté?

                       OUI. En effet la matrice M n'est pas symétrique par

                       rapport à la diagonale principale.

             3. En numérotant ls sommets :  ( 1 ) ,  ... etc 

                donner une représentation possible de G.

                      On peut proposer:

                         Graphe238 1

            4. Le graphe est-il complet ?

                   NON.  Les sommets (4 ) et (5) ne sont pas adjacents.

           5.Le graphe est-il connexe?

                     NON. Par exemple on ne peut pas partir du sommet ( 6 )

                     pour  joindre un autre sommet à l'aide d'une chaîne.

           6. Le graphe possède-t-il une boucle?

                 NON. Il n'y a que des 0 dans la diagonale principale.

          7. Existe-t-il une chaîne qui passe une fois et une seule par toutes les arêtes?

                NON. Trois arêtes arrivent au sommet ( 6 ). Or on ne peut pas en repartir.

                 Deux des trois arêtes qui arrivent au sommet ( 6) ne peuvent donc être 

                dans une chaîne.

                 Aucun tableau des degrés des sommets n'est à considérer car 

                 le Th. d'Euler ne s'applique pas ici  comme le graphe n'est pas connexe.

          8. Calculer les matrices M2  , M3 et M4   .

                 Que pouvez-vous en déduire?

   /  0  2   1  0   0 2  \ 
  |   0  0 0 0 0 0  |
  |   0  0 0 0 0 0  |
M2 =  |   0  0 0 0 0 1  |
  |   0  0 0 0 0 2  |
   \  0  0 0 0 0 0 /

 

   /  0  0   0  0   0 3  \ 
  |   0  0 0 0 0 0  |
  |   0  0 0 0 0 0  |
M3 =  |   0  0 0 0 0 0  |
  |   0  0 0 0 0 0  |
   \  0  0 0 0 0 0 /

                 M4  est la matrice nulle. Donc il n'y a aucune chaîne de longueur 4.

                Le 3  à l'intersection de la première ligne et de la sixième colonne 

               indique qu'il y a 3 chaînes de longueur 3 qui vont de ( 1 ) à ( 6).

            9. Combien de chemins relient  le sommet ( 1 ) au sommet  ( 6 ) 

                de toutes longueurs possibles ?

                   Il y en a 5. ( 2 chemins de longueur 2 et  3  chemins de longueur 3)

                    Il suffit d'ajouter les termes de rang ( 1 ; 6 ) des matrices 

                    M ,  M2  , M3 et  M4  .

                         0 +  2  +  3  + 0 = 5

          10. On donne le tableau suivant  qui indique la durée de chaque 

               liaison entre deux sommets adjacents.

           Donner un trajet de durée minimale en minutes entre les sommets ( 1) et ( 6).              

      →  ( 1)  ( 2 )  ( 3 )  ( 4 )   ( 5 )  ( 6 ) 
 ( 1 )     75    45  30  
 ( 2 )            20
 ( 3 )            25
 ( 4 )    20        50
 ( 5 )    40  35      
 ( 6 )            

  Graphe2382                 

       •  Il y a seulement  5 chemins ( 2 chemins de longueur 2 et 3 chemins  de longueur 3 )

         du sommet ( 1 ) au  sommet ( 6).  il est donc possible de procéder par inventaire ici:

              • ( 1 ) → (  2  )  → ( 6 )                        Durée:     75 + 20 = 95

              •  ( 1 ) → (  4 )  → ( 6 )                        Durée:      45 + 50 = 95

              •   ( 1 ) → ( 5  )  → ( 2  )  → ( 6 )          Durée:      30  + 40 + 20 = 90

              •   ( 1 ) → ( 5  )  → ( 3  )  → ( 6 )          Durée   30 + 35 + 25 = 90

             •    ( 1 ) → ( 4  )  → ( 2  )  → ( 6 )          Durée:   45 + 20+ 20 = 85

                Le plus court chemin recherché est ( 1 ) ( 4 ) ( 2 ) ( 6 )   d'une durée de 85 mn.

                      Chmini

            •      Autre méthode avec Moore-Dijkstra:

             Tableau:      

                      Moore2

                    En remontant on rencontre:

      ( 6 ) ( en provenance de 85 ( 2 ) ) ---- ( 2 ) (en provenance de  65(4) )  ---- (4)  ( 45 (1) )  ---- ( 1 ) 

         Le chemin minimal est donc dans l'ordre contraire:

                  ( 1 )   ---- ( 4)  ---- ( 2 )  ---- ( 6 )

           Sa durée est 85 mn

 Explication 4

             De façon générale quand vous aurez compris le processus il faudra mettre le moins de choses

               possibles dans le tableau.

             Il était possible à la  5 ième ligne du tableau de sélestionner pour la ligne ( 3 ) au lieu de ( 2 ).

             Le tableau s'écrit alors :

 Autrechoix

      Cela ne change pas grand chose ici. Quand on sélectionne un sommet c'est pour une

           ligne pas pour le chemin que l'on cherche.

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

                      Remarque  pour le tableau:

                    C'est une méthode ou une " recette "  très fastidieuse  .

                   Dans certains cas avec des circuits ou des boucles la méthode ne marche pas.

            •  A chaque ligne on prend toujours la plus petite durée pour la sélection du sommet de la ligne

               ( Cela ne préjuge pas qu'il soit dans le trajet de longueur minimale )  

               même si ce n'est pas un sommet adjacent au sommet précédent sélectionné.

            • Pour les sommets adjacents à un sommet sélectionné on doit sommer

              le coefficient du sommet précédent selectionné avec la durée qui le sépare du sommet adjacent.

            • Un fois les coefficients mis sur une ligne on compare les coefficients avec la ligne du dessus

             pour prendre le plus petit. Ce n'est qu'après que on fait la selection du sommet sélectionné suivant.. 

           • Chaque fois qu'un sommet est sélectionné sa colonne est fermée.

          •Attention sélectionner un sommet ne signifie pas que ce sommet sera finalement dans le

            chemin minimal retenu.

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