Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

Graphes et chaînes de Markov

Imprimer le thème

Toutes les leçons du thème, de la première année à la dernière, prêtes pour le papier. Les séries d'exercices sont notées A, B, C… et corrigées à la fin.

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

1. Graphes : sommets, arêtes, degré, chaînes

Découvrir

Un graphe a 4 sommets, tous reliés deux à deux. Combien a-t-il d'arêtes ?

  1. 6
  2. 4

L'idée clé

Un graphe modélise des relations.

Figure non à l'échelle

Un graphe est formé de sommets reliés par des arêtes. Son ordre est son nombre de sommets. Le degré d'un sommet est le nombre d'arêtes qui en partent.

Une chaîne est une suite d'arêtes consécutives ; sa longueur est son nombre d'arêtes. Un graphe est connexe si deux sommets sont toujours reliés par une chaîne. La somme des degrés est le double du nombre d'arêtes.

Exemple corrigé

Un graphe a les degrés 3, 3, 2, 2. Combien a-t-il d'arêtes ?

3+3+2+2=103 + 3 + 2 + 2 = 10
Somme des degrés.
55 arêtes
Double du nombre d'arêtes.

À toi, guidé

À toi : combien d'arêtes a le graphe complet à 3 sommets ?

33
3 × 2 / 2.

Entraînement ★

  1. Combien d'arêtes le graphe complet d'ordre 3 a-t-il ?
  2. Combien d'arêtes le graphe complet d'ordre 23 a-t-il ?
  3. Combien d'arêtes le graphe complet d'ordre 5 a-t-il ?

Attention !

Entraînement ★★

  1. Un graphe a 3 arêtes. Quelle est la somme des degrés de ses sommets ?
  2. Un graphe a 73 arêtes. Quelle est la somme des degrés de ses sommets ?
  1. Dans un graphe complet d'ordre 5, quel est le degré de chaque sommet ?
  1. La somme des degrés d'un graphe vaut 8. Combien a-t-il d'arêtes ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Combien d'arêtes le graphe complet d'ordre 3 a-t-il ?
  2. Combien d'arêtes le graphe complet d'ordre 23 a-t-il ?
  3. Combien d'arêtes le graphe complet d'ordre 5 a-t-il ?

Fiche résumé

Graphes

  • Ordre : nombre de sommets.
  • Somme des degrés = 2 × nombre d'arêtes.

Attention : une chaîne se mesure en arêtes.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Un graphe a 6 sommets, tous de degré 3. Combien a-t-il d'arêtes ?

2. Matrice d'adjacence et nombre de chemins

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Combien d'arêtes le graphe complet d'ordre 3 a-t-il ?
  2. Un graphe a 3 arêtes. Quelle est la somme des degrés de ses sommets ?
  3. Dans un graphe complet d'ordre 5, quel est le degré de chaque sommet ?

Découvrir

AA est la matrice d'adjacence d'un graphe. Que signifie aij=1a_{ij} = 1 ?

  1. Il y a une arête de ii vers jj
  2. Le sommet ii a pour degré 1

L'idée clé

Les puissances de AA comptent les chemins.

La matrice d'adjacence AA a pour coefficient aij=1a_{ij} = 1 s'il existe une arête de ii vers jj, 0 sinon.

Le coefficient (i;j)(i ; j) de AnA^n est le nombre de chemins de longueur nn reliant ii à jj.

Exemple corrigé

A=(0111)A = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}. Combien de chemins de longueur 2 vont de 2 à 2 ?

A2=(1112)A^2 = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix}
Calcul de A².
22 chemins
Coefficient (2 ; 2).

À toi, guidé

À toi : avec le même A2A^2, combien de chemins de longueur 2 vont de 1 à 1 ?

11
Coefficient (1 ; 1).

Entraînement ★

  1. Pour un graphe, A3=(5269)A^3 = \begin{pmatrix} 5 & 2 \\ 6 & 9 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
  2. Pour un graphe, A3=(3511)A^3 = \begin{pmatrix} 3 & 5 \\ 1 & 1 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
  3. Pour un graphe, A3=(7259)A^3 = \begin{pmatrix} 7 & 2 \\ 5 & 9 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?

