MATRICE GRAPHE 2

              Matrices et Graphes 2         BTS 

              EXERCICE 1        

                    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 ?                        

                      b. Comment interprétez-vous la présence de deux lignes 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  M2  , M3  , M4  , M5  ,M6  .                         

                  7.a. Combien y a-t-il un chemin de longueur 2 qui arrive à E  ?                      

                     b. Combien y a-t-il en tout de chemins de longueur 2 ?

                        Citez ce ou ces chemins.                       

                  8. a. Y a-t-il des chemins de longueur 3.                   

                      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  M2  , M3  , M4  , M5  ,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 ,  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 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 A

                 pour y revenir seulement  à la fin en ayant pu  consulter successivement

                  toutes les pages du site ?                                     

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

        EXERCICE 3   ( Si vous avez le temps )

               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

                                
                       

               2.  Donner les niveaux des sommets. 

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