INFO TEST GRAPHE janvier 2014

                    Soit G un graphe orienté simple de sommets ABCDEF dont

                   la matrice adjacente est :

                           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.

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

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

                       Réponse:

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

                             Réponse:

                      Les matrices  M³  , M⁴  , M⁵  ,M⁶   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 M² 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 M³ est la matrice nulle

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

                     Réponse:    NON car toutes les matrices  , M⁴  , M⁵  ,M⁶   , ... 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 :

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

                           Réponse:  

                  10. a . Dans chacune des matrices  M²  , M³  , M⁴  , M⁵  ,M⁶  

                                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⁵  ,M⁶    

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

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

                                     booléennes      M ,  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 

                                                  D'où :    A = M '

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

            EXERCICE 3                   

                             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: 

              2. Donner sa matrice adjacente M.

                  Réponse:      On a : 

              3. Trouver la matrice M²  .

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

                       Réponse:  On a :  

                            Donc :

                            Il suffit d'ajouter tous les termes de la matrice M²      

                                  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 4   ( Si vous avez le temps )

               Compléter le tableau et trouver le trajet de durée minimale

                  de A à F du graphe G suivant:

                   ( La pondération est en minutes )

              REPONSE:    Il existe plusieurs façons de procéder:

           ► Méthode par le calcul sur le graphe:

                         En chaque sommet on met la plus courte durée depuis le départ et

                         en mettant le prédécesseur.

                         Quand c'est terminé, on recule du sommet

                         d'arrivée  jusqu'au sommet de départ.

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

                       On peut conclure en se remettant dans le bon sens.

                   Conclusion:  Le chemin le plus court est :   ACF de 16 mn