EX 00 SUR LES GRAPHES

  EXERCICE SUR LES GRAPHES ORIENTES SIMPLES  DE 2000N          MARS 2009

      EXERCICE 1      5 POINTS      

                Une entreprise veut créer un site Internet comportant 5 pages A , B , C , D , E .

                La structure des pages vérifie les conditions suivantes:

                   • La page A est la page d'accueil et sur chacune des autres pages figure un bouton

                     permettant de revenir directement à la page d'accueil. 

                   • On peut passer directement de la page A aux autres pages sauf à la page E.

                   •  On peut passer directement de la page B à la page E et de la page E à la page C.

            1. Dessiner une représentation du graphe orienté associé au site.

            2. Vérifier que la matrice d'adjacence M du graphe est :

     /    0       1       1       1       0    \
   /      1       0       0       0       1      \
M = |       1       0       0       0       0       |
   \      1       0        0       0       0      /
     \    1       0       1       0       0    /

 

 

           3. Calculer les deux matrices booléennes M[ 2 ]   et  M[ 3 ]  . Quelle est la signification

                des " 1 "  présents dans la matrice   M[ 3 ]  ?

          4. On admet que la matrice  M 3  = M × M ×M , où  × désigne la multiplication des matrices, peut

               s'écrire :       

     /    1       3       4       3       0    \
   /      4       1       1       1       1      \
M = |        3       0       0       0       1       |
   \      3       0        0       0       1      /
     \    3       1       1       1       1    /

                                  

                a. Déterminer le nombre de chemins de longueur 3 ayant pour origine B et pour extrémité A.

                   Ecrire ces chemins.

               b.  Ecrire les trois circuits de longueur 3

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