Attention !

Entraînement ★★

  1. A=(0110)A = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}. Que vaut le coefficient (1;1)(1 ; 1) de A2A^2 ?
  2. A=(0120)A = \begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix}. Que vaut le coefficient (1;1)(1 ; 1) de A2A^2 ?
  1. A=(0310)A = \begin{pmatrix} 0 & 3 \\ 1 & 0 \end{pmatrix} compte les arêtes de chaque sommet vers chaque sommet. Combien d'arêtes vont du sommet 1 au sommet 2 ?
  1. La matrice d'adjacence d'un graphe non orienté est toujours :
    1. Symétrique
    2. Diagonale
    3. Inversible

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Pour un graphe, A3=(5269)A^3 = \begin{pmatrix} 5 & 2 \\ 6 & 9 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
  2. Pour un graphe, A3=(3511)A^3 = \begin{pmatrix} 3 & 5 \\ 1 & 1 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?
  3. Pour un graphe, A3=(7259)A^3 = \begin{pmatrix} 7 & 2 \\ 5 & 9 \end{pmatrix}. Combien de chemins de longueur 3 vont du sommet 1 au sommet 2 ?

Fiche résumé

Chemins

  • Coefficient (i;j)(i ; j) de AnA^n : chemins de longueur nn de ii à jj.
  • Graphe non orienté : AA est symétrique.

Attention : la puissance est la longueur.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Un graphe est un triangle (3 sommets, tous reliés). Combien de chemins de longueur 2 partent du sommet 1 et y reviennent ?

3. Chaînes de Markov

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Calcule ad−bcad - bc pour (3623)\begin{pmatrix} 3 & 6 \\ 2 & 3 \end{pmatrix}.
  2. Avec D=(3001)D = \begin{pmatrix} 3 & 0 \\ 0 & 1 \end{pmatrix}, que vaut le coefficient en haut à gauche de D2D^{ 2 } ?
  3. La matrice (3612)\begin{pmatrix} 3 & 6 \\ 1 & 2 \end{pmatrix} est-elle inversible ?
    1. Non : son déterminant est nul
    2. Oui : ses coefficients sont non nuls
    3. Oui : toute matrice carrée l'est

Découvrir

Il pleut aujourd'hui. Il pleut demain avec la probabilité 0,60{,}6. Quelle est la probabilité qu'il ne pleuve pas demain ?

  1. 0,40{,}4
  2. 0,60{,}6

L'idée clé

La probabilité de l'état suivant ne dépend que de l'état présent.

Figure non à l'échelle

La matrice de transition PP a pour coefficient pijp_{ij} la probabilité de passer de ii à jj. Chaque ligne a pour somme 1.

La distribution après nn transitions est πn=π0Pn\pi_n = \pi_0P^n. Le coefficient (i;j)(i ; j) de PnP^n est la probabilité d'aller de ii à jj en nn transitions.

Exemple corrigé

P=(0,90,10,50,5)P = \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}5 & 0{,}5 \end{pmatrix} et π0=(10)\pi_0 = \begin{pmatrix} 1 & 0 \end{pmatrix}. Calcule π1\pi_1.

π1=π0P\pi_1 = \pi_0P
Ligne × matrice.
π1=(0,90,1)\pi_1 = \begin{pmatrix} 0{,}9 & 0{,}1 \end{pmatrix}
On lit la première ligne.

À toi, guidé

À toi : dans la même chaîne, que vaut la probabilité d'être dans l'état 2 après une étape, en partant de l'état 2 ?

0,50{,}5
Coefficient (2 ; 2).

Entraînement ★

  1. Dans une chaîne à deux états, p11=810p_{11} = \dfrac{ 8 }{10}. Que vaut p12p_{12} ?
  2. Dans une chaîne à deux états, p11=610p_{11} = \dfrac{ 6 }{10}. Que vaut p12p_{12} ?
  3. Dans une chaîne à deux états, p11=710p_{11} = \dfrac{ 7 }{10}. Que vaut p12p_{12} ?

Attention !

