Chapitre 3 Graphes pondérés et probabilistes.pdf


Aperçu du fichier PDF chapitre-3-graphes-ponderes-et-probabilistes.pdf

Page 1 2 3 4 5 6 7 8 9 10 11 12




Aperçu texte


6   Lucas a raison : il s’agit de PRT avec un poids de 6 + 5 = 11.
7   PRQSV est une chaîne de poids 13 : Estelle a tort.
8   QSUQ n’est pas une chaîne de ce graphe : Karim a tort.
9   Voir livre page 95.
10   a. La somme des probabilités des arêtes issues de A fait 1,1.

b. La somme des probabilités des arêtes issues de B fait 0,6.
c. La somme des probabilités des arêtes issues de B fait 1,1.
d. Une arête issue de A a une étiquette égale à 1,1 et ne peut
être une probabilité.
11   Seuls A, B et D sont des graphes probabilistes.
12   a.
0,4
0,7
A
0,6
b.

0,8

A
0,2

0,5
0,3

A
0,7

0,3

A

0,2

B

1

13   La somme des arêtes issues de chacun des sommets fait
toujours 1 : il s’agit bien d’un graphe probabiliste (d’ordre 3).
14   Il suffit d’étiqueter trois arêtes : la boucle issue de B porte
une probabilité de 0,3, l’arête issue de A également et celle
issue de C porte une probabilité de 0,5.
15   a. Non : la somme des coefficients de chacune des lignes
ne vaut pas 1.
b. Oui : la somme des coefficients de chacune des lignes fait
toujours 1.
c. Non : il s’agit de la somme des colonnes. La transposée est
donc une matrice de transition.
d. Oui.
16   a. Non : il manque 0,1 à la seconde ligne.
b. Oui.
c. Non : il y a 0,1 en trop à la première ligne et 0,1 en moins à
la seconde.
d. Oui.
17   a. M =  0,9 0,1 
 0,7 0,3 

 0, 8 0,2 
b. M = 
 0,3 0,7 


c. M =  1 0 
 0,2 0, 8 
 0, 6 0, 4 
d. M = 
 0,7 0,3 

120

 0,7 0,1 0,2 
b. M =  0 0
1 
 0,2 0,5 0,3 
 0,55 0,35 0,1 
c. M =  0,25 0, 6 0,15 
 0,35 0, 05 0, 6 
 0 1 0 
d. M =  0 0 1 
 0 0,5 0,5 
 0,5 0,5 
= ( 0,52 0, 48
0,2 ) × 
 0, 6 0, 4 

)

 0,5 0,5 
P2 = P1M = ( 0,52 0, 48 ) × 
= ( 0,548 0, 452
 0, 6 0, 4 

)

( 0, 8

20 a. P1 = P0 M =

B

0,8

d.

0,7

0,5
B

c.

 0,7 0,1 0,2 

19 P = P M =
1
0

B

0,3

 0,3 0, 6 0,1 

18   a. M =  0, 4 0, 4 0,2 

( 0, 6



0, 4 ) × 


 1
P2 = P1M =  29 31  ×  4
 60 60 
5

6

3
4
1
6

1
4
5
6

3
4
1
6


 =  29 31 
  60 60 



 =  397 323 
  720 720 


 0 1 0
b. P1 = P0 M = ( 0,2 0,5 0,3 ) ×  1 0 0  = ( 0,5 0,2 0,3 ).


0 0 1
 0 1 0
P2 = P1M = ( 0,5 0,2 0,3 ) ×  1 0 0  = ( 0,2 0,5 0,3 ) .


0 0 1
21 P = P M3 =
3
0

(

 0,3 0,5 0,2 
0, 4 0,2 0, 4 ) ×  0,3 0,7
0 
 0,9 0, 05 0, 05 

3

= ( 0,3678 0,55455 0, 07765 )

22 a. P5 ≈

( 0,566

0, 434

)

b. P5 ≈ ( 0,344 0,312 0,344

)

23 La vérification est faite à l’aide de la calculatrice.
24 Voir livre page 95.
25 Il suffit de vérifier que P = PM à la calculatrice, par exemple.
26 Il suffit de vérifier que P = PM à la calculatrice par exemple.
27 Il faut trouver P tel que P = PM. On pose P =

(x

y ) . Ainsi :

P = PM ⇔ ( x y ) = ( 0,6 x + 0,1y 0, 4 x + 0,9 y

)

⎧ x = 0,6 x + 0,1y
⇔⎨
⇔ y = 4 x.
⎩ y = 0, 4 x + 0,9 y
Or x + y = 1 donc x = 1 et y = 4 .
5
5


1
4
Donc P =
.
 5 5 

POUR S’ENTRAÎNER
28 1. Seuls ACC, ABCC et CCAC sont reconnus.
2. On forme la matrice d’adjacence du graphe en considérant
les sommets de gauche à droite :