Graphes en maths expertes : de la matrice d'adjacence aux chaînes de Markov

Les graphes appartiennent à l'option maths expertes de terminale, partie « Graphes et matrices » du programme de 2019 (BO spécial n° 8 du 25 juillet 2019). Ils n'ont rien à voir avec la représentation graphique d'une fonction : ici, on modélise des liens entre objets, et le calcul se fait avec les matrices.

Sommets, arêtes, degré : le vocabulaire exigé

Un graphe (non orienté) est formé de sommets et d'arêtes ; chaque arête relie deux sommets. Le programme demande les mots suivants.

• Ordre : le nombre de sommets.
• Sommets adjacents : deux sommets reliés par une arête.
• Degré d'un sommet : le nombre d'arêtes dont il est une extrémité.
• Graphe complet : graphe dont tous les sommets sont deux à deux adjacents. Le graphe complet d'ordre n a n(n − 1)/2 arêtes et chaque sommet y est de degré n − 1.
• Chaîne : suite de sommets dans laquelle deux sommets consécutifs sont adjacents. Sa longueur est le nombre d'arêtes parcourues, soit le nombre de sommets moins un. Une chaîne peut repasser par un sommet ou par une arête.
• Graphe connexe : graphe dans lequel deux sommets quelconques sont reliés par au moins une chaîne.

Une propriété sert à démasquer les graphes impossibles : la somme des degrés est égale au double du nombre d'arêtes, puisque chaque arête est comptée une fois à chacune de ses deux extrémités. Cette somme est donc toujours paire.

Le programme parle de « chaînes » dans les contenus et de « chemins » dans les capacités ; pour un graphe non orienté, c'est la même chose. Dans un graphe orienté, les arêtes deviennent des arcs, avec un sens, et l'on parle de chemins.

Pourquoi Aⁿ compte les chaînes de longueur n

Cette démonstration figure dans la liste du programme ; elle se fait par récurrence. On note p le nombre de sommets, numérotés de 1 à p, et, pour tout n ≥ 1, P(n) : « pour tous i et j, le coefficient (i, j) de Aⁿ est le nombre de chaînes de longueur n reliant i à j ».

Initialisation. Une chaîne de longueur 1 de i à j est une arête entre i et j : il y en a une si i et j sont adjacents, aucune sinon. C'est exactement aᵢⱼ. P(1) est vraie.

Hérédité. Supposons P(n) vraie pour un entier n ≥ 1. Une chaîne de longueur n + 1 de i à j se décompose de façon unique en une chaîne de longueur n de i à un sommet k, suivie de l'arête de k à j. On classe ces chaînes selon leur avant-dernier sommet k. Pour k fixé, il y a (Aⁿ)ᵢₖ chaînes de longueur n de i à k, par hypothèse de récurrence, et chacune se prolonge jusqu'à j de aₖⱼ façons (une si k et j sont adjacents, zéro sinon). Le nombre total est donc la somme, pour k de 1 à p, des produits (Aⁿ)ᵢₖ × aₖⱼ, qui est par définition du produit matriciel le coefficient (i, j) de AⁿA = Aⁿ⁺¹. P(n + 1) est vraie.

Conclusion. Par récurrence, P(n) est vraie pour tout n ≥ 1.

Les termes « décomposition unique » et « classer selon l'avant-dernier sommet » sont ce qui fait la démonstration : sans eux, on n'a pas justifié que la somme compte chaque chaîne une fois et une seule.

Coder un graphe et compter ses chaînes

La méthode, dans un exercice de devoir : nommer les sommets dans un ordre fixé et l'annoncer, écrire la matrice d'adjacence ligne par ligne, calculer la puissance demandée à la calculatrice, puis rédiger la phrase de conclusion en citant la propriété (« le coefficient (i, j) de Aⁿ est le nombre de chaînes de longueur n reliant i à j »). Le nombre seul ne justifie rien.

Exemple 1 · Un graphe d'ordre 4

Énoncé. Le graphe G a pour sommets A, B, C, D et pour arêtes AB, AC, BC, BD, CD. Donner l'ordre, les degrés, la matrice d'adjacence, puis le nombre de chaînes de longueur 3 reliant A à D et A à B.

