20 Graphe 2
20 Graphe 2
20 Graphe 2
GRAPHES (Partie 2)
I. Graphes orientés et graphes pondérés
1) Graphes orientés
Définitions : - Un graphe est orienté si ses arêtes, appelées arcs dans ce cas, ont
un sens de parcours.
- Un chemin est une succession d'arcs mis bout à bout.
- Un circuit est un chemin fermé dont les arcs sont tous distincts.
Exemple :
Le graphe orienté ci-contre est d'ordre 3 car il
possède 3 sommets.
Il possède une boucle sur le sommet A.
A – C – B est un chemin de longueur 2.
B – C – B – A – A – C – B est un chemin
fermé de longueur 6.
A – C – B – A est un circuit de longueur 3.
2) Graphes pondérés
Définitions : - Un graphe est étiqueté si ses arêtes (ou ses arcs) sont affectés
d'étiquettes (mots, lettres, symboles, nombres, …)
- Dans le cas où les étiquettes sont des nombres, le graphe est dit pondéré. Les
étiquettes sont appelées les poids entre les sommets.
- Le poids du chaîne (respectivement d'un chemin) est la somme des poids des
arêtes (respectivement des arcs) constituant la chaîne (respectivement le chemin).
Exemple :
Le graphe orienté ci-contre est pondéré.
Le poids entre le sommet B et le sommet A est
égal à 5.
Le poids du chemin B – C – B – A est égal à :
1+3+5=9
Vidéo https://youtu.be/ZEiOWcqX7S4
Remarque :
Le chemin le plus court entre deux sommets est le chemin qui a le poids minimum.
Définition : Soit un graphe 𝐺 orienté d'ordre 𝑛 dont les sommets sont numérotés de 1
à 𝑛.
La matrice d'adjacence associée à 𝐺 est la matrice carrée de taille 𝑛 dont chaque
terme 𝑎%& est égal au nombre d'arcs orientés reliant le sommet 𝑖 vers le sommet 𝑗.
Exemple :
Vidéo https://youtu.be/yRBCx3uxN9A
1) Définition
Dans une équipe de football, on étudie les passes que se font trois attaquants 𝐴, 𝐵 et
𝐶.
Les probabilités qu'un attaquant passe le ballon
à un autre sont schématisées sur le graphe
orienté et pondéré suivant. Chaque passe de
ballon correspond à une nouvelle expérience
aléatoire dont les issues sont 𝐴, 𝐵 ou 𝐶 (un des
trois attaquants est susceptible de recevoir le
ballon).
1 4
Par exemple, la somme des poids issus de 𝐴 est égal à + = 1
2 2
2) Marche aléatoire
3) Probabilité de transition
4) Matrice de transition
Vidéo https://youtu.be/KRi0C_zOsHs
Remarques :
- Le coefficient 𝑝44 de la matrice 𝑃 est nul car la probabilité que l'attaquant A garde le
ballon est nulle. Il en est de même pour les coefficients 𝑝11 et 𝑝22 .
- La somme des coefficients d'une même ligne d'une matrice de transition est égale à
1.
Exemple : Dans l'exemple des passeurs au football, la matrice ligne des états après
la 3e étape donnerait les probabilités que le ballon se trouve chez l'attaquant A, chez
l'attaquant B et chez l'attaquant C après 3 passes.
3
⎧𝑝6A4 = 0,5𝑞6 + 𝑟6
⎪ 4
2 1
𝑞6A4 = 𝑝6 + 𝑟6
⎨ 3 4
⎪ 1
⎩𝑟6A4 = 3 𝑝6 + 0,5𝑞6
Démonstration au programme :
• On note :
- 𝜋6 = (𝑝6 𝑞6 𝑟6 ) la matrice ligne des états de la chaîne de Markov après 𝑛
étapes.
- 𝐴, 𝐵 et 𝐶 les états de 𝑋6 .
𝑝6A4 = 𝑃(𝑋6A4 = 𝐴)
= 𝑃=> ?@ (𝑋6A4 = 𝐴) 𝑃(𝑋6 = 𝐴) + 𝑃=> ?e (𝑋6A4 = 𝐴) 𝑃(𝑋6 = 𝐵) + 𝑃=> ?f (𝑋6A4 = 𝐴)
𝑃(𝑋6 = 𝐶),
selon la formule des probabilités totales.
Soit : 𝑝6A4 = 𝑃=> ?@ (𝑋6A4 = 𝐴) 𝑝6 + 𝑃=> ?e (𝑋6A4 = 𝐴) 𝑞6 + 𝑃=> ?f (𝑋6A4 = 𝐴)𝑟6 .
On reconnait le premier coefficient du produit 𝜋6 × 𝑃.
On prouve de même que 𝑞6A4 et 𝑟6A4 sont respectivement le deuxième et troisième
coefficient du produit 𝜋6 × 𝑃.
• La démonstration de l’expression explicite 𝜋6 = 𝜋d × 𝑃6 est semblable à celle
faites dans le cadre des suites numériques.
Exemple :
Vidéo https://youtu.be/gxrgpotHfnE
Définition : Si la suite (𝜋6 ) des états d'une chaîne de Markov convergente vérifie
𝜋6A4 = 𝜋6 × 𝑃 alors la limite 𝜋 de cette suite définit un état stable solution de
l'équation 𝜋 = 𝜋𝑃.
0 0 1
La matrice de transition est 𝑃 = + 0,5 0 0,5 ..
0 0,5 0,5
Pour tout entier naturel 𝑛, on a : 𝜋6A4 = 𝜋6 × 𝑃, où (𝜋6 ) est la suite des matrices
lignes des états de la chaîne de Markov.
On a donc : 𝜋6 = 𝜋d × 𝑃6 avec 𝜋d = (1 0 0) car on part de A.
A l'aide de la calculatrice, calculons par exemple 𝜋4d :
On peut effectuer les calculs pour des puissances de 𝑃 de plus en plus grandes. On
constate que l'état stable semble être la matrice colonne :
1 2 4
𝜋=l m
7 7 7
Remarque :
Cette méthode ne prouve pas que la chaîne de Markov est convergente.
En supposant qu'elle l'est, elle permet seulement de déterminer l'état stable.
1−𝑝 𝑝
Alors on a : 𝑃 = l m. Et la suite des matrices lignes (𝜋6 ) des états de la
𝑞 1−𝑞
chaîne de Markov converge vers un état stable 𝜋 tel que 𝜋 = 𝜋𝑃.
𝜋 ne dépend pas de l'état initial 𝜋d .
Démonstration :
Pour tout entier naturel n, on note 𝜋6 = (𝑝6 𝑞6 ) avec 𝑝6 + 𝑞6 = 1.
Comme 𝜋6A4 = 𝜋6 × 𝑃, on a :
𝑝6A4 = 𝑝6 (1 − 𝑝) + 𝑞6 × 𝑞 = 𝑝6 (1 − 𝑝) + (1 − 𝑝6 ) × 𝑞 = 𝑝6 (1 − 𝑝 − 𝑞) + 𝑞
s
Pour tout entier naturel 𝑛, on pose : 𝑢6 = 𝑝6 − et on a :
tAs
s
𝑢6A4 = 𝑝6A4 −
tAs
s
= 𝑝6 (1 − 𝑝 − 𝑞) + 𝑞 −
tAs
s(4utus)
= 𝑝6 (1 − 𝑝 − 𝑞) −
tAs
𝑞
= (1 − 𝑝 − 𝑞) l𝑝6 − m
𝑝+𝑞
= (1 − 𝑝 − 𝑞)𝑢6
Méthode : Étudier une distribution invariante d'une chaîne de Markov sur un graphe à
deux sommets
Vidéo https://youtu.be/PS756B-M0Dw
0,4 0,6
La matrice de transition est 𝑃 = w x.
0,3 0,7
Pour tout entier naturel 𝑛, on a : 𝜋6A4 = 𝜋6 × 𝑃 où (𝜋6 ) est la suite des matrices
lignes des états de la chaîne de Markov.
L'état stable 𝜋 = (𝑝 𝑞) vérifie l'équation 𝜋 = 𝜋𝑃, soit :
0,4 0,6
(𝑝 𝑞 ) = (𝑝 𝑞 ) × w x
0,3 0,7
𝑝 = 0,4𝑝 + 0,3𝑞
Ainsi, on a le système : y
𝑞 = 0,6𝑝 + 0,7𝑞
Yvan Monka – Académie de Strasbourg – www.maths-et-tiques.fr
8
0,6𝑝 = 0,3𝑞
⟺y
0,3𝑞 = 0,6𝑝
⟺ 𝑞 = 2𝑝
4 1
Comme 𝑝 + 𝑞 = 1, on a 1 − 𝑝 = 2𝑝 et donc 𝑝 = et donc 𝑞 = .
2 2
L'état stable du graphe est donc :
1 2
𝜋=l m
3 3
Cela signifie que, quel que soit l'état initial (départ de 𝐴 ou de 𝐵), les probabilités
4 1
d'être en 𝐴 et en 𝐵 tendent respectivement vers et .
2 2
Hors du cadre de la classe, aucune reproduction, même partielle, autres que celles prévues à l'article L 122-5 du
code de la propriété intellectuelle, ne peut être faite de ce site sans l'autorisation expresse de l'auteur.
www.maths-et-tiques.fr/index.php/mentions-legales