Exercices corrigés ECG : graphes et chaînes de Markov

↩ Chapitre : Graphes et chaînes de Markov (ECG)

Introduction

Douze exercices corrigés sur les graphes (ECG1) et les chaînes de Markov (ECG2), chapitres propres aux maths appliquées, de difficulté croissante : degrés et formule d’Euler, matrice d’adjacence, nombre de chemins de longueur donnée, connexité, matrice de transition, évolution de la loi et loi invariante.

Avant de commencer

Revoir la formule d’Euler (la somme des degrés vaut deux fois le nombre d’arêtes), l’interprétation du coefficient (i,j) de A^k comme nombre de chemins de longueur k de i à j, et, pour les chaînes de Markov, la relation V_{n+1}=V_nP où V_n est la loi de X_n écrite en ligne.

Exercices

Exercice 1 · Degrés et formule d’Euler ★★★

On considère le graphe non orienté G de sommets 1,2,3,4,5 et d’arêtes \{1,2\}, \{1,3\}, \{2,3\}, \{2,4\}, \{3,4\}, \{4,5\}.

  1. Donner le degré de chaque sommet.
  2. Vérifier la formule d’Euler.
  3. Le graphe est-il connexe ?
Corrigé
  1. \deg(1)=2, \deg(2)=3, \deg(3)=3, \deg(4)=3, \deg(5)=1.
  2. La somme des degrés vaut 2+3+3+3+1=12, et le graphe a 6 arêtes : on a bien \sum\deg=2\times6. Chaque arête est comptée deux fois, une fois à chacune de ses extrémités.
  3. La chaîne (1,2,4,5) complétée par l’arête \{2,3\} relie tous les sommets : il existe une chaîne entre deux sommets quelconques, le graphe est connexe.

Exercice 2 · Conséquences de la formule d’Euler ★★★

  1. Montrer que dans un graphe non orienté, le nombre de sommets de degré impair est pair.
  2. Sept personnes peuvent-elles se serrer la main de sorte que chacune serre exactement trois mains ?
  3. Combien d’arêtes possède le graphe complet K_n à n sommets ?
Corrigé
  1. \sum\deg(s)=2m est pair. La somme des degrés pairs est paire, donc la somme des degrés impairs est paire : il y a un nombre pair de termes impairs.
  2. On modélise par un graphe : les personnes sont les sommets, les poignées de main les arêtes. On aurait 7 sommets de degré 3, impair, en nombre impair : c’est impossible.
  3. Dans K_n, chaque sommet est de degré n-1, donc 2m=n(n-1) et m=\frac{n(n-1)}{2}.

Exercice 3 · Matrice d’adjacence d’un graphe ★★★

Écrire la matrice d’adjacence A du graphe G de l’exercice 1. Quelles propriétés a-t-elle ? Comment lire les degrés sur A ?

Corrigé

Avec a_{ij}=1 si \{i,j\} est une arête, 0 sinon : A=\begin{pmatrix}0&1&1&0&0\\1&0&1&1&0\\1&1&0&1&0\\0&1&1&0&1\\0&0&0&1&0\end{pmatrix}.

Le graphe étant non orienté, A est symétrique ; il n’a pas de boucle, donc la diagonale est nulle. La somme des coefficients de la ligne i est le nombre de voisins de i, c’est-à-dire \deg(i) : on retrouve 2,3,3,3,1.

Exercice 4 · Graphe défini par sa matrice ★★★

Soit A=\begin{pmatrix}0&1&0&0&1\\1&0&1&0&0\\0&1&0&1&0\\0&0&1&0&1\\1&0&0&1&0\end{pmatrix}.

  1. Justifier que A est la matrice d’adjacence d’un graphe non orienté sans boucle, et le décrire.
  2. Donner le nombre d’arêtes et le degré de chaque sommet. Le graphe est-il connexe ?
