MATRICE.GRAPHE BTS

                                      Matrices et Graphes     BTS 

              EXERCICE 1            

                    Soit G un graphe orienté simple de sommets ABCDEF dont

                   la matrice adjacente est :

                           t45-1.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 ?

                      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. a. Combien d'arcs G comporte-t-il ?

                      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.

                  6. Trouver les matrices  M , M , M , M ,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.

                            ( 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  >>.

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

                  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 :

                       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.    

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

            EXERCICE 2                   

                                    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.

              2. Donner sa matrice adjacente M.

              3. Trouver la matrice M .

                   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 A

                 pour consulter successivement toutes les pages du site puis

                de revenir à l'accueil A ?

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

              EXERCICE 3   (  S'il vous reste du temps vous pouver faire l'exercice. )

               1. Trouver le ou les trajets de durée minimale de A à F du graphe G suivant.

                        ( La pondération est en minutes )

                                t3.png

                              ( Il faudra faire figurer sur le graphe les explications )

               2.  Donner les niveaux des sommets.

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