Rédaction. G est d'ordre 4. Les degrés sont 2 pour A, 3 pour B, 3 pour C, 2 pour D ; leur somme, 10, est bien le double des 5 arêtes. G est connexe : A est relié directement à B et C, et à D par la chaîne A – B – D ; deux sommets quelconques sont donc reliés par une chaîne qui passe par A. Dans l'ordre A, B, C, D :

A = (0 1 1 0 ; 1 0 1 1 ; 1 1 0 1 ; 0 1 1 0), où chaque groupe entre points-virgules est une ligne.

On obtient A² = (2 1 1 2 ; 1 3 2 1 ; 1 2 3 1 ; 2 1 1 2) et A³ = (2 5 5 2 ; 5 4 5 5 ; 5 5 4 5 ; 2 5 5 2). Le coefficient (1, 4) de A³ vaut 2 : il existe deux chaînes de longueur 3 reliant A à D, A – B – C – D et A – C – B – D. Le coefficient (1, 2) vaut 5 : A – B – A – B, A – B – C – B, A – B – D – B, A – C – A – B, A – C – D – B. Trois d'entre elles repassent par un sommet déjà visité ; elles comptent quand même.

Au passage, la diagonale de A² redonne les degrés : une chaîne de longueur 2 de i à i est un aller-retour le long d'une arête issue de i.

Chaînes de Markov : le graphe pondéré et πₙ = π₀Pⁿ

Une chaîne de Markov à deux ou trois états décrit un système qui change d'état à chaque étape, avec des probabilités de transition qui ne dépendent que de l'état présent. On la représente par un graphe orienté pondéré : un sommet par état, un arc de i vers j portant la probabilité pᵢⱼ de passer de i à j. La matrice de transition P a pour coefficient (i, j) ce nombre pᵢⱼ ; la somme de chaque ligne vaut 1. La distribution à l'étape n est la matrice ligne πₙ des probabilités d'être dans chaque état.

La relation πₙ₊₁ = πₙP vient de la formule des probabilités totales, appliquée avec la partition donnée par l'état à l'étape n : la probabilité d'être en j à l'étape n + 1 est la somme des produits « probabilité d'être en i à l'étape n » × pᵢⱼ, qui est le coefficient j de πₙP. Une récurrence immédiate donne πₙ = π₀Pⁿ, et en prenant pour π₀ la distribution concentrée sur l'état i, on lit sur la ligne i de Pⁿ les probabilités de passer de i à chaque état en n transitions. Ces deux résultats sont aussi des démonstrations au programme.

Exemple 2 · Deux états, une distribution invariante

Énoncé. Un jour sec (état 1) est suivi d'un jour sec avec la probabilité 0,8 ; un jour de pluie (état 2) est suivi d'un jour sec avec la probabilité 0,4. Le jour 0 est sec. Donner P, π₁, π₂, puis la distribution invariante.

Rédaction. P = (0,8 0,2 ; 0,4 0,6) et π₀ = (1 0). Alors π₁ = π₀P = (0,8 0,2), et π₂ = π₁P = (0,8 × 0,8 + 0,2 × 0,4 ; 0,8 × 0,2 + 0,2 × 0,6) = (0,72 0,28). Le jour 2 est sec avec la probabilité 0,72.

On cherche π = (x y) avec x + y = 1 et πP = π. La première coordonnée donne 0,8x + 0,4y = x, soit 0,4y = 0,2x, c'est-à-dire x = 2y. Avec x + y = 1, on obtient y = 1/3 et x = 2/3. On vérifie la seconde coordonnée : 0,2 × 2/3 + 0,6 × 1/3 = 1/3. La distribution invariante est (2/3 1/3).

Sans la condition x + y = 1, l'équation πP = π a une infinité de solutions : c'est elle qui fixe la réponse.

Le graphe de l'exemple 1, animé

La figure reprend le graphe de l'exemple 1. Les quatre sommets apparaissent, puis les cinq arêtes se tracent, puis la matrice d'adjacence s'inscrit à droite, colonnes repérées par A, B, C, D. La chaîne A – B – C – D se surligne en or, la chaîne A – C – B – D en vert. Enfin A³ s'affiche, et son coefficient ligne A, colonne D est entouré : il vaut 2, autant que les deux chaînes tracées.

Les erreurs sur les graphes qui coûtent des points

