INFO EXGRAPHE EPREUVE BTS FR00

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

           x1   et  x  sont les antécédents de x2 .

           x2   est l'antécédent de x 

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

             NON.   x1   et  x  bien que différents ont la même image  x2  .

             f ne conserve pas la distinction.

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

             NON.   x1   n'a pas d'antécédent par f.

       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 .

               Le seul arc d'origine  x  est  l'arc (  x , x ).

               On n'a pas les arcs orientés (  x , x ) ni (  x , x ).

          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   /

  Il y a 3 raccourcis dont deux boucles.

   La matrice de la fermeture transitive est donc:

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

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

         Pour trouver  M[2]    il suffit de considérer la matrice M²

       puis de remplacer les termes non nuls par 1 en laissant les 0.

 /   0   0  1   \
M[2]    = |    0   1  0    |
 \   0   0  1   /

       Même méthode pour M[3]  

 /   0   1  0   \
M[3]    = |    0   0  1    |
 \   0   1  0   /

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

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

 /  0 1  0  \  / 0 0  1  \    / 0 1  0 \
 M (+) M[2]  (+) M[3]  =    |    0 0  1   | (+) |   0 1  0   | (+) |   0 0  1  |
     \  0 1  0  /  \  0 0  1  /    \  0 1  0 /

 /   0   1  1   \
M (+) M[2]  (+) M[3]  = |    0   1  1    |
 \   0   1  1   /

                    On a bien l'égalité. M ' = M (+) M[2]  (+) M[3]   

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