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


 2 1 0
 16 10 5 
M =  0 0 1  , puis on calcule la matrice M4 =  0 1 0  .




0 1 0
0 0 1
4 = 5 qui donne le nombre de
On extrait ensuite le coefficient M1,3
chaînes de longueur 4 reliant le sommet vert au sommet rouge,
c’est-à-dire le nombre de mots de quatre lettres reconnus par
le graphe.
Ces mots sont : ABCC, CCAC, AACC, BBCC et BACC.
29 1. Seuls les mots RECOURS et RETORD sont reconnus.
2. Il faut au minimum trois lettres : il s’agit du mot EOR. On
peut aussi le vérifier en formant la matrice d’adjacence en
considérant les sommets de gauche à droite :
 1 1 0 0
M =  0 2 1 0  .
0 0 1 1


0 0 0 2
La première puissance de M comportant un coefficient non nul
à l’intersection de la première ligne et de la dernière colonne
est M3.
3. Par exemple : RETOUR.
30 Il suffit de reprendre la matrice d’adjacence précédemment
établie et de trouver respectivement :
4 = 6, M5 = 23 et M6 = 72.
M1,4
1,4
1,4
Il y a donc 6 mots de quatre lettres, 23 mots de 5 lettres et 72
mots de six lettres reconnus par ce graphe.
31 1. BACCALETS est un mot reconnu par le graphe, mais
pas BLEUS.
2. Non : il faudrait pour cela que le deuxième sommet en
partant de la gauche soit le sommet final (en rouge).
3. On forme tout d’abord la matrice d’adjacence de ce graphe
(pas d’ordre privilégié pour les sommets, on garde juste le
sommet vert en premier et le rouge en dernier), par exemple :
 0 1 0 0 0 0
 0 2 1 0 0 0


M =  0 0 0 1 1 1 .
0 0 1 0 0 0


 0 0 1 0 0 0
 0 0 0 0 0 0
5 = 6. Il y a donc bien six mots de cinq
On calcule ensuite M1,6
lettres reconnus par ce graphe.
32 Voir livre page 95.
33 Vrai : la distance entre le sommet de départ et celui de fin
est 2. Il s’agit du mot BE (aucune autre possibilité – on peut là
encore vérifier avec la matrice d’adjacence).
34 Faux : on ne peut avoir une succession de deux E dans
ce graphe.
35 Vrai : ABE, BCE, BDE et BEF.
36 Vrai.
37 a. A – B – C – D a un poids de 31.
b. B – E – C – D a un poids de 23.
c. C – G – A – B – G – F a un poids de 54.
38 1. Les parcours en trois étapes de A à D correspondent aux
chaînes de longueur 3 reliant A à D : A – B – C – D, A – B – E – D,
A – G – C – D et A – G – E – D.
2. Les poids respectifs sont 31, 31, 29 et 30. Le parcours le plus
court est donc A – G – C – D.

39 Oui si, et seulement si, on considère un graphe comportant
des arêtes de poids nul.
Oui : dans l’exercice précédent, A – B – C – D et A – B – E – D
ont même poids.
40 Voir livre page 95.
41 Vrai : il suffit d’additionner les poids des arêtes constituant
la chaîne.
42 Vrai : ce poids vaut 8.
43 Vrai : une rapide « exploration du meilleur » à la manière
de l’algorithme de Dijkstra aide à s’en convaincre.
44 La chaîne correspondante est A – D – F – G avec un poids
total de 510.
45 La chaîne correspondante est E – C – F – S avec un poids
total de 10.
46 Les chaînes correspondantes, toutes de poids total égal à 5
sont : A – B – F – H, A – C – G – H et A – F – H.
47 La chaîne correspondante est A – C – E – F – G avec un
poids total de 7.
48 Voir livre page 95.
50 1. La chaîne correspondante est O – P – L – H – T avec un
poids total de 46.
2. 46 minutes, donc Amélie sera en retard !
51 Faux : la chaîne correspondante est A – B – C – E – F – H
avec un poids total de 25.
52 Faux : la chaîne correspondante est B – C – E – F – H avec
un poids total de 22.
53

1
2

P

B

1
6

1
4
1
2

1
2

1
4
V

1
3

1
4

1
4

 0, 4 0, 6
0 
0,7 0,1 
 0 0,15 0, 85 

54 M =  0,2
55 1.  P0 =

( 0,5

0,5 ).

2. La probabilité de rester favorable au parti est 0,9 ; celle d’y
rester défavorable est 0,85.
3. P2 = P1M = P0M2
2
 0,9 0,1 
= ( 0,5 0,5 ) × 


 0,15 0, 85 
= ( 0,54375 0, 45625 )
= ( 0,54 0, 46
à 10–2 près.

)

 1 2 

56 1. M =  3 3  .

 3 1


4 4 

Chapitre 3 Graphes pondérés et probabilistes – Term ES spécialité

121