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 / |
AIDE: 289140.htmRPl
• Laquelle des matrice suivantes est la matrice M² ? ( Barrer les deux mauvaises matrices . )
| / 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. AIDE: 289140.htmRPl
...............
• Faire le tableau des prédécesseurs et des successeurs.
PREDECESSEURS
SOMMETS
SUCCESSEURS
A
B
C
• Combien de chemins de longueur 2 de A à C y a -t- il ? ...................
Citer ces chemins: ......................
• Combien de chemins allant à C et de longueur 2 y a - t- il ? .................
• On admet que : AIDE: 289140.htmRPl
| / 2 | 2 | 3 \ | |
| M3 = | | 1 | 1 | 2 | |
| \ 2 | 1 | 2 / |
Combien de chemins de longueur 3 y a-t-il ? .................... ,
Combien de chemins de longueur 3 d'origine A et d'extrémité C y a-t-il ? ,
............................
Citer ces chemins.
...................................
On choisit au hasard ( avec équiprobabilité ) un chemein de longueur 3 dans le graphe de G.
Quelle est la probabilité de l'événement E " Le chemin se termine par A" ? AIDE: 289140.htmRPl
..........................................
Quelle est la probabilité de l'événement F " Le chemin est un circuit" ?
( Un circuit étant un chemin qui revient au mêm sommet )
............................
On admet que la matrice booléenne M[2] est:
| / 1 | 1 | 1 \ | |
| M[2] = | | 1 | 0 | 1 | |
| \ 1 | 1 | 1 / |
http,289140.htmRP
Elle est obtenue en remplaçant tous les termes non nuls de M² par 1.
Calculer la somme booléenne M' = M (+) M[2] (+) M[3] . AIDE: 289140.htmRPl
.........................
Faire le graphe de matrice d'adjacence M'. Que remarquez-vous?
...................................