• Matrice écrite sans annoncer l'ordre des sommets : le correcteur ne peut pas lire les coefficients.
• Longueur d'une chaîne comptée en nombre de sommets au lieu d'arêtes : A – B – D est de longueur 2, pas 3.
• Chaînes qui repassent par un sommet oubliées dans un dénombrement à la main, alors que Aⁿ les compte.
• Matrice de transition écrite en colonnes : avec πₙ en ligne, c'est la somme de chaque ligne de P qui vaut 1.
• Calcul de π₀Pⁿ écrit Pⁿπ₀, qui n'a pas de sens pour une matrice ligne π₀.

Trois exercices corrigés sur les graphes

Exercice 1 · Graphe complet et graphe impossible

Énoncé. a) Combien d'arêtes possède le graphe complet d'ordre 5 ? Quel est le degré de chaque sommet ? Que vaut la somme des coefficients de sa matrice d'adjacence ? b) Existe-t-il un graphe à 5 sommets dont tous les sommets sont de degré 3 ?

Correction. a) Chaque sommet est adjacent aux 4 autres : il est de degré 4. La somme des degrés vaut 5 × 4 = 20, donc le graphe a 20/2 = 10 arêtes, ce que redonne 5 × 4/2. La matrice d'adjacence a des 0 sur la diagonale et des 1 ailleurs : la somme de ses coefficients vaut 20, la somme des degrés.

b) La somme des degrés vaudrait 5 × 3 = 15, nombre impair. Or elle est égale au double du nombre d'arêtes. Un tel graphe n'existe pas.

Exercice 2 · Chaînes dans le graphe complet d'ordre 4

Énoncé. Le graphe complet K₄ a pour sommets A, B, C, D. Écrire sa matrice d'adjacence M, calculer M² et M³, puis donner le nombre de chaînes de longueur 2 de A à A, de longueur 2 de A à B et de longueur 3 de A à B.

Correction. Dans l'ordre A, B, C, D, M a des 0 sur la diagonale et des 1 ailleurs. On obtient M² avec des 3 sur la diagonale et des 2 ailleurs, puis M³ avec des 6 sur la diagonale et des 7 ailleurs.

Il y a 3 chaînes de longueur 2 de A à A (A – B – A, A – C – A, A – D – A), 2 de longueur 2 de A à B (A – C – B, A – D – B) et 7 de longueur 3 de A à B, lues sur les coefficients (1, 1) et (1, 2) de M² et (1, 2) de M³.

Exercice 3 · Une chaîne de Markov qui mène à une suite arithmético-géométrique

Énoncé. Un client est chez l'opérateur X (état 1) ou Y (état 2). D'un mois au suivant, un client de X reste chez X avec la probabilité 0,9 ; un client de Y passe chez X avec la probabilité 0,3. Au mois 0, le client est chez Y. On note πₙ = (pₙ 1 − pₙ). a) Donner P, π₁ et π₂. b) Montrer que pₙ₊₁ = 0,6pₙ + 0,3, puis exprimer pₙ en fonction de n. c) À partir de quel mois pₙ ≥ 0,7 ?

Correction. a) P = (0,9 0,1 ; 0,3 0,7), π₀ = (0 1), π₁ = (0,3 0,7), π₂ = (0,3 × 0,9 + 0,7 × 0,3 ; 0,3 × 0,1 + 0,7 × 0,7) = (0,48 0,52).

b) La première coordonnée de πₙ₊₁ = πₙP donne pₙ₊₁ = 0,9pₙ + 0,3(1 − pₙ) = 0,6pₙ + 0,3. Le réel ℓ tel que ℓ = 0,6ℓ + 0,3 est ℓ = 0,75. La suite (pₙ − 0,75) est géométrique de raison 0,6 et de premier terme −0,75 (voir la suite arithmético-géométrique), donc pₙ = 0,75 − 0,75 × 0,6ⁿ. La suite converge vers 0,75, et (0,75 0,25) est la distribution invariante : on vérifie que (0,75 0,25)P = (0,75 0,25).

c) pₙ ≥ 0,7 équivaut à 0,6ⁿ ≤ 1/15, soit n ≥ ln(1/15)/ln(0,6) ≈ 5,30, l'inégalité changeant de sens car ln(0,6) < 0. C'est à partir du mois 6 : p₅ ≈ 0,692 et p₆ ≈ 0,715.