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 = { 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.
x1 et x3 sont les antécédents de x2 .
x2 est l'antécédent de x3
b. L'application f est-elle une injection de E dans E ? ( Justifier ).
NON. x1 et x3 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 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 .
Le seul arc d'origine x1 est l'arc ( x1 , x2 ).
On n'a pas les arcs orientés ( x1 , x3 ) ni ( x1 , x1 ).
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 /
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]
----------------------------------------------------------------------------------------------------------