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



Nom original: Chapitre 3 - Graphes pondérés et probabilistes.pdf

Ce document au format PDF 1.6 a été généré par Adobe InDesign CS4 (6.0.6) / Adobe PDF Library 9.0, et a été envoyé sur fichier-pdf.fr le 26/04/2015 à 15:09, depuis l'adresse IP 105.103.x.x. La présente page de téléchargement du fichier a été vue 5575 fois.
Taille du document: 2.5 Mo (12 pages).
Confidentialité: fichier public


Aperçu du document


chapitre

3

Graphes pondérés
et probabilistes

A Le programme
L’enseignement de spécialité prend appui sur la résolution de problèmes. (…)
Les graphes probabilistes permettent d’étudier des phénomènes d’évolution simples et de faire un lien avec les suites. (…)
Exemples de problèmes

Contenus

Codage par un graphe étiqueté, applications à l’accès à un réseau
informatique, reconnaissance de codes.
Minimisation d’une grandeur (coût, longueur,
durée, etc.).
Phénomènes évolutifs (variation d’une population, propagation
d’une rumeur ou d’un virus, etc.).

Recherche du plus court chemin sur un graphe pondéré
connexe.

Graphe probabiliste à deux ou trois sommets : matrice de
transition, état stable d’un graphe probabiliste.

B Notre point de vue
Ce chapitre est également axé sur la résolution de problèmes. Il s’articule en deux séquences.
La première partie, consacrée aux graphes pondérés est composée de deux problèmes permettant d’introduire les
graphes étiquetés, puis les graphes pondérés :
Avec un ordinateur traite tout ce qui est autour de la reconnaissance de codes, avec un approfondissement sur les
automates ;
Itinéraire routier a pour objectifs principaux la découverte des graphes pondérés, la notion de plus courte chaîne et
la mise en œuvre de l’algorithme de Dijkstra.
La seconde partie est dédiée aux graphes probabilistes : L’allumeur de réverbères est un problème dont l’objectif est
l’introduction d’un graphe probabiliste et de sa matrice de transition, mais aussi l’utilisation de la calculatrice pour
conjecturer l’existence d’un état stable. Transferts de population est un problème classique de graphe probabiliste à
deux états, où on calcule un état stable en résolvant l’équation P = PM.
Ce chapitre fait la part belle à l’algorithmique avec l’algorithme de Dijkstra (souvent présenté sous forme de tableau).
La calculatrice y est également indispensable afin de calculer rapidement des états probabilistes à un rang donné.
Les travaux pratiques sont quant à eux consacrés à l’algorithme PageRank et à l’utilisation du tableur pour réaliser des
simulations de marches sur un graphe probabiliste à deux états et, plus précisément, pour évaluer des temps d’attente
de retour à un état donné.

  Les notions abordées dans le chapitre 3  
1. Graphes étiquetés et pondérés
2. Graphes probabilistes

C Avant de commencer
Voir livre page 95 et le site www.bordas-indice.fr pour les corrigés détaillés.
Chapitre 3 Graphes pondérés et probabilistes – Term ES spécialité

117

D Problèmes
L’objectif de ce problème est de découvrir et d’utiliser les graphes
étiquetés, spécialement dans le but de reconnaître des codes. Ce
problème se divise en deux parties, la première étant proposée
pour acquérir les compétences du programme, la seconde
constituant un élargissement de ce domaine.
Partie A. Reconnaissance de codes
sur un écran informatique
1. Oui.
2. Il y en a 6 : DACF, DECF, DCIF, DBIF, DEBF et DABF.

3. M = 


0
0
0
0

1
2
0
0

0
2
1
0

2 Itinéraire routier

Les objectifs de ce problème sont de découvrir les graphes
pondérés, la notion de plus courte chaîne et aussi l’algorithme de
Dijkstra. La fin du problème constitue une première application
de cet algorithme.
Lettre autre que M

M

Mâcon

Roanne

125

73

86

Lyon

Clermont-Ferrand

63

147

Saint-Étienne

Moulins

107
94

79
Clermont-Ferrand
88

Mâcon

Roanne

52

86

Lyon
48

