Comment calculer le nombre de chemins de longueur $n$ entre deux sommets d'un graphe ?

En élevant la matrice d'adjacence $A$ à la puissance $n$ : le coefficient $(A^n)_{ij}$ donne le nombre de chemins de longueur exactement $n$ allant du sommet $i$ au sommet $j$

L'objectif

Compter le nombre de chemins de longueur $n$ entre deux sommets d'un graphe orienté.

Le principe

Le coefficient $(i,j)$ de $A^n$ (où $A$ est la matrice d'adjacence) est égal au nombre de chemins de longueur exactement $n$ allant du sommet $i$ au sommet $j$ .

La méthode

1
Construire la matrice d'adjacence $A$ : $A_{ij} = 1$ s'il existe un arc de $i$ vers $j$ , $0$ sinon.
2
Calculer $A^n$ par multiplications matricielles successives ( $A^2 = A \times A$ , $A^3 = A^2 \times A$ , etc.).
Comment calculer les puissances d'une matrice carrée ?Voir
3
Lire le coefficient $(A^n)_{ij}$ pour obtenir le nombre de chemins de longueur $n$ de $i$ à $j$ ; sommer une ligne pour obtenir tous les chemins partant de $i$ .

Exemple corrigé

Difficulté croissante de 1 à 4

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.

En élevant la matrice d'adjacence AAA à la puissance nnn : le coefficient (An)ij(A^n)_{ij}(An)ij​ donne le nombre de chemins de longueur exactement nnn allant du sommet iii au sommet jjj

Exemple corrigé

En élevant la matrice d'adjacence $A$ à la puissance $n$ : le coefficient $(A^n)_{ij}$ donne le nombre de chemins de longueur exactement $n$ allant du sommet $i$ au sommet $j$