TEST2 GRAPHE 28 janvier 2014 BTS

           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?

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

              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 ? 

                   b. G est-il orienté ?

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

               3. a.Calculer les matrices M2   ,   M3  ,  M4  .

                      Combien y a-t-il de chemins de longueur 3 ?

                   b. Trouver la matrice M ' de la fermeture transitive du graphe G.

                              Ferm

               4. Dessiner le graphe G.

               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.  

   Mooore

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