Saint-Étienne
2. En observant le second graphe, Camille va choisir Lyon –
Mâcon – Moulins.
3. En observant le premier graphe, Camille va choisir Moulins –
Roanne – Lyon.
4. Sylvain fera un kilomètre de moins en passant par SaintEtienne, et mettra surtout 29 minutes de moins en choisissant
cet itinéraire !
Il choisira donc Clermont-Ferrand – Saint-Étienne – Lyon.
5. On a la liste suivante : Clermont-Ferrand (210), Mâcon (73)
et Roanne (86).
Depuis Mâcon, Moulins seule est accessible. On obtient  :
Clermont-Ferrand (210), Moulins (214) et Roanne (86).
Reprenons le raisonnement depuis Roanne. Clermont-Ferrand
est une ville adjacente, mais avec 125 kilomètres, ce qui fait un
total de 211, ce qui est moins intéressant que précédemment.
Moulins est accessible avec 98 km, donc un total de 184 km.
On obtient donc : Moulins (184), Clermont-Ferrand (210).
Enfin, depuis Clermont-Ferrand, Moulins est accessible mais
avec bien trop de kilomètres.
On trouve ainsi le chemin le plus court reliant Lyon à Mâcon.

M

M

A

M

MA

Lettre autre que M ou A
Lettre autre que M
Lettre autre que A ou M
Lettre autre que M ou N

118

98

103

83

 0 1 0 0
 0 34 21 8 
5 = 8.
M =  0 2 1 0  ; M5 =  0 89 55 21  donc M1,4
0 1 1 1
0 55 34 13




0 0 0 0
0 0 0 0
Il y a donc 8 chemins de longueur 5 reliant le premier au dernier
sommet.
Partie B. Recherche d’un mot dans un texte
Voir schéma en bas de page. Cet automate reconnaît le mot
« MAMAN » dans un texte quelconque composé de caractères
parmi les lettres de l’alphabet.

Départ

141

0
0
1

0

 0 16 30 14 
5 = 14.
4. M5 =  0 32 62 30  donc M1,4
0 0 1 1


0 0 0 0
Il y a donc 14 chemins de longueur 5 reliant le premier au
dernier sommet.
5. DECIF est reconnu mais pas DAAEEBIIF.
Il y a trois mots de longueur 4 : DACF, DECF et DCIF.

Problème

Moulins

1.

1 Avec un ordinateur

Problème

M

A
MAM

MAMA
M

N

MAMAN

Problème

1.

3 L’allumeur de réverbères

L’objectif de ce problème est d’introduire la notion de graphe
probabiliste et aussi de matrice de transition d’un graphe
probabiliste. En fin de problème, on donne l’intuition de l’existence
possible d’un état stable.
1.
Jour 0
Jour 1
Jour 2
0,25 A
A

0,75
E
0,25

0,75

B

0,75

A
B

E

 0, 484375 0,515625 
5. M5 = 
 0,515625 0, 484375 
 0,5005 0, 4995 
M10 ≈ 
à 10–4 près.
 0, 4995 0,5005 

( 0,3875

0, 6125 )

=

On conjecture une stabilisation de l’état probabiliste autour
de P = ( 0, 8 0,2 ) .

 0,5 0,5 
≈ 
à 10–4 près.
 0,5 0,5 

6. Sur un grand nombre de jours, le réverbère est allumé un
jour sur deux en moyenne.

Problème

P0M2
P0M5

4. Le coefficient à l’intersection de la première ligne et de la
première colonne est la probabilité de passer de l’état A à l’état
A, celui à l’intersection de la première ligne et de la deuxième
colonne est la probabilité de passer de l’état A à l’état E, etc.

M15

Y

( 0, 490625 0,509375 )
P5 =
≈ ( 0, 67 0,33 )
P10 = P0M10 ≈ ( 0,77 0,23 )
7. P1 = P0M = ( 0, 45 0,55 )
P2 = P0M2 = ( 0,5375 0, 4625 )
P5 = P0M5 ≈ ( 0, 69 0,31 )
P10 = P0M10 ≈ ( 0,77 0,23 )
puis : P1 = P0M = ( 0,7 0,3 )
P2 = P0M2 = ( 0,725 0,275 )
P5 = P0M5 ≈ ( 0,768 0,232 )
P10 = P0M10 ≈ ( 0,79 0,21 )
P2 =