Entraînement ★★

  1. P=(5101−5106101−610)P = \begin{pmatrix} \dfrac{ 5 }{10} & 1 - \dfrac{ 5 }{10} \\ \dfrac{ 6 }{10} & 1 - \dfrac{ 6 }{10} \end{pmatrix} et π0=(1212)\pi_0 = \begin{pmatrix} \dfrac{1}{2} & \dfrac{1}{2} \end{pmatrix}. Calcule la première coordonnée de π1\pi_1.
  2. P=(7101−7104101−410)P = \begin{pmatrix} \dfrac{ 7 }{10} & 1 - \dfrac{ 7 }{10} \\ \dfrac{ 4 }{10} & 1 - \dfrac{ 4 }{10} \end{pmatrix} et π0=(1212)\pi_0 = \begin{pmatrix} \dfrac{1}{2} & \dfrac{1}{2} \end{pmatrix}. Calcule la première coordonnée de π1\pi_1.
  1. Dans une matrice de transition à deux états, la première ligne est (810;p)\left(\dfrac{ 8 }{10} ; p\right). Que vaut pp ?
  1. Une chaîne reste dans l'état 1 avec la probabilité 510\dfrac{ 5 }{10} à chaque pas. Partant de l'état 1, quelle est la probabilité d'y rester deux fois de suite ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Dans une chaîne à deux états, p11=810p_{11} = \dfrac{ 8 }{10}. Que vaut p12p_{12} ?
  2. Dans une chaîne à deux états, p11=610p_{11} = \dfrac{ 6 }{10}. Que vaut p12p_{12} ?
  3. Dans une chaîne à deux états, p11=710p_{11} = \dfrac{ 7 }{10}. Que vaut p12p_{12} ?

Fiche résumé

Chaînes de Markov

  • πn=π0Pn\pi_n = \pi_0P^n.
  • Lignes de PP : somme 1.

Attention : lis pijp_{ij} de ii vers jj.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. P=(1−9109102101−210)P = \begin{pmatrix} 1 - \dfrac{ 9 }{10} & \dfrac{ 9 }{10} \\ \dfrac{ 2 }{10} & 1 - \dfrac{ 2 }{10} \end{pmatrix}. On part de l'état 1. Quelle est la probabilité d'être dans l'état 2 après deux étapes ?

4. Distributions invariantes

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Dans une chaîne à deux états, p11=810p_{11} = \dfrac{ 8 }{10}. Que vaut p12p_{12} ?
  2. P=(5101−5106101−610)P = \begin{pmatrix} \dfrac{ 5 }{10} & 1 - \dfrac{ 5 }{10} \\ \dfrac{ 6 }{10} & 1 - \dfrac{ 6 }{10} \end{pmatrix} et π0=(1212)\pi_0 = \begin{pmatrix} \dfrac{1}{2} & \dfrac{1}{2} \end{pmatrix}. Calcule la première coordonnée de π1\pi_1.
  3. Dans une matrice de transition à deux états, la première ligne est (810;p)\left(\dfrac{ 8 }{10} ; p\right). Que vaut pp ?

Découvrir

Une distribution π\pi vérifie πP=π\pi P = \pi. Que se passe-t-il à l'étape suivante ?

  1. La distribution ne change pas
  2. Elle double

L'idée clé

On cherche π\pi en résolvant un système.

π\pi est invariante si πP=π\pi P = \pi et si ses coefficients ont pour somme 1.

Exemple corrigé

P=(0,90,10,50,5)P = \begin{pmatrix} 0{,}9 & 0{,}1 \\ 0{,}5 & 0{,}5 \end{pmatrix}. Trouve π=(ab)\pi = \begin{pmatrix} a & b \end{pmatrix}.

0,9a+0,5b=a0{,}9a + 0{,}5b = a, donc 0,5b=0,1a0{,}5b = 0{,}1a
Première coordonnée de πP = π.
a=5ba = 5b, donc 6b=16b = 1
a + b = 1.
π=(5616)\pi = \begin{pmatrix} \dfrac{5}{6} & \dfrac{1}{6} \end{pmatrix}
Solution.

À toi, guidé

