Exercices sur la théorie des graphes

Sommaire

Graphes probabilistes
Chaînes de Markov
Algorithme de Dijkstra

Pour accéder au cours sur la théorie des graphes, clique ici !

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 pn 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.

Chaînes de Markov

Haut de page

On considère la chaîne de Markov suivante :

1) Initialement on est en A.
Quelle est la probabilité d’être en A à la 3ème étape ?
2) Etudier la convergence de la chaîne de Markov.

Algorithme de Dijkstra

Haut de page

On donne le graphe suivant :

Exercice sur l'algorithme de Dijkstra

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.