EX GRAPHES EPREUVE BTS FR00

 EXERCICE EPREUVE BTS FRANCE  00   SUR LES GRAPHES

     EXERCICE 4 POINTS

            Les questions 1) et 2) peuvent être traitées indépendamment l'une de l'autre.

     1. On considère l'ensemble E = { x , x2  , x3  } et l'application f de E dans E définie par

         f(  x ) =  x 

         f( x ) =  x 

         f(  x  ) =  x 

         a. Déterminer les antécendents  par f de chacun des éléments de l'ensemble E.

        b. L'application f est-elle une injection de E dans E ? ( Justifier ).

        c. L'application f est-elle une surjection de E sur E ? ( Justifier ).

       2. On considère le graphe orienté G , de sommets x , x et  x , tels que les successeurs

            de x , x2  , x sont respectivement   f(  x ) ,  f( x ) ,  f(  x  ) .

           a. Donner une représentation géométrique de ce graphe.

           b. On note M la matrice d'adjacence de G.  

               On constate que  :

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

               Expliquer pourquoi la première ligne de M est  0  1  0 .

          c. On note G ' la fermeture transitive de G.

              On rappelle que G' est le graphe obtenu en conservant les sommets de G

               et en ajoutant , s'ils n'existent pas  dans G, les arcs ( x , x )  lorsqu'il existe un chemin

              d'origine x  et  d'extrémité x  dans le graphe de G.

              Tracer la représentation géométrique de G' et vérifier que la matrice adjacente M '

               du graphe G'  est :

 /   0   1  1   \
|    0   1  1    |
 \   0   1  1   /

                  d. Calculer les matrices booléennes  M[2]    et   M[3]  .

                      Vérifier que M ' = M (+) M[2]  (+) M[3]      ,

                      où (+) représente l'addition booléenne des matrices.

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