Corrigé
  1. A est symétrique, à coefficients dans \{0,1\} et de diagonale nulle. Les arêtes sont \{1,2\}, \{2,3\}, \{3,4\}, \{4,5\} et \{5,1\} : c’est un cycle (1,2,3,4,5,1).
  2. Chaque ligne contient deux 1 : tous les sommets sont de degré 2, et m=\frac{5\times2}{2}=5 arêtes. Le cycle passe par tous les sommets : le graphe est connexe.

Exercice 5 · Compter des chemins avec les puissances de A ★★★

Soit G le graphe de sommets 1,2,3,4 et d’arêtes \{1,2\}, \{2,3\}, \{1,3\}, \{3,4\}, de matrice d’adjacence A.

  1. Écrire A et calculer A^2 et A^3.
  2. Combien y a-t-il de chaînes de longueur 3 de 1 à 3 ? Les écrire.
  3. Interpréter la diagonale de A^2.
Corrigé
  1. A=\begin{pmatrix}0&1&1&0\\1&0&1&0\\1&1&0&1\\0&0&1&0\end{pmatrix}, A^2=\begin{pmatrix}2&1&1&1\\1&2&1&1\\1&1&3&0\\1&1&0&1\end{pmatrix}, A^3=\begin{pmatrix}2&3&4&1\\3&2&4&1\\4&4&2&3\\1&1&3&0\end{pmatrix}.
  2. Le coefficient (1,3) de A^3 vaut 4 : il y a 4 chaînes de longueur 3 de 1 à 3. Ce sont les chaînes (1,2,1,3), (1,3,1,3), (1,3,2,3) et (1,3,4,3).
  3. (A^2)_{ii} compte les chaînes (i,j,i), une par voisin j de i : c’est \deg(i). On lit bien 2,2,3,1.

Exercice 6 · Traces de A² et A³ ★★★

Soit G un graphe non orienté sans boucle à n sommets et m arêtes, de matrice d’adjacence A.

  1. Montrer que \operatorname{tr}(A^2)=2m.
  2. Montrer que \operatorname{tr}(A^3) vaut six fois le nombre de triangles de G.
  3. Vérifier sur le graphe de l’exercice 5.
Corrigé
  1. (A^2)_{ii}=\sum_{j}a_{ij}a_{ji}=\sum_j a_{ij}^2=\deg(i), donc \operatorname{tr}(A^2)=\sum_i\deg(i)=2m par la formule d’Euler.
  2. (A^3)_{ii} compte les chaînes fermées (i,j,k,i) de longueur 3. Sans boucle, i, j, k sont distincts et forment un triangle. Un triangle \{i,j,k\} fournit 2 telles chaînes partant de chacun de ses 3 sommets (deux sens de parcours), soit 6 au total dans la trace.
  3. \operatorname{tr}(A^2)=2+2+3+1=8=2\times4 et \operatorname{tr}(A^3)=2+2+2+0=6 : un seul triangle, \{1,2,3\}.

Exercice 7 · Connexité et matrice d’adjacence ★★★

Soit G un graphe à n sommets, de matrice d’adjacence A.

  1. Montrer que s’il existe une chaîne entre deux sommets distincts i et j, il en existe une de longueur au plus n-1.
  2. En déduire que G est connexe si et seulement si tous les coefficients de I_n+A+A^2+\dots+A^{n-1} sont strictement positifs.
  3. Application : G a pour sommets 1,2,3,4 et pour arêtes \{1,2\} et \{3,4\}.
Corrigé
  1. Prenons une chaîne de longueur minimale de i à j. Si elle passait deux fois par le même sommet, on pourrait supprimer la boucle intermédiaire et obtenir une chaîne plus courte. Ses sommets sont donc distincts : elle en a au plus n, donc au plus n-1 arêtes.
  2. (A^k)_{ij} est le nombre de chaînes de longueur k de i à j, et (I_n)_{ii}=1. Le coefficient (i,j) de la somme est strictement positif si et seulement s’il existe une chaîne de longueur au plus n-1 de i à j, c’est-à-dire, par la question 1, une chaîne quelconque. D’où l’équivalence.
  3. On trouve I_4+A+A^2+A^3=\begin{pmatrix}2&2&0&0\\2&2&0&0\\0&0&2&2\\0&0&2&2\end{pmatrix} : le coefficient (1,3) est nul, aucune chaîne ne relie 1 à 3, le graphe n’est pas connexe.

