Sommaire

Graphes pobabilistes
Algorithme de Dijkstra

Graphes probabilistes

Une considère une personne, elle est soit malade (événement noté M) soit saine (noté S).
La probabilité qu’une personne malade devienne saine le lendemain est de 0,3.
La probabilité qu’une personne saine devienne malade le lendemain est de 0,2.
On note p_n la probabilité qu’une personne soit malade le n-ième jour.
Initialement, la maladie touche 5% de la population.

1) Donner le graphe probabiliste associé.
2) Donner la matrice associée.
3) Quelle est la proportion de personnes malades le 5ème jour ?
4) Trouver l’état stable du système.

Algorithme de Dijkstra

Haut de page

On donne le graphe suivant :

1) Ce graphe est-il connexe ?
2) Ce graphe est-il complet ?
3) Ce graphe comporte-t-il une chaîne eulérienne ?
4) Ce graphe comporte-t-il un cycle eulérien ?
5) Utiliser l’algorithme de Dijkstra pour déterminer le plus court chemin entre les points A et G.