INFO MATRICE GRAPHE 2

                           INFO   Matrices et Graphes 2         BTS 

              EXERCICE 1            

                    Soit G un graphe orienté simple de sommets ABCDEF dont

                   la matrice adjacente est :

                           t45-2.png

                           Les réponses attendues ne sont pas OUI , NON simplement.

                           Ce qui entraîne votre conviction doit figurer sur la copie.

                  1. a. Y a-t-il des arcs qui "arrivent" en A ou C ou F ?

                           Réponse:  NON. La première colonne , la troisième colonne et 

                                            la sixième colonne n'ont que des zéros.

                      b. Comment interprétez-vous la présence de deux lignes de zéros dans M ?

                           Réponse:    Les deuxième et cinquième lignes n'ont que des 0.

                                                Aucun arc ne part donc du sommet E ni du sommet B.

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

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

                                                de la matrice M.

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

                          Réponse:   Il y a 6 fois le 1 dans la matrice M.

                                             Il y a donc   6 arcs.

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

Prédécesseurs Sommets successeurs  
  A   D   E
    C D B    
  C    B  E
     A  D    B
     A C F E  
  F     E  

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

Prédécesseurs Sommets Niveaux  
  A       0
     C D B       2
  C       0
     A  D       1
     A C F E       1
  F       0 

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

                       Réponse:

                                                 s0-1.png

                  6. Trouver les matrices  M , M , M , M ,M6  .

                             Réponse:

                                            s1-1.png

                      Les matrices  M , M , M ,M6   sont les matrices nulles

                  7.a. Combien y a-t-il un chemin de longueur 2 qui arrive à E  ?

                         Réponse: NON car la cinquième colonne de M2 est faite de 0.

                     b. Combien y a-t-il en tout de chemins de longueur 2 ?

                        Citez ce ou ces chemins.

                          Réponse:   La somme des termes de la matrice  M est 1.

                                              Il y a donc un seul chemin de longueur 2.

                                              C'est    ADB

                  8. a. Y a-t-il des chemins de longueur 3.

                      Réponse :  NON  car M3 est la matrice nulle

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

                     Réponse:    NON car toutes les matrices  , M , M ,M6   , ... sont nulles.

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

                            ( Un raccoucis étant un arc entre deux sommets

                             qui sont déjà joignable par un chemin existant. )

                             On obtient un nouveau graphe G ' appelé:

                              << fermeture transitive de G  >>.

                                   Réponse:    G '  est :

                               s5.png

                      b. Donner la matrice adjacente M ' de ce nouveau graphe G '.

                           Réponse:  

                                                                s10.png

                  10. a . Dans chacune des matrices  M , M , M , M ,M6  

                                on laisse les 0 et on remplace les termes autres que 0 par des 1.

                                On obtient ainsi des matrices booléennes , n'ayant que des 0 ou des 1.

                                On les note respectivement :   

                                 M [ 2 ]  , M[ 3]   , M[ 4 ]  , M[ 5 ]  ,M[ 6 ]  .

                                 Préciser ces cinq matrices booléennes :

                                Réponse: On retrouve ici les matrices   M , M , M , M ,M6    

                                                  car  elles étaient déjà booéennes.

                       b. Calculez la matrice A somme booléenne des matrices 

                                     booléennes      M ,  [ 2 ]  , M[ 3]   , M[ 4 ]  , M[ 5 ]  ,M[ 6 ]  

                                    ( Rappel:    0 + 0 = 0        1 + 0 = 0 + 1 = 1      1 + 1 = 1  )

                                    Comparer M ' et A.  

                                  Réponse:       Comme les matrices  M[ 3]   , M[ 4 ]  , M[ 5 ]  ,M[ 6 ]    sont  nulles

                                                           cela revient à   considérer la somme booléenne 

                        s48.png

                                                  D'où :    A = M '

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

            EXERCICE 2                   

                                    t1.png

                             L'entreprise Nevets and  Sirhc Society 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 B et C.

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

                       On doit pouvoir depuis la page E en cliquant obtenir la page D.

                       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: 

                                t70.png

              2. Donner sa matrice adjacente M.

                  Réponse:      On a : 

                                                       t110.png

              3. Trouver la matrice M .

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

                       Réponse:  On a :  

                                                 t109.png

                            Donc :

                            Il suffit d'ajouter tous les termes de la matrice M2      

                                  il y en a donc :  18

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

                 pour y revenir seulement  à la fin en ayant pu  consulter successivement

                  toutes les pages du site ?                

                          Réponse:     NON car si on part de A   pour B on doit revenir  en A.

                                                   et si l'on part de A pour C on ne peut pas atteindre B

                                                  sans repasser par A entre temps.                            

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

     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 )

                                t3.png

                                 figg1.gif

                             F  16(C)   11(A)   A

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

               2.  Donner les niveaux des sommets. 

                        Réponse:

Prédécesseurs Sommets Niveaux
  A 0
A B 1
AB C 2
B D 2
CD E 3
EC F 4


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