INFO TEST GRAPHE janvier 2014

     INFO     TEST  GRAPHES    BTS1                                        22 janvier 2014

              EXERCICE 1

                 Gr938  

              Soit G le graphe orienté simple ci-dessus.

                    1.Quelle est sa matrice adjacente M ?

                      Réponse:            

                                   Mtm

                  2.Quel est l'ordre du graphe ?

                         Réponse : 7 car il y a 7 sommets.

                 3. Le graphe possède-t-il un circuit ?

                        Réponse:  OUI .  ABCA

                 4. Donner le tableau des prédécesseurs.

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

                 5.Peut-on déterminer les niveaux des sommets?

                     Réponse:  Non  car il y a un circuit.

                6. Trouver les matrices M2 , M3 .

                    Réponse:   

                      Mtm2

                 7. Combien existe-il de chemins de longueur 2?

                     Réponse :   

                   La somme des termes de la matrice M est 11.

                           Il y a donc 11 chemins  de longueur 2.

                 8. Combien existe-il de chemins de longueur 2 qui partent du sommet B.

                   Réponse : Il y en a 3.

                                      BCA       BCF     BDE

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

           EXERCICE 2           

                    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 3                   

                                    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 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 )

                                t3.png

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

           ► Méthode par le calcul sur le graphe:

                                 figg1.gif

                         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

                 ►Avec le tableau de Moore-Dijstra :                               

                 (  Seulement au programme de spé maths en TES  )

  Mooore4

                 Il vient en reculant :

                  F ←  C ( 16 )  ← A( 11) 

            Conclusion : Le chemin de durée minimale est ACF de 16 mn         

             ► Méthode élémentaire :

                 Elle ne nécessite aucune connaissance.

                 On fait un simple inventaire des chemins possibles:

                  •    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

              On compare les durées.

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

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