0,75

0,20

 0,95 0, 05 
2. M = 
 
 0,2 0, 8 
3. Pn+1 = PnM
4. Pn = P0Mn

6. P1 = P0M =

2. P (A) = 0,25 × 0,75 + 0,75 × 0,25 = 0,375
3.
0,75
0,25
A
0,25

0,95

0,80

5. P0 =  1 3 
 4 4 

E
0,25

0,05

X

4 Transferts de population

L’objectif de ce problème est de réaliser un calcul d’état stable
d’un graphe probabiliste via un système, et également d’utiliser
la calculatrice pour des calculs d’états probabilistes.

8. Soit P = ( a b ) avec a + b = 1.
P = PM équivaut à :

⎧ 0,95a + 0,2b = a
⎨ 0,05a + 0,8b = b ⇔ 0,05a = 0,2b ⇔ a = 4b .

Par substitution, a = 4 et b = 1 .
5
5
Ce sont les valeurs vers lesquelles l’état probabiliste semble
tendre.

E Exercices
POUR DÉMARrER
1   1. Il y a une unique arête d’origine le sommet vert et
d’extrémité le sommet rouge. Cette arête est étiquetée d’un Y.
Y est donc le seul mot reconnu par le graphe.
2. En partant du sommet vert, puis en empruntant deux fois la
boucle étiquetée d’un X et en finissant par l’arête étiquetée Y
arrivant au sommet rouge, on crée une chaîne montrant que
le mot XXY est reconnu.
3. Les mots reconnus par ce graphe sont constituées d’un
nombre quelconque de X (éventuellement nul) suivis d’un Y.

2   1. La chaîne CAT est bien une chaîne du graphe, partant
du sommet vert et aboutissant au sommet rouge : ce mot est
reconnu par le graphe.
2. HAT n’est pas une chaîne orientée du graphe, et ne peut
donc pas être un mot reconnu par ce graphe.
3   Voir livre page 95.
4   Voir livre page 95.
5   1. La chaîne de poids minimal reliant A à E est ABE pour
un poids total de 4.
2. AECDE est la chaîne de poids maximal reliant A à E et ne
comportant que des arêtes distinctes avec un poids de 12.

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

119

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 :

 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

2. La matrice M ne comportant pas de zéro, il existe un état
stable et il est unique.
Soit P = ( a b ) l’état stable.
On sait que a + b = 1, d’autre part P = PM équivaut à :
⎧ 1a + 3 b = a
⎪3
4
⇔ 2a = 3b ⇔ b = 8a.
⎨2
3
4
9
⎪ a + 1b = b
4
⎩3
Par substitution, a = 9 et b = 8 .
17
17
L’état stable est P =  9 8  .
 17 17 
58 1.
1
4
2
5
A
1
2

B

1
5

 1 1
2. M =  2 2 
1 4


5 5 

3. P1 = P0 M = ( 1 0 ) × 



1
2
1
5

1
2
4
5

0 3
4
3 0
4
0 1

b. On a P6 = ( 0,28745 0,71255 ) donc la probabilité que
Madame Z convainque son sixième client est de 0,28745.
c. Si elle n’a pas convaincu son premier client, l’état initial est
P1 = ( 0 1 ) et P6 = P1 × M5 = ( 0,28502 0,71498 ). Dans ce
cas, la probabilité qu’elle convainque son sixième client est
0,28502.
5. La matrice M ne comportant pas de zéro, il existe un état
stable et il est unique.
Soit P = ( a b ) l’état stable.
On sait que a + b = 1, d’autre part P = PM équivaut à :
⎧ 1a + 1b = a
⎪ 2
5
⇔ 1a = 1b ⇔ a = 2 b.
⎨ 1
2
5
5
4b = b
a
+

5
⎩2
Par substitution, a = 2 et b = 5 . L’état stable est P =  2 5  .
7
7
 7 7
En considérant un grand nombre de clients, Mme Z arrive à en
convaincre environ deux sur sept.
59 Voir livre page 95.
60 1.
3
4
A
B

1
4
1
4
0



 .


5

 0 3 1

