Résumé de cours Maths expertes : graphes et chaînes de Markov

↩ Chapitre : Matrices et graphes (Maths expertes)

L’essentiel de la partie Graphes et matrices du programme de Maths expertes (programme de 2019) : vocabulaire des graphes, matrice d’adjacence, chaînes de Markov et distribution invariante.

1. Graphes

  • Un graphe est formé de sommets reliés par des arêtes (graphe non orienté) ou des arcs (graphe orienté). L’ordre est le nombre de sommets ; le degré d’un sommet est le nombre d’arêtes qui en partent.
  • Une chaîne (un chemin dans un graphe orienté) est une suite de sommets consécutifs reliés ; sa longueur est son nombre d’arêtes. Un cycle est une chaîne fermée.
  • Graphe complet : deux sommets distincts quelconques sont reliés. Graphe connexe : deux sommets quelconques sont reliés par une chaîne.

2. Matrice d’adjacence

À connaître

  • La matrice d’adjacence A d’un graphe à n sommets numérotés a pour coefficient a_{ij} le nombre d’arêtes (ou d’arcs) allant du sommet i au sommet j. Elle est symétrique pour un graphe non orienté.
  • Le coefficient (i,j) de A^k est le nombre de chaînes (ou chemins) de longueur k allant de i à j.

3. Chaînes de Markov

À connaître

  • Une chaîne de Markov sur un ensemble fini d’états est décrite par un graphe orienté pondéré par des probabilités de transition ; la somme des poids des arcs issus d’un sommet vaut 1.
  • La matrice de transition P a pour coefficient p_{ij} la probabilité de passer de l’état i à l’état j ; ses lignes ont une somme égale à 1.
  • Si \pi_n est la loi (matrice ligne) à l’étape n : \pi_{n+1}=\pi_nP et \pi_n=\pi_0P^n.
  • Une distribution invariante \pi vérifie \pi=\pi P, avec des coefficients positifs de somme 1.
  • Exemple à deux états : P=\begin{pmatrix}0{,}9&0{,}1\\0{,}3&0{,}7\end{pmatrix} ; \pi=(x\,;1-x) est invariante si 0{,}9x+0{,}3(1-x)=x, soit x=0{,}75 : \pi=(0{,}75\,;0{,}25).
  • Pour une chaîne à deux états dont la matrice de transition n’a aucun coefficient nul, la suite (\pi_n) converge vers l’unique distribution invariante, quelle que soit la loi initiale.

4. Pièges classiques

  • Avec la convention des lignes, on écrit \pi_{n+1}=\pi_nP, et non P\pi_n.
  • Le coefficient (i,j) de A^k compte des chaînes de longueur exactement k.

Pour aller plus loin

Besoin d’aide sur ce chapitre ?

Un blocage sur une notion, un contrôle à préparer ou le bac en ligne de mire : Pr. Elakili, agrégé de mathématiques depuis 1991, propose des cours particuliers aux lycéens (Première, Terminale, Maths expertes), en présentiel à Casablanca ou en ligne.

Publications similaires