INFO TEST 2 28 janvier 2014

                INFO  TEST  GRAPHES    BTS1B                                28 janvier 2014              

            EXERCICE 1               

                                    t1.png

              L'entreprise Nibor and Ymerej 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.

              2. Donner sa matrice adjacente M.

              3. Trouver la matrice M2  .

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

              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?

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

          REPONSE:

             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:    On  peut considérer:

                                Gr753 1

              2. Donner sa matrice adjacente M.

                  Réponse:      On a : 

                                                       M14 1

              3. Trouver la matrice M2  .

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

                       Réponse: 

                        Un double clic est un chemin de longueur 2

                          On considère:

                                                 Ma12

                            Donc :

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

                                Conclusion :  il y en a donc   19 

             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:     OUI

                            Il suffit de considérer :    AEBCDA

                                       Attention on ne repasse par A qu'à la fin.      

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

              EXERCICE 2

                 On considère le graphe G de sommets A B C D E F de matrice d'adjacence:

                     Matriceds 1

               1. a. G admet-il une boucle ? 

                       Non.

                 En effet la diagonale principale n'a que des zéros

                   b. G est-il orienté?  

           OUI.  

                En effet  la matrice M n'est pas symétrique par rapport à la diagonale principale.

               2. Donner le tableau des prédécesseurs et des niveaux.

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

              3. Calculer les matrices M2   ,   M3  ,  M4  .

                Matriceds2       Matriceds23 1

                         M1413

                        M5 = 0

                      Il y a  2 + 2 + 2 = 6  chemins de longueur 3

                 b. La matrice de la fermeture transitive du graphe G est:

                          Ferm

                     On a :

                                 Matprim

               4. Dessiner le graphe G.

                      t3.png

               5.  On considère pour les arcs  la pondération en minutes indiquée

                    par le tableau suivant:                  

→  A   B   C  D   E F
A    7 11      
B     16  4    
C         14  5
D         17  
E           12
F            

  Compléter le tableau de Moore-Dijstra ci-dessous et trouver le trajet de durée minimale de A à F

   du graphe G.  

   Mooore4

   Il vient:

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

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

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