Graphe probabiliste à 2 ou 3 sommets
- Fiche de cours
- Quiz
- Profs en ligne
- Videos
- Application mobile
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é
Graphe 1
► Graphe pondéré
Graphe 2
► Graphe probabiliste
► Matrice de transition
La somme des éléments de chaque ligne vaut 1.
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 P0 est donné par l’énoncé : « au départ on considère que 80 % des éléments sont dans A ». La matrice sera alors : P0 = (0,80 0,20). |
Graphe 4
|
► Matrice de transition
Pour déterminer l’état
probabiliste à l’étape n, on a
les relations : 
et 
où M est la matrice de transition.
et
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 ie ligne je
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
Pn à l’étape n tend vers
un état indépendant de l’état
initial P0 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". |
Comment as-tu trouvé ce cours ?
Évalue ce cours !
Vous avez obtenu75%de bonnes réponses !
Recevez l'intégralité des bonnes réponses ainsi que les rappels de cours associés :
Fiches de cours les plus recherchées
Mathématiques
Détermination de primitives
Mathématiques
Intervalles de fluctuation
Mathématiques
Prise de décision, estimation
Mathématiques
Suites numériques : limite finie ou infinie
Mathématiques
Suites numériques : limites et comparaison
Mathématiques
Suites numériques : opérations sur les limites
Mathématiques
Suites numériques : comportement à l'infini de (qn), avec q un réel.
Mathématiques
Suites numériques : suites majorées, minorées, bornées
Mathématiques
Calcul d'intégrales : définitions et notations
Mathématiques
Savoir utiliser la calculatrice pour le calcul d'intégrales
Fermer
Accédez gratuitement à