4 4 
3. P5 = P0 M5 = ( 1 0 0 ) ×  3
1
 4 0 4 


0 1 0 
= ( 0,259 0,542 0,199 ) .
à 10–3 près.
La probabilité que Boris ait la balle après le cinquième lancer
est d’environ 0,542.
4. On peut s’assurer que la puissance quatrième de la matrice
de transition de ce graphe probabiliste ne comporte pas de 0,
ce qui garantit l’existence et l’unicité de l’état stable.
Soit P = ( a b c ) l’état stable.
On sait que a + b + c = 1, d’autre part P = PM équivaut à :









 =  1 1 .
  2 2


 0,28745 0,71255 
4. a. M5 = 
 0,28502 0,71498 

3b = a
4
⎧ a = 3b
4 .
3a+c = b ⇔ ⎪

4
⎪c= 7 b
16
1a + 1b = c

4
4

Par substitution, a = 12 , b = 16 et c = 7 .
35
35
35
L’état stable est P =  12 16 7  .
 35 35 35 
En considérant un grand nombre de passes, Alexis a la balle 12
fois sur 35 environ, Boris 16 fois sur 35 et Camille 7 fois sur 35.
61 1. P1 =

2.

( 0,15

0, 85 )
0,35

G
0,65

0,33

0,67
_
G

 0, 65 0,35 
3. M = 
 0,33 0, 67 
4. P3 = P2M = P1M2 = ( 0, 45096 0,54904 ) .donc environ 45 %
des personnes seront favorables à la grève le troisième jour.
5. La matrice M ne comportant pas de zéro, il existe un état
stable et il est unique.
Soit P = ( a b ) l’état stable.
On sait que a + b = 1, d’autre part P = PM équivaut à :
⎧ 0,65a + 0,33b = a
33
⎨ 0,35a + 0,67b = b ⇔ 35a = 33b ⇔ a = 35 b .

Par substitution, a = 35 et b = 33 .
68
68

3
4
1
4

1
4
C

122



2. M = 



1

L’état stable est P =  35 33  .
 68 68 
62 Faux : ce n’est même pas un graphe probabiliste !
63 Vrai : on justifie à l’aide de la calculatrice par exemple.
64 La chaîne correspondante est K – F – H – M – B avec un
poids total de 2208.

65 1.

0,1

A

B

0,3

0,5

0,3
0,2

0,2

0,6

0,6
C

0,2

2. Se vérifie à la main ou à la calculatrice.

pour FAIRE LE POINT
Voir livre page 95.
Les corrigés détaillés sont disponibles sur le site www.bordasindice.fr.

Travaux pratiques
TP

1 Moteur de recherche sur le Web

L’objectif de ce TP est de découvrir l’algorithme PageRank utilisé
par Google au travers d’un modèle réduit simple du Web.
On y utilise les matrices de transition de graphes probabilistes, en
cheminant de manière aléatoire sur un graphe.
A. Un modèle réduit du Web
1. Le déplacement étant aléatoire, supposé équiprobable :
1
3
A
B
1

1
3

1
3

3.

0,378
0,370
0,366
0,382

 0,375
 0,375
M20 ≈ 
0,375

 0,375

1 1
3 3
0 0 .

0 1
2
0 0

0,311
0,315
0,315
0,310

0,312
0,313
0,313
0,312

E

0,123
0,127
0,131
0,120

0,125
0,125
0,125
0,125

0,188 
0,188 
0,188 

0,188 

0,188 
0,187 
0,187 

0,188 

1

D
1
3

D

0 1
3
1 0
1 0
2
0 1

1
3

1
3
C

C



≈



1
3

1

1
2

M10

1
1
3

1
2




2. On a M = 




 0,375 0,313 0,125 0,187 
 0,375 0,313 0,125 0,187 
M80 ≈ 
0,375 0,313 0,125 0,187 


 0,375 0,313 0,125 0,187 
La dernière colonne a été ajustée en termes d’arrondis pour
que les matrices restent des matrices de transition.
On constate qu’il y a stabilisation à partir d’un certain rang.
4. P20 = P0M20 = ( 0,375 0,312 0,125 0,188 )
Il s’agit de la première ligne de la matrice de transition M20.
En partant de B, on obtient la seconde ligne de la matrice de
transition M20, en partant de C la troisième, de D la quatrième.
⎧ y + 1z = x

