MATR.GRAPH

                       Matrices et Graphes   décembre 2012 

              EXERCICE 1            

                    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 2                   

                                    t1.png

              L'entreprise Ynot and Ifauol 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 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.

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