TEST GRAPHES janvier 2014 BTS

                         TEST  GRAPHES    BTS1                                        22 janvier 2014

              EXERCICE 1

                 Gr938  

              Soit G le graphe orienté simple ci-dessus.

                  1.Quelle est sa matrice adjacente M ?

                  2.Quel est l'ordre du graphe ?                     

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

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

Prédécesseurs Sommets
           
             
             
             
             
             
             

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

                 6. Trouver les matrices M2 , M3 .                  

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

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

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

           EXERCICE 2          

                    Soit G un graphe orienté simple de sommets ABCDEF dont

                   la matrice adjacente est :

                           t0.png

                  1. a. Comment interprétez-vous la présence de trois colonnes de zéros dans M ?

                       b. Comment interprétez-vous la présence d'une ligne de zéros dans M ?

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

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

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

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

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

                   6. Trouver les matrices  M2  , M3  , M4  , M5  ,M6  .

                   7.a. Combien y a-t-il de chemins de longueur 2 qui arrivent à E  ?

                      b. Combien y a-t-il de chemins de longueur 2 qui arrivent à F ?

                      c. Trouver tous les chemins de longueur 2.

                    8. a. Combien y a-t-il de chemins de longueur 3.

                             Citez les.

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

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

                             On obtient un nouveau graphe G ' appelé:

                             << fermeture transitive de G  >>.

                           b. Donner la matrice adjacente M ' du graphe G '.

                       10. a .Préciser les matrices booléennes :

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

                             b. Calculez la somme booléenne  A des matrices 

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

                                    c'est-à-dire  trouver la matrice A telle que: 

                                     sans-titre.png

                                 Comparer M ' et A.    

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

            EXERCICE 3                   

                                    t1.png

              L'entreprise Lime and Amairt 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 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

   Mooore

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