2
⎧ x = 3z
⎪ 1
⎪⎪
x
+
t=y
5
⎪ 3
⇔ ⎨ y = 2z
5. P = PM ⇔ ⎨
1
x=z
⎪ t = 3z

⎪⎩
⎪ 3
2
1
1
⎪ x+ z =t
2
3

or x + y + z + t = 1 car on parle d’un état probabiliste ; donc par
substitution, z = 1 , x = 3 , y = 5 et t = 3 .
8
8
16
16
Donc P =  3 5 1 3  .
 8 16 8 16 
L’internaute naviguant au hasard sur un grand nombre de
pages a environ 3 chances sur 8 d’être sur la page A, 5 sur 16
d’être sur la page B, 1 sur 8 d’être en C et 3 sur 16 d’être en D.
B. Évolution du modèle
1. L’internaute va être coincé en E.
2.
1
3
A
B

1

 0 1 1 1 0


3 3 3
 1 0 0 0 0
M1 =  1
1 1
 3 0 0 3 3


 0 1 0 0 0
 0 0 0 0 1
3. Les coefficients des quatre premières colonnes tendent vers
0 alors que ceux de la dernière colonne tendent vers 1 : il est
donc de plus en plus probable de rester coincé sur la page E,
ne disposant pas de lien extérieur.
Chapitre 3 Graphes pondérés et probabilistes – Term ES spécialité

123

4. a. On retrouve la matrice précédente.
b. On passe au hasard d’une page à l’autre.
C. PageRank sur la toile de la partie A
1. On obtient :
 1 1
 0 1 1 1
 4 4
 1 1

3 3 3



M = 0, 85  1 0 0 0  + 0,15 ×  4 4
1 0 0 1
 1 1

2 
 4 4
 2
 0 1 0 0
 1 1
 4 4
2. On «  gomme  » les différences constatées
rapprocher les probabilités de chaque page de

TP

c. J2 =MAX(CZ6 : CZ1006)

1 1
4 4 
1 1
4 4 
1 1 
4 4 
1 1
4 4 
en faisant se
1.
4

2 Temps de retour… du beau temps

L’objectif de ce TP est l’utilisation du tableur pour déterminer le
temps de retour à un état donné sur un graphe probabiliste à
deux états. La partie A est théorique, la partie B met en œuvre une
modélisation via un tableur.
Fichiers associés sur www.bordas-indice.fr et sur le manuel
numérique premium :
03_TESspe_TP2.ods (fichier élève OpenOffice), 03_TESspe_
TP2.xls (fichier élève Excel 2003), 03_TESspe_TP2.xlsx
(fichier élève Excel 2007), 03_TESspe_correctionTP2.ods
(fichier correction OpenOffice), 03_TESspe_correctionTP2.
xls (fichier correction Excel 2003) et 03_TESspe_
correctionTP2.xlsx (fichier correction Excel 2007).
A. Quelques temps d’attente
1.

a

A
1–a

b

1–b
B

2. M =  1 − a a 
 b 1− b 
3. a. C’est être en A et y revenir : on parle des chaînes de
longueur 1 reliant A à A, précisément la boucle en A.
b. P (T = 1) = 1 – a.
4. a. C’est être en A et y revenir avec une chaîne de longueur 2
reliant A à A. Il y en a deux : A – A – A et A – B – A.
b. En calculant le premier terme diagonal de M 2, on trouve
P (T = 2) = (1 – a)2 + ab.
B. Météorologie avec le tableur
1. La colonne B représente l’état initial, celui auquel on cherche
à revenir ensuite.
2. a. Cette formule simule une marche sur le graphe probabiliste
à deux états de la partie A : s’il pleut (un 0 en B6) alors il y a une
probabilité de 0,9 qu’il pleuve à nouveau : ENT(ALEA()+0,1)
qui donne 0 dans 90 % des cas. Sinon (un 1 en B6), il fait beau
et il fera beau à nouveau avec une probabilité égale à 0,5 et
la formule ENT(ALEA()+0,5) retourne bien un 1 dans 50 %
des cas.
3. a. =EQUIV(1;C6 : CX6;0)
b. J1 =MOYENNE(CZ6 : CZ1006)

