Exo 1 · Facile Représenter
Écris la matrice d'adjacence du graphe orienté : 1→2, 2→3, 3→1.
Graphes et chaînes de Markov
Terminale — option · Algorithmique · BO 2019 (Maths expertes)
Graphes orientés et matrice d'adjacence, marches sur un graphe, chaînes de Markov et distribution stationnaire.
Étape 01 / 07
Avant de commencer
Question honnête : où en es-tu ?
Sais-tu ce qu'est une matrice de transition d'un système qui change d'état ?
Étape 02 / 07
Prérequis
- Calcul matriciel et produit de matrices (chapitre précédent).
- Probabilités conditionnelles et arbres.
- Suites et limites.
- Lecture d'un schéma sommets-arêtes.
Étape 03 / 07
Cours
3.1 — Graphe orienté
Un graphe est un ensemble de sommets reliés par des arêtes (ou des arcs s'il est orienté). On le code par sa matrice d'adjacence M où mᵢⱼ = 1 si un arc va du sommet i au sommet j.
3.2 — Puissances de la matrice
Le coefficient (i ; j) de Mᵏ donne le nombre de chemins de longueur k du sommet i au sommet j. C'est l'outil pour compter les trajets dans un réseau.
3.3 — Chaîne de Markov
Un système passe d'un état à l'autre avec des probabilités de transition. La matrice de transition P a des lignes dont la somme vaut 1. Si Pₙ est la distribution à l'étape n (vecteur ligne), alors Pₙ₊₁ = Pₙ × P, donc Pₙ = P₀ × Pⁿ.
3.4 — Distribution stationnaire
Une distribution stationnaire π vérifie π = π P : elle ne change plus d'une étape à l'autre. Sous de bonnes conditions, Pₙ converge vers π quel que soit l'état initial.
Erreur classique
Selon la convention (vecteur ligne ou colonne), on écrit Pₙ₊₁ = Pₙ P ou P Pₙ. Vérifier que les lignes de la matrice de transition somment à 1 avant tout calcul.
Étape 04 / 07
Exemples résolus
Ex 1 — Matrice d'adjacence
Graphe A→B, B→C, A→C : M = [[0, 1, 1], [0, 0, 1], [0, 0, 0]].
Ex 2 — Chemins de longueur 2
Le coefficient (A ; C) de M² compte les chemins A→B→C : ici 1 chemin de longueur 2.
Ex 3 — Transition
P = [[0,9 ; 0,1], [0,3 ; 0,7]] : 90 % des « abonnés » le restent, 30 % des « non-abonnés » le deviennent. P₀ = [0,5 ; 0,5] donne P₁ = [0,6 ; 0,4].
Ex 4 — Stationnaire
Pour P ci-dessus, π = (0,75 ; 0,25) vérifie π = πP : c'est la répartition d'équilibre.
Étape 05 / 07
Exercices d'application
Exo 2 · Facile Calculer
Pour la matrice de transition P = [[0,8 ; 0,2], [0,5 ; 0,5]], vérifie que chaque ligne somme à 1.
Exo 3 · Moyen Calculer
Avec P de l'exercice 2 et P₀ = [1 ; 0], calcule P₁ et P₂.
Exo 4 · Moyen Calculer
Calcule M² pour M = [[0, 1, 0], [0, 0, 1], [1, 0, 0]] et interprète un coefficient.
Exo 5 · Moyen Modéliser
Un client fidèle reste fidèle à 70 %, un client perdu revient à 20 %. Écris la matrice de transition.
Exo 6 · Moyen Raisonner
Cherche la distribution stationnaire π = (a ; 1 − a) telle que π = πP pour P = [[0,6 ; 0,4], [0,3 ; 0,7]].
Exo 7 · Défi Raisonner
Montre que toute distribution stationnaire vérifie un système linéaire et résous-le pour une P 2×2 donnée.
Exo 8 · Défi Communiquer
Explique ce que représente la convergence de Pₙ vers π dans une situation concrète (parts de marché, météo…).
Étape 06 / 07
Synthèse — À retenir
- Graphe ⟷ matrice d'adjacence M.
- Mᵏ : nombre de chemins de longueur k.
- Matrice de transition P : lignes de somme 1.
- Pₙ = P₀ × Pⁿ (avec vecteurs lignes).
- Distribution stationnaire : π = π P, limite de Pₙ.
Étape 07 / 07
Plan de révisions
J+1
Refais exos 1 et 2.
J+7
Refais exos 3 et 5.
J+30
Exos 6 et 8.
Pour aller plus loin
Q1. Pourquoi Mᵏ compte-t-elle les chemins de longueur k ?
Q2. Que signifie concrètement une distribution stationnaire ?