À toi : si a=3ba = 3b et a+b=1a + b = 1, que vaut bb ?

14\dfrac{1}{4}
4b = 1.

Entraînement ★

  1. On trouve a=3ba = 3b et a+b=1a + b = 1. Que vaut bb ?
  2. On trouve a=29ba = 29b et a+b=1a + b = 1. Que vaut bb ?
  3. On trouve a=2ba = 2b et a+b=1a + b = 1. Que vaut bb ?

Attention !

Entraînement ★★

  1. P=(1−9109106101−610)P = \begin{pmatrix} 1 - \dfrac{ 9 }{10} & \dfrac{ 9 }{10} \\ \dfrac{ 6 }{10} & 1 - \dfrac{ 6 }{10} \end{pmatrix}. Trouve la première coordonnée aa de la distribution invariante.
  2. P=(1−5105107101−710)P = \begin{pmatrix} 1 - \dfrac{ 5 }{10} & \dfrac{ 5 }{10} \\ \dfrac{ 7 }{10} & 1 - \dfrac{ 7 }{10} \end{pmatrix}. Trouve la première coordonnée aa de la distribution invariante.
  1. Comment vérifier qu'une distribution π\pi est invariante pour la matrice de transition PP ?
    1. On vérifie que πP=π\pi P = \pi
    2. On vérifie que Pπ=PP\pi = P
    3. On vérifie que π=1\pi = 1
  1. Une distribution sur deux états s'écrit (610;b)\left(\dfrac{ 6 }{10} ; b\right). Que vaut bb ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. On trouve a=3ba = 3b et a+b=1a + b = 1. Que vaut bb ?
  2. On trouve a=29ba = 29b et a+b=1a + b = 1. Que vaut bb ?
  3. On trouve a=2ba = 2b et a+b=1a + b = 1. Que vaut bb ?

Fiche résumé

Distribution invariante

  • πP=π\pi P = \pi.
  • Somme des coefficients : 1.

Attention : n'oublie pas la condition de somme.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Dans une chaîne à deux états, p12=15p_{12} = \dfrac{1}{ 5 } et p21=19p_{21} = \dfrac{1}{ 9 }. Quelle est la seconde coordonnée de la distribution invariante ?

5. La distribution invariante d'une chaîne à deux états

Découvrir

Un chat est soit endormi (E), soit éveillé (V). S'il dort, il reste endormi avec probabilité 0,8 ; s'il est éveillé, il s'endort avec probabilité 0,4. À long terme, quelle part du temps dort-il ?

  1. 23\dfrac{2}{3}
  2. 0,80{,}8

L'idée clé

La distribution invariante d'une chaîne à deux états.

Chaîne à deux états AA et BB : P(A→B)=pP(A \to B) = p, P(B→A)=qP(B \to A) = q (avec p+q>0p + q > 0). La distribution invariante est

πA=qp+q\pi_A = \dfrac{q}{p + q}, πB=pp+q\quad \pi_B = \dfrac{p}{p + q}.

Exemple corrigé

p=0,1p = 0{,}1, q=0,3q = 0{,}3.

πA=0,30,4\pi_A = \dfrac{0{,}3}{0{,}4}
Formule.
πA=0,75\pi_A = 0{,}75, πB=0,25\pi_B = 0{,}25
On calcule.

À toi, guidé

À toi : p=0,5p = 0{,}5, q=0,5q = 0{,}5 : πA\pi_A ?

0,50{,}5
0,51\dfrac{0{,}5}{1}.

Entraînement ★

  1. Chaîne à deux états : P(A→B)=0,8P(A \to B) = 0{,}8 et P(B→A)=0,8P(B \to A) = 0{,}8. Calcule πA\pi_A pour la distribution invariante.
  2. Chaîne à deux états : P(A→B)=0,6P(A \to B) = 0{,}6 et P(B→A)=0,3P(B \to A) = 0{,}3. Calcule πA\pi_A pour la distribution invariante.
  3. Chaîne à deux états : P(A→B)=0,1P(A \to B) = 0{,}1 et P(B→A)=0,8P(B \to A) = 0{,}8. Calcule πA\pi_A pour la distribution invariante.

