INFO TEST
NOM: ..................... PRENOM: .............. DATE: Mars 09 CLASSE : BTS1
Soit A , B , C les trois sommets d'un graphe orienté G de matrice d'adjacence
la matrice M ci-dessous:
/ 1 | 0 | 1 \ | |
M = | | 1 | 0 | 0 | |
\ 0 | 1 | 1 / |
• Laquelle des matrice suivantes est la matrice M² ? ( Barrer les deux mauvaises matrices . )
C'est la troisième.
/ 0
1
2 \
/ 1
0
0 \
/ 1
1
2 \
| 1
0
1 |
| 1
0
1 |
| 1
0
1 |
\ 1
1
1 /
\ 1
1
1 /
\ 1
1
1 /
• Construire le graphe G. RETOUR http://www.mathemaths.com/rubrique,test-graphe-bts1,289113.html
• Faire le tableau des prédécesseurs et des successeurs.
PREDECESSEURS
SOMMETS
SUCCESSEURS
A B
A
A C
C
B
A
A C
C
B C
• Combien de chemins de longueur 2 de A à C y a -t- il ? Deux
Citer ces chemins: AAC ACC
• Combien de chemins allant à C et de longueur 2 y a - t- il ? Quatre
2+ 1+ 1 = 4
Il suffit de sommer les termes de la colonne de C dans la matrice M².
• On admet que : http://www.mathemaths.com/rubrique,test-graphe-bts1,289113.html
/ 2 | 2 | 3 \ | |
M3 = | | 1 | 1 | 2 | |
\ 2 | 1 | 2 / |
• • Combien de chemins de longueur 3 y a-t-il ? SEIZE
2 + 2 + 3 + 1 +1 + 2 + 2 + 1 + 2 = 16 Somme des termes de la matrice M3
• • Combien de chemins de longueur 3 d'origine A et d'extrémité C y a-t-il ?
3
• • Citer ces chemins.
AAAC ACCC AACC
• • On choisit au hasard ( avec équiprobabilité ) un chemin de longueur 3
dans le graphe G . http://www.mathemaths.com/rubrique,test-graphe-bts1,289113.html
• • • Quelle est la probabilité de l'événement E " Le chemin se termine par A " ?
Soit Ω l'univers ds possibles. Il contient les 16 chemins de longueur 3.
Card( Ω ) = 16
E est l'ensemble des chemins de longueurs 3 qui se terminent par A.
Card( E ) = 2 + 1 + 2 = 5
Il suffit d'ajouter les termes de la première colonne de M3 .
Comme P( E ) = Card( E ) / Card( Ω ) on a :
Conclusion : P( E ) = 5 / 16
• • • Quelle est la probabilité de l'événement F " Le chemin est un cicuit " ?
( Un circuit étant un chemin qui revient au même sommet )
F est l'ensemble des circuits de longueur 3.
Card( F ) =2 + 1 + 3 = 5
Il suffit d'ajouter les termes de la diagonale principale de la matrice M3 .
Comme P( F ) = Card( F ) / Card( Ω ) on a :
Conclusion : P( F ) = 5 / 16
• On admet que l'on a la matrice booléenne : RETOUR 289113.htmRPl
obtenue à partir de la matrice M² , en remplaçant les termes non nuls par 1.
/ 1
1
1 \
M[2] =
| 1
0
1 |
\ 1
1
1 /
• • Calculer la somme booléenne suivante : M ' = M (+) M[2] (+) M[3] .
/ 1 | 0 | 1 \ | / 1 | 1 | 1 \ | / 1 | 1 | 1 \ | |||
M (+) M[2] (+) M[3] = | | 1 | 0 | 0 | | (+) | | 1 | 0 | 1 | | (+) | | 1 | 1 | 1 | |
\ 0 | 1 | 1 / | \ 1 | 1 | 1 / | \ 1 | 1 | 1 / |
On obtient :
/ 1
1
1 \
M ' =
| 1
1
1 |
\ 1
1
1 /
• • Faire le graphe de matrice d'adjacence M'. Que remarque-t-on ?
On a les 4 raccourcis. RETOUR 289113.htmRPl
On remarque M' est la matrice d'adjacence de la fermeture transitive de G.