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 = { x1 , x2 , x3 } et l'application f de E dans E définie par
f( x1 ) = x2
f( x2 ) = x3
f( x3 ) = x2
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 x1 , x2 et x3 , tels que les successeurs
de x1 , x2 , x3 sont respectivement f( x1 ) , f( x2 ) , f( x3 ) .
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 ( xi , xj ) lorsqu'il existe un chemin
d'origine xi et d'extrémité xj 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.
-------------------------------------------------------------------------------------------------------------------