Exercice 8 · Chemins dans un graphe orienté ★★★

On considère le graphe orienté de sommets 1,2,3 dont les arcs sont 1\to2, 2\to3 et 3\to1.

  1. Écrire sa matrice d’adjacence A. Est-elle symétrique ?
  2. Calculer A^2 et A^3.
  3. Pour n\in\mathbb{N}, combien y a-t-il de chemins de longueur n de 1 à 1 ?
Corrigé
  1. A=\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}. Elle n’est pas symétrique : il y a un arc de 1 vers 2 mais pas de 2 vers 1.
  2. A^2=\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix} et A^3=I_3.
  3. Par division euclidienne n=3q+r, on a A^n=(A^3)^qA^r=A^r. Le coefficient (1,1) de A^n vaut 1 si r=0 et 0 sinon : il y a exactement un chemin (le tour du cycle, répété q fois) lorsque n est multiple de 3, aucun sinon.

Exercice 9 · Chaîne de Markov à deux états ★★★

Chaque jour, le temps est beau (état B) ou pluvieux (état P). S’il fait beau, il fait beau le lendemain avec probabilité 0{,}8 ; s’il pleut, il pleut le lendemain avec probabilité 0{,}6. On note p_n la probabilité qu’il fasse beau le jour n.

  1. Écrire la matrice de transition M (états dans l’ordre B, P).
  2. Montrer que p_{n+1}=0{,}4\,p_n+0{,}4.
  3. En déduire p_n en fonction de p_0, puis la limite de p_n.
  4. Vérifier que \pi=\left(\frac23,\frac13\right) est une loi invariante : \pi M=\pi.
Corrigé
  1. M=\begin{pmatrix}0{,}8&0{,}2\\0{,}4&0{,}6\end{pmatrix} : chaque ligne est une loi de probabilité.
  2. Par la formule des probabilités totales sur le temps du jour n : p_{n+1}=0{,}8\,p_n+0{,}4\,(1-p_n)=0{,}4\,p_n+0{,}4.
  3. Le point fixe \ell vérifie \ell=0{,}4\ell+0{,}4, soit \ell=\frac23. La suite (p_n-\frac23) est géométrique de raison 0{,}4 : p_n=\frac23+\left(p_0-\frac23\right)0{,}4^n. Comme |0{,}4| < 1, p_n\to\frac23, quelle que soit la situation initiale.
  4. \pi M=\left(\frac23\times0{,}8+\frac13\times0{,}4,\;\frac23\times0{,}2+\frac13\times0{,}6\right)=\left(\frac23,\frac13\right).

Exercice 10 · Loi invariante d’une chaîne à trois états ★★★

Une chaîne de Markov (X_n) sur les états 1,2,3 a pour matrice de transition P=\begin{pmatrix}\frac12&\frac12&0\\\frac14&\frac12&\frac14\\0&\frac12&\frac12\end{pmatrix}, avec X_0=1.

  1. Dessiner le graphe probabiliste associé.
  2. Déterminer la loi de X_1 et celle de X_2.
  3. Déterminer les lois invariantes \pi=(a,b,c), c’est-à-dire telles que \pi P=\pi et a+b+c=1.
Corrigé
  1. Sommets 1,2,3 ; boucles de poids \frac12 sur chaque sommet ; arcs 1\to2 de poids \frac12, 2\to1 et 2\to3 de poids \frac14, 3\to2 de poids \frac12.
  2. V_0=(1,0,0), V_1=V_0P=\left(\frac12,\frac12,0\right), puis V_2=V_1P=\left(\frac14+\frac18,\;\frac14+\frac14,\;\frac18\right)=\left(\frac38,\frac12,\frac18\right).
  3. \pi P=\pi s’écrit \frac a2+\frac b4=a, \frac a2+\frac b2+\frac c2=b et \frac b4+\frac c2=c, soit b=2a et b=2c (la deuxième équation est alors automatique). Avec a+b+c=1 : a+2a+a=1, d’où l’unique loi invariante \pi=\left(\frac14,\frac12,\frac14\right).