124

et J2 =MIN(CZ6 : CZ1006)  .
d. On attend 5 à 6 jours en moyenne avant le retour du beau
temps.
4. Il suffit de changer le contenu de B1 par un 0.

Pour aller plus loin
73 La situation peut être modélisée par le graphe suivant, un
mot reconnu par le graphe étant un digicode possible.
9
5
3
7

La matrice d’adjacence de ce graphe est M =  2 1  .
 0 1
Pour connaître le nombre de codes de 4 chiffres, il nous faut
4 . Or M4 =  16 15  . Il y a donc 15 codes possibles
trouver M1,2


0 1 
et pas 16 : le souhait du propriétaire n’est pas réalisable.
74 1. À l’aide de l’algorithme de Dijkstra, on trouve que le plus
court chemin est E – A – B – C – S avec un temps de parcours
de 19 heures.
2. a. E – A – B – C – D – S avec 22 heures.
b. E – A – B – D – S avec 20 heures.
75 Partie A
1. P (A B) = 3 × 1 = 3 (indépendance)
4 2 8
2. P (« Au moins un feu est vert ») = 1
P (« Aucun n’est vert ») = 1 − 1 × 1 = 7
4 2 8
Partie B

1.

0,45

R

V

0,05

0,5
0,1

0,05

0,05
O

0,1

 0,9 0, 05 0, 05 
M =  0, 8 0,1 0,1  .
 0, 45 0, 05 0,5 
2. P1 = ( 1 0 0

)

P2 = P1M



0,9

 0,9 0, 05 0, 05 
= ( 1 0 0 ) ×  0, 8 0,1 0,1 
 0, 45 0, 05 0,5 
= ( 0,9 0, 05 0, 05 )

0,8

3. P4 = P1M3

3

 0,9 0, 05 0, 05 
= ( 1 0 0 ) ×  0, 8 0,1 0,1 
 0, 45 0, 05 0,5 
= ( 0, 861 0, 052625 0, 086375 )

donc la probabilité que le quatrième feu soit vert est 0,861.
4. P1 = ( 0 0 1 )
 0,9 0, 05 0, 05 
P2 = P1M = ( 0 0 1 ) ×  0, 8 0,1 0,1 
 0, 45 0, 05 0,5 
= ( 0, 45 0, 05 0,5 )

5. En considérant un grand nombre de feux, environ 85 % sont
verts, 5 % oranges et 10 % rouges.
76 1.
0,3
0,95
A
0,7

B

0,05

 0,7 0,3 
2. M = 
 0, 05 0,95 
3. En 2013 :
P2 = P0M2 = ( 0,336 0, 664 ) ≈ ( 0,34 0, 66 ) .

5. À l’aide de la calculatrice.
6. Les vols à deux escales sont représentés par les chaînes de
3 = 4. Il y a quatre vols à deux
longueur 3. On cherche donc M1,1
escales : A – B – C – A, A – C – B – A, A – C – F – A et A – F – C – A.
3 = 0 donc on ne peut relier G à lui-même en deux escales.
7. M7,7



8. M4 = 





26
22
27
16
31
19
14

22
36
31
20
29
33
13

27
31
37
24
32
30
14

16
20
24
20
18
23
6

31
29
32
18
39
23
19

19
33
30
23
23
35
8

14 
13 
14 
6 

19 
8 
11 

4 = 23 donc il y a 23 vols à trois escales reliant F à E.
M6,5
9. Oui, car il n’y a pas de 0 dans la matrice M4.
10. La chaîne correspondante est A – B – D – G avec un poids
total de 27.
78 1.
0,2
0,85
A

0,8

B

0,15

 0, 8 0,2 
2. M = 
 0,15 0, 85 

