Terminale > Mathématiques > Graphe probabiliste à 2 ou 3 sommets

Graphe probabiliste à 2 ou 3 sommets

Fiche de cours Vidéos Quiz Profs en ligne Télécharger
le pdf

Objectif(s)

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

Il est nécessaire de connaître l’ensemble des définitions de base du cours "Graphes : définitions, propriétés". Les calculs (matrices) nécessitent une calculatrice ou un logiciel de mathématiques.

1. Définitions

► Graphe étiqueté

Un graphe étiqueté est un graphe orienté où chaque arête est étiquetée par un nombre ou un mot (un dessin…).

Graphe 1

► Graphe pondéré

Un graphe pondéré est un graphe étiqueté de nombres positifs uniquement.

Chaque nombre est appelé poids d’une arête.

Le poids d’une chaîne est la somme des poids des arêtes qui la composent.

Graphe 2

► Graphe probabiliste

Un graphe probabiliste est un graphe orienté pondéré tel que la somme des poids des arêtes issues de chaque sommet vaut 1.

L’état probabiliste d’un élément est représenté par une matrice ligne.

Graphe 3	Ci-contre un graphe probabiliste à deux sommets, puis un autre graphe probabiliste à trois sommets. Pour le graphe ci-contre à deux sommets, l’état P₀ est donné par l’énoncé : « au départ on considère que 80 % des éléments sont dans A ». La matrice sera alors : P₀ = (0,80 0,20).
Graphe 4

► Matrice de transition

Pour déterminer l’état probabiliste à l’étape n, on a les relations :

où M est la matrice de transition.

La matrice de transition d’un graphe probabiliste à n sommets est une matrice carrée d’ordre n, pour laquelle chaque coefficient de la i^e ligne j^e colonne est le poids de l’arête orientée de i vers j si cette arête existe, 0 sinon.

Matrice pour le graphe 3

Matrice pour le graphe 4

La somme des éléments de chaque ligne vaut 1.

2. État stable

Pour tout graphe probabiliste dont la matrice de transition ne comporte pas de 0, l’état P_n à l’étape n tend vers un état indépendant de l’état initial P₀ quand n devient grand.

À l’état stable, on a : P = P × M où P est l’état stable.

Par exemple, avec les conditions indiquées pour le graphe à deux sommets, en posant :
P = (x ; y) avec x + y = 1 soit y = 1- x.

Nous avons :

Ce qui donne un système de trois équations à deux inconnues :

En reportant (3) dans (1) on obtient :
x - 0,25x = 0,19(1 - x)
0,75x = 0,19 - 0,19x
0,94x = 0,19

D’où :

, on en déduit :

3. Calculs et utilisation d'une calculatrice

On utilise la calculatrice pour le calcul de puissances de la matrice.

Calcul de :	TI 82 stats (ou 83-84)	Casio Graph 35+	TI-Nspire
Résultat :	• Dans le menu "matrice", "edit", choisir A par exemple, donner la dimension 2×2. • Valider, remplir la matrice. • Choisir de nouveau le menu matrice, appuyer sur "Entrer". • Puis touches ^2. • Valider.	• Menu "Mat" puis sur un nom de matrice flèche droite donner les dimensions, valider. • Remplir la matrice. • Menu "Run", puis touche "OPTN", F2 MAT s’affiche, touche "ALPHA" A puis ^2. • Valider.	• Appuyer sur menu, choix 7 matrices et vecteurs, "créer" donner les dimensions, valider. • Remplir la matrice puis ^2 et "entrée".