Entraînement ★★

  1. Même chaîne (p=0,8p = 0{,}8, q=0,2q = 0{,}2), départ en AA. Calcule la probabilité d'être en AA après deux pas.
  2. Même chaîne (p=0,5p = 0{,}5, q=0,2q = 0{,}2), départ en AA. Calcule la probabilité d'être en AA après deux pas.

Bilan

Deux questions pour vérifier.

  1. Chaîne à deux états : P(A→B)=0,8P(A \to B) = 0{,}8 et P(B→A)=0,8P(B \to A) = 0{,}8. Calcule πA\pi_A pour la distribution invariante.
  2. Chaîne à deux états : P(A→B)=0,6P(A \to B) = 0{,}6 et P(B→A)=0,3P(B \to A) = 0{,}3. Calcule πA\pi_A pour la distribution invariante.

Fiche résumé

État stable

  • πA=qp+q\pi_A = \dfrac{q}{p + q}.
  • Ne dépend pas de l'état de départ.

Les algorithmes de classement des pages web utilisent la distribution invariante d'une immense chaîne de Markov.

6. Histoire des graphes : Euler et Markov

Découvrir

La ville de Königsberg avait sept ponts. Peut-on faire une promenade qui traverse chaque pont exactement une fois ? En 1736, Euler répond.

  1. Non, c'est impossible
  2. Oui, en partant du bon endroit

L'idée clé

Des ponts de Königsberg aux chaînes de Markov.

17501800185019001736Euler1736Euler
  1. Étape 117501800185019001736Euler1736EulerLeonhard Euler 1707–1783Jakob Emanuel Handmann, 1753. Domaine public1736 : Euler démontre qu'on ne peut pas traverser les sept ponts une seule fois chacun.
  2. Étape 217501800185019001736Eulervers 1900Markov1736Eulervers 1900MarkovAndreï Markov 1856–1922Auteur inconnu, 1886. Domaine publicMarkov (1856–1922) : chaînes où le futur ne dépend que du présent ; voyelles et consonnes.

En 1736, Euler résout le problème des ponts de Königsberg : un graphe a un chemin passant une fois par chaque arête seulement s'il a 0 ou 2 sommets de degré impair. Andreï Markov (1856–1922) étudie les chaînes qui portent son nom, où le futur ne dépend que du présent ; il les applique aux voyelles et consonnes d'un texte littéraire.

Source

À Königsberg, en Prusse, il y a une île, entourée par deux bras de la rivière, et sept ponts. On demande si quelqu'un peut organiser sa promenade de façon à passer une fois et une seule sur chacun des ponts.

Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, 1736 : le problème qu'il pose, résumé avec nos mots

Qu'est-ce qui compte vraiment pour répondre ?

  1. Quelles rives et îles chaque pont relie, pas les distances
  2. La longueur de chaque pont

Exemple corrigé

Königsberg : quatre zones reliées par sept ponts ; les degrés sont 5, 3, 3 et 3.

4
Sommets de degré impair.
promenade impossible
Plus de 2.

Entraînement ★

  1. À quoi Markov a-t-il appliqué ses chaînes ?
    1. Aux voyelles et consonnes d'un texte littéraire
    2. Aux ponts de Königsberg
    3. Aux moteurs de recherche
  1. Un graphe a 11 sommets, tous de degré 4. Combien a-t-il d'arêtes ?
  2. Un graphe a 8 sommets, tous de degré 4. Combien a-t-il d'arêtes ?
  1. Dans tout graphe, la somme des degrés vaut le double du nombre d'arêtes (c'est pourquoi les sommets impairs vont par paires, comme chez Euler). Un graphe a 15 arêtes : quelle est la somme des degrés ?

Fiche résumé

Les graphes aujourd'hui

  • GPS et livraisons : plus courts chemins dans un réseau routier.
  • Réseaux sociaux : qui est relié à qui.
  • Prédiction de texte : le mot suivant dépend des mots précédents, comme chez Markov.

Sources : article de MacTutor sur l'histoire de la topologie ; biographie de Markov (voir « Sources et crédits »).