P3 = P0M3 = ( 0,2684 0,7316 ) ≈ ( 0,27 0,73 ) .
(au centième).
⎛ 0,7 0,3 ⎞
4. Pn+1 = PnM ⇔ ( an+1 bn+1 ) = ( an bn )⎜
⎝ 0,05 0,95 ⎟⎠
⇔ an+1 = 0,7an + 0,05bn
or an + bn = 1 donc bn = 1 – an et par substitution :
an+1 = 0,65an + 0,05.
un +1
5. En calculant
, on trouve 0,65. La suite (un) est donc
un
géométrique de premier terme 0, 6 − 1 = 16 et de raison 0,7.
7 35
16
× (0,7)n et ainsi :
6. On peut donc écrire un =
35
an = 16 × (0,7)n + 1.
7
35
7. lim (0,7)n = 0 donc lim an = 1 .
7
n →+
n →+
8. Il y aura toujours 14 % des salariés qui se rendront au travail
avec leur voiture personnelle.
77 1. A – B – C – E – D – G – F est une chaîne passant par tous
les sommets du graphe, chaque paire de sommets peut donc
être reliée par une chaîne : le graphe est connexe.
2.
A
B
C
D
E
F
G

3. a. P1 = P0M = ( 0, 4425 0,5575 ) donc la probabilité qu’un
touriste choisisse la société « Alizés » en 2013 est de 0,4425.
b. P2 = P0M2 = ( 0, 437625 0,562375 )
En 2014, environ 44 % des touristes choisiront la société Alizés
contre 56 % pour Bonair.
4. a. La matrice M ne comportant pas de zéro, il existe un état
stable et il est unique.
Soit P = ( a b ) l’état stable.
On sait que a + b = 1, d’autre part P = PM équivaut à :

3. D’après le théorème d’Euler, ce graphe connexe ayant
exactement deux sommets de degré impair (A et D), ce graphe
admet une chaîne eulérienne reliant A à D.
La réponse est donc oui.
4. En considérant les sommets dans l’ordre alphabétique :
 0 1 1 0 0 1 0
 1 0 1 1 1 0 0
 1 1 0 0 1 1 0
M= 0 1 0 0 1 0 1


 0 1 1 1 0 1 0
 1 0 1 0 1 0 1
 0 0 0 1 0 1 0

C ap vers le bac

3

4

4

3

4

4

⎧ 0,8a + 0,15b = a
3
⎨ 0,2a + 0,85b = b ⇔ 0,2a = 0,15b ⇔ a = 4 b.

Par substitution, a = 3 et b = 4 .
7
7
L’état stable est P =  3 4  .
 7 7 
b. lim an = 3 donc au bout d’un grand nombre d’années, 3
7
n →+
touristes sur 7 environ choisiront la société Alizés.
5. P (« Au moins un touriste choisit Alizés ») = 1
4
P (« Aucun ne choisit Alizés ») = 1 − 4 ≈ 0, 893.
7

()

2

Sujet

A

 0 0 0 0 1 0
 1 0 0 0 0 1


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


 0 0 0 1 0 0
 1 1 1 0 0 0
2. À l’aide de la calculatrice.
6 = 8 : il y a donc 8 chemins de longueur 6 reliant A à A.
3. a. M1,1

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

125

b. A – E – D – A – E – D – A
A–E–D–C–D–F–A
A–E–D–F–C–D–A
A–E–D–F–C–F–A
A–E–D–F–B–F–A
A–E–D–C–B–F–A
A–E–D–C–F–B–A
A–E–D–F–C–B–A
c. A – E – D – C – B – F – A : poids de 28.
A – E – D – C – F – B – A : poids de 21.
A – E – D – F – C – B – A : poids de 28.
Il s’agit de A – E – D – F – C – B – A.
d. L’itinéraire le plus judicieux pour lui est :
A – E – D – F – C – B – A.
4. Via l’algorithme de Dijkstra : C – D – F – B – A avec un poids
total de 10 minutes.

Sujet

B

1. Via l’algorithme de Dijkstra : A – E – D – F – G avec un poids
total de 12.
2. a. Soit A l’événement : « Géraud a livré le courrier du jour »
et B l’événement contraire.
0,3
0,8
A
0,7

B

0,2

 0,7 0,3 
M=
 0,2 0, 8 
