Comment compter les chemins de… : En calculant A^d et en lisant le… — ECG1 appliquées | MetMat

Comment compter les chemins de longueur $d$ à l'aide de la matrice d'adjacence ?

En calculant $A^d$ et en lisant le coefficient $(i,j)$ comme nombre de chemins de longueur $d$ de $i$ vers $j$

Dénombrer les chemins de longueur exactement $d$ reliant deux sommets d'un graphe grâce aux puissances de sa matrice d'adjacence.

Maîtriser

Reconnaître

Résoudre

Que ferais-tu face à un exercice de ce type ?

Soit le graphe orienté à $3$ sommets de matrice $A=\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ . Déterminer le nombre de chemins de longueur $2$ de $1$ vers $3$ .

L'objectif

Dénombrer les chemins de longueur exactement $d$ reliant deux sommets d'un graphe grâce aux puissances de sa matrice d'adjacence.

Le principe

Si $A\in\mathcal{M}_n(\mathbb{R})$ est la matrice d'adjacence d'un graphe (orienté ou non) dont les sommets sont numérotés $1,\dots,n$ , alors pour tout entier $d\ge 1$ , le coefficient $(A^d)_{i,j}$ est égal au nombre de chemins de longueur $d$ de $i$ vers $j$ .

La méthode

1
J'identifie la matrice d'adjacence $A$ du graphe et la longueur $d$ souhaitée pour les chemins.
Comment construire la matrice d'adjacence d'un graphe (orienté ou non) ?Voir
2
Je calcule la puissance $A^d$ par multiplications successives ( $A^2=A\cdot A$ , $A^3=A^2\cdot A$ , etc.).
Comment calculer les puissances $n$-èmes d'une matrice carrée ?Voir
3
Je lis le coefficient $(A^d)_{i,j}$ pour obtenir le nombre de chemins de longueur $d$ de $i$ vers $j$ , et je conclus.

Pour comprendre, fais des exercices !

Exercice d'exemple

Soit le graphe orienté à $3$ sommets de matrice $A=\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ . Déterminer le nombre de chemins de longueur $2$ de $1$ vers $3$ .

Étape 1 —

J'identifie la matrice d'adjacence

A

du graphe et la longueur

d

souhaitée pour les chemins.

La matrice $A$ est donnée et on cherche $d=2$ pour le trajet de $1$ à $3$ .

Étape 2 —

Je calcule la puissance

A^d

par multiplications successives (

A^2=A\cdot A

A^3=A^2\cdot A

, etc.).

Je calcule $A^2=A\cdot A=\begin{pmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$ .

Étape 3 —

Je lis le coefficient

(A^d)_{i,j}

pour obtenir le nombre de chemins de longueur

d

i

vers

j

, et je conclus.

Le coefficient $(A^2)_{1,3}=1$ , donc il y a exactement $1$ chemin de longueur $2$ de $1$ vers $3$ (c'est le chemin $1\to 2\to 3$ ).

$1$ chemin de longueur $2$ de $1$ vers $3$ .

Les applications suivantes et la correction guidée sont réservées aux membres Premium

La méthode et sa première application corrigée restent en accès libre. Le Premium débloque les applications suivantes, l'aide IA et le suivi de ta maîtrise.

Comment compter les chemins de longueur ddd à l'aide de la matrice d'adjacence ?

En calculant AdA^dAd et en lisant le coefficient (i,j)(i,j)(i,j) comme nombre de chemins de longueur ddd de iii vers jjj

Pour comprendre, fais des exercices !

Comment compter les chemins de longueur $d$ à l'aide de la matrice d'adjacence ?

En calculant $A^d$ et en lisant le coefficient $(i,j)$ comme nombre de chemins de longueur $d$ de $i$ vers $j$