MATR.GRAPH INFO

                             TEST   MATRICES-GRAPHES   BTS              25  janvier  2013

              EXERCICE 1         

                    Soit G un graphe orienté simple de sommets ABCDEF dont

                      la matrice adjacente est :

                  ATTENTON: Toute réponse doit être argumentée: OUI - NON ne sont pas suffisants.

                  1. a. Comment interprétez-vous la présence de trois colonnes de zéros dans M ?

                           Réponse:  Aucun arc n'arrive en A ni en B ni en C.

                       b. Comment interprétez-vous la présence d'une ligne de zéros dans M ?

                            Réponse:  Aucun arc ne part de F.

                   2. Le graphe G comporte-t-il des boucles ?

                             Réponse:  NON: car il n'y a que des 0 dans la diagonale principale.

                   3. Combien d'arcs G comporte-t-il ?

                             Réponse:   Dans M il y a 7 fois le 1. Il y a donc  7 arcs dans le graphe.

                        Donner le tableau des prédécesseurs et des successeurs.

                          Réponse:

                   4. Compléter le tableau par les niveaux des sommets.

                    Réponse:

                   6. Trouver les matrices  M²  , M³  , M⁴  , M⁵  ,M⁶  .

                       Réponse:

                           M⁴  = M⁵  =  M⁶   = matrice nulle        

               5. Proposer une représentation de G en l'ordonnant suivant les niveaux.

                   7.a. Combien y a-t-il de chemins de longueur 2 qui arrivent à E  ?

                           Réponse:     Deux car dans   M²    il y a deux  1 dans la cinquième colonne  

                      b. Combien y a-t-il de chemins de longueur 2 qui arrivent à F ?

                           Réponse:   Deux car dans   M²    il y a deux  1 dans la sixième colonne . 

                      c. Trouver tous les chemins de longueur 2.

                            Réponse: On a :

                                            ADE

                                            BDE 

                                            CEF

                                            DEF

                    8. a. Combien y a-t-il de chemins de longueur 3.

                             Citez les.

                           Réponse:   Deux car dans M³ il y a deux fois 1

                                     On a :    ADEF

                                                   BDEF  

                         b. Existe-t-il des chemins de longueur supérieure à 3.

                             Réponse:    NON car    M⁴    est  déjà la matrice nulle.

                     9. a. Reproduire le graphe précédent en rajoutant les raccourcis.

                             On obtient un nouveau graphe G ' appelé:

                             << fermeture transitive de G  >>.

                             Réponse:

                                          Il y a 4 raccourcis  que l'on met en couleur.

                           b. Donner la matrice adjacente M ' du graphe G '.

                                    Réponse:   On a 

                          On voit qu'il y a dans M ' quatre 1 de plus que dans M.

                          Chaque 1 supplémentaire correspond à un raccourci.

                       10. a . Préciser les matrices booléennes :

                                  M ^{[ 2 ]}  , M^{[ 3]}   , M^{[ 4 ]}  , M^{[ 5 ]}  ,M^{[ 6 ]}  .

                                 Réponse:    M²  , M³  , M⁴  , M⁵  ,M⁶    respectivement ici

                                                  M ^{[ 2 ]}  , M^{[ 3]}   , M^{[ 4 ]}  , M^{[ 5 ]}  ,M^{[ 6 ]}  .                     

                               b. Calculez la somme booléenne  A des matrices 

                                           M ,    M ^{[ 2 ]}  , M^{[ 3]}   , M^{[ 4 ]}  , M^{[ 5 ]}  ,M^{[ 6 ]}  

                                    c'est-à-dire 

                                  Trouver la matrice A telle que: 

                                 Comparer M ' et A.    

                                  Réponse:    On a 

                                              Donc:        M ' = A.  

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

            EXERCICE 2                   

              L'entreprise Ynot and Ifauol Company doit créer un site internet pour un particulier.

                      Ce site site internet doit comporter 5 pages notées B , C , D, E

                      et la page d'accueil A.

                      De chacune des pages B, C, D, E en cliquant on doit pouvoir

                      revenir à la page d'accueil.

                      On doit pouvoir à partir de la page d'accueil A, en cliquant, obtenir l'accès

                      directement aux pages D et E.

                       Depuis la page E on doit pouvoir en cliquant obtenir la page B et la page C.

                       On doit pouvoir depuis la page B en cliquant obtenir la page C.

                       En fin à partir de la page C en cliquant on doit pouvoir obtenir la page D.

                       Il n'est pas prévu de bouton sur lequel en cliquant on reste sur la même page.

              1. Faire la représentation du site en considérant le graphe G dont les

                 sommets sont A, B, C, D, E et en considérant les "clic " comme des arcs.

                              Réponse:

              2. Donner sa matrice adjacente M.

                            Réponse:   On a 

              3. Trouver la matrice M²  .

                                  Réponse:

                   Combien de double " clic" peut-on  faire pour aller d'une page à une autre?                  

                             Réponse:   La somme totale des termes de la matrice M²  l'indique.

                                                          19  chemins de longueur 2 sont possibles

             4. Est-il possible, en cliquant plusieurs fois, de partir de la page d'accueil

                 pour consulter successivement toutes les pages du site puis

                de revenir à l'accueil?

                    Réponse:    OUI.      En considérant  A  E B C D A

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

              EXERCICE 3   ( Si vous avez le temps )

               1. Trouver le ou les trajets de durée minimale de A à F du graphe G suivant.

                        ( La pondération est en minutes )

                 Méthode rudimentaire:

                  On fait un inventaire:

                  •    ACEF :           11 + 14 + 12 = 37   

                  •    ACF :                      11  +  5 = 16     

                  •    ABCEF:   7  +  16  +  14  12  = 49

                  •      ABCF :    7  +  16  +  5  = 28

                  •      ABDEF: 7  +  4  +  17  +  12  =  40

                     Conclusion :  ACF de 16 mn est le plus court trajet de A à F

             Autre méthode  : 

               En écrivant dans  le graphe orienté.

                On avance en mettant chaque fois le temps le plus court

              pour arriver au sommet où l'on est.  les calculs et

              comparaisons se font dans le graphe orienté.

            Par exemple , en C   la durée la plus courte  en partant du sommet A  si l'on compare

                  11   et    7 + 16 = 23    est 11    

                 Donc à côté de C on met 11 ( A ) c-à-d  11 mn  depuis A

                             F ← 16(C)  ← 11(A)  ← A

                            Donc le chemin le plus court est :   ACF de 16 mn

             Autre méthode : Un tableau de  Moore-Dijstra

                     ( Pas au programme de BTS  SIO mais au programme de la spé maths en TES )                    

           2.  Donner les niveaux des sommets. 

                        Réponse:

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