⎛ 0,7 0,3 ⎞
b. Pn+1 = PnM ⇔ ( an+1 bn+1 ) = ( an bn )⎜
⎝ 0,2 0,8 ⎟⎠
⇔ an+1 = 0,7an + 0,2bn
or an + bn = 1 donc bn = 1 – an et par substitution :
an+1 = 0,5an + 0,2.
un +1
, on trouve 0,5. La suite (un) est donc
c. En calculant
un
géométrique de premier terme 1 – 0,4 = 0,6 et de raison 0,5.
d. On peut donc écrire un = 0,6 × (0,5)n–1 et ainsi :
an = 0,6 × (0,5)n–1 + 0,4.

Sujet
1. a.

C
P
0,9

0,1

0,2
D’où la matrice de transition proposée.

0,8
L

 0,9 0,1 
b. P1 = P0 M = ( 0,5 0,5 ) × 
 0,2 0, 8 
= ( 0,55 0, 45 ) .
c. La matrice M ne comportant pas de zéro, il existe un état
stable et il est unique.
Soit P = ( a b ) l’état stable.

126

On sait que a + b = 1, d’autre part P = PM équivaut à :
⎧ 0,9a + 0,2b = a
⎨ 0,1a + 0,8b = b ⇔ 0,1a = 0,2b ⇔ a = 2b.

Par substitution a = 2 et b = 1 .
3
3


2
1
L’état stable est P =
.
 3 3
Il va donc y avoir une stabilisation de la population : il y aura
toujours deux tiers environ de propriétaires.
⎛ 0,9 0,1 ⎞
2. Pn+1 = PnM ⇔ ( pn+1 ln+1 ) = ( pn ln )⎜
⎝ 0,2 0,8 ⎠⎟
⇔ pn+1 = 0,9pn + 0,2In
or pn + In = 1 donc In = 1 – pn et par substitution :
pn+1 = 0,7pn + 0,2.
un +1
, on trouve 0,7. La suite (un) est donc
un
géométrique de premier terme 0,5 − 2 = − 1 et de raison 0,7.
3
6
b. On peut donc écrire un = − 1 × (0,7)n et ainsi :
6
pn = − 1 × (0,7)n + 2 .
3
6
lim (0,7)n = 0 donc lim pn = 2 .
3
n →+
n →+
3. a. En calculant

Sujet

D

1. Réponse A.
2. Réponse A.
3. Réponse B.
4. Réponse C.

 0,1 0,9 
5. P3 = P1M2 = ( 0, 65 0,35 ) × 
 0, 6 0, 4 
= ( 0, 4625 0,5375 )
Réponse B.
6. Réponse A, à l’aide de la calculatrice.

2

79 Via l’algorithme de Dijkstra : A – C – E – H – F avec un
poids total de 1200.

 5 1

80 1. M =  6 6  .

 1 2 


3 3
2. La matrice M ne comportant pas de zéro, il existe un état
stable et il est unique.
Soit P = ( a b ) l’état stable.
On sait que a + b = 1, d’autre part P = PM équivaut à :
⎧ 0,9a + 0,2b = a
⎨ 0,1a + 0,8b = b ⇔ 0,1a = 0,2b ⇔ a = 2b.

Par substitution a = 2 et b = 1 .
3
3


2
1
.
L’état stable est P =
 3 3
En considérant un grand nombre de jours, deux jours sur trois
environ seront des jours de temps sec.


Chapitre 3 - Graphes pondérés et probabilistes.pdf - page 1/12
 
Chapitre 3 - Graphes pondérés et probabilistes.pdf - page 2/12
Chapitre 3 - Graphes pondérés et probabilistes.pdf - page 3/12
Chapitre 3 - Graphes pondérés et probabilistes.pdf - page 4/12
Chapitre 3 - Graphes pondérés et probabilistes.pdf - page 5/12
Chapitre 3 - Graphes pondérés et probabilistes.pdf - page 6/12
 




Télécharger le fichier (PDF)


Chapitre 3 - Graphes pondérés et probabilistes.pdf (PDF, 2.5 Mo)

Télécharger
Formats alternatifs: ZIP



Documents similaires


chapitre 3 graphes ponderes et probabilistes
theorie des graphes
fiches revision spe tes1 et tes2 bac 2011
4 eg ds3 1516 sm
theorie de graphe
chapitre 2 problemes de graphes

Sur le même sujet..