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$

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$ .

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, passons aux 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$ .

1

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

2

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

3

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, passons aux 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$