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

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$

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

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

Pour comprendre, fais des exercices !

0/5 validés

Exercice d'exemple

On considère un graphe orienté à 3 sommets avec les arcs $1 \to 2$ , $2 \to 3$ , $3 \to 1$ . Trouver le nombre de chemins de longueur 2 entre chaque paire de sommets.

Étape 1 —

Construire la matrice d'adjacence

A

A_{ij} = 1

s'il existe un arc de

i

vers

j

0

sinon.

$A = \begin{pmatrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{pmatrix}$ (cycle $1 \to 2 \to 3 \to 1$ ).

Étape 2 —

Calculer

A^n

par multiplications matricielles successives (

A^2 = A \times A

A^3 = A^2 \times A

, etc.).

$A^2 = A \times A = \begin{pmatrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0\end{pmatrix}$ .

Étape 3 —

Lire le coefficient

(A^n)_{ij}

pour obtenir le nombre de chemins de longueur

n

i

j

; sommer une ligne pour obtenir tous les chemins partant de

i

Il existe exactement 1 chemin de longueur 2 : de 1 à 3, de 2 à 1, de 3 à 2. Par exemple $1 \to 2 \to 3$ est le seul chemin de longueur 2 de 1 à 3.

Application guidée

Avec le même graphe cycique $1 \to 2 \to 3 \to 1$ , combien y a-t-il de chemins de longueur 3 de 1 à 1 ?

Application autonome 1

Graphe orienté : $1 \to 2$ , $1 \to 3$ , $2 \to 4$ , $3 \to 4$ . Combien y a-t-il de chemins de longueur 2 de 1 à 4 ?

Application autonome 2

Graphe non orienté complet $K_3$ (arêtes $1-2$ , $2-3$ , $1-3$ ). Combien de chemins de longueur 2 de 1 à 1 (retour au départ) ?

Application autonome 3

Graphe orienté à 4 sommets : arcs $1\to 2$ , $2\to 3$ , $2\to 4$ , $3\to 1$ , $4\to 1$ . Combien y a-t-il de chemins de longueur $3$ partant de $1$ et revenant à $1$ ?

Crée ton compte gratuit pour accéder à la fiche et aux exercices

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

Pour comprendre, fais des exercices !

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$