Exercice 11 · Puissances d’une matrice de transition ★★★

Soient a,b\in\,]0,1[ et P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}. On pose E=\frac{1}{a+b}\begin{pmatrix}b&a\\b&a\end{pmatrix} et F=\frac{1}{a+b}\begin{pmatrix}a&-a\\-b&b\end{pmatrix}.

  1. Vérifier que E+F=I_2, P=E+(1-a-b)F, E^2=E, F^2=F et EF=FE=0.
  2. En déduire P^n pour tout n\in\mathbb{N}.
  3. Déterminer la limite de P^n et l’interpréter.
Corrigé
  1. E+F=\frac{1}{a+b}\begin{pmatrix}a+b&0\\0&a+b\end{pmatrix}=I_2, puis E+(1-a-b)F=I_2-(a+b)F=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}=P. Le calcul direct donne \begin{pmatrix}b&a\\b&a\end{pmatrix}^2=(a+b)\begin{pmatrix}b&a\\b&a\end{pmatrix}, d’où E^2=E ; de même F^2=F, et les produits EF et FE sont nuls.
  2. Par récurrence, P^n=E+(1-a-b)^nF : c’est vrai pour n=0 car E+F=I_2, et si c’est vrai au rang n, P^{n+1}=\big(E+(1-a-b)^nF\big)\big(E+(1-a-b)F\big)=E+(1-a-b)^{n+1}F.
  3. Comme a,b\in\,]0,1[, -1 < 1-a-b < 1, donc (1-a-b)^n\to0 et P^n\to E. Les deux lignes de E sont égales à \left(\frac{b}{a+b},\frac{a}{a+b}\right) : quelle que soit la loi initiale, la loi de X_n converge vers cette loi, qui est l’unique loi invariante de la chaîne. Avec a=0{,}2 et b=0{,}4, on retrouve \left(\frac23,\frac13\right) de l’exercice 9.

Exercice 12 · Marche aléatoire sur un graphe ★★★

Soit G un graphe non orienté connexe, sans boucle, à n sommets et m arêtes. Un marcheur se déplace sur les sommets : à chaque étape, il quitte le sommet i pour l’un des \deg(i) voisins de i, choisi au hasard de façon équiprobable.

  1. Écrire le coefficient p_{ij} de la matrice de transition P.
  2. Montrer que \pi=\left(\frac{\deg(1)}{2m},\dots,\frac{\deg(n)}{2m}\right) est une loi invariante.
  3. Application au graphe de l’exercice 1.
Corrigé
  1. p_{ij}=\frac{1}{\deg(i)} si \{i,j\} est une arête, et p_{ij}=0 sinon. Le graphe étant connexe, chaque sommet a au moins un voisin, donc \deg(i)\geqslant1.
  2. Les \pi_i sont positifs et de somme \frac{2m}{2m}=1 par la formule d’Euler : \pi est une loi. Pour tout sommet j, (\pi P)_j=\sum_{i\text{ voisin de }j}\frac{\deg(i)}{2m}\cdot\frac{1}{\deg(i)}=\frac{\deg(j)}{2m}=\pi_j.
  3. Degrés 2,3,3,3,1 et m=6 : \pi=\left(\frac{2}{12},\frac{3}{12},\frac{3}{12},\frac{3}{12},\frac{1}{12}\right)=\left(\frac16,\frac14,\frac14,\frac14,\frac1{12}\right). À long terme, le marcheur passe plus de temps sur les sommets les plus reliés : c’est une première mesure de centralité.

Pour aller plus loin

Besoin d’aide sur ce chapitre ?

Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir ou un concours à préparer : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 20 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca ou en ligne.

Publications similaires