Mathématiques expertes (option) · Terminale

Matrice d'adjacence et chemins : cours de Terminale (maths expertes)

Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur

L'essentiel

La matrice d'adjacence d'un graphe d'ordre $n$ est un tableau carré $n \times n$ : le coefficient $a_{ij}$ compte les arêtes (ou arcs) de $i$ vers $j$ ; la diagonale compte les boucles.¹⁴
Le tableau dépend de l'ordre choisi pour les sommets ; une fois l'ordre fixé, il est unique. Un graphe simple non orienté donne une matrice binaire, symétrique, à diagonale nulle.⁴
Théorème : le coefficient $(i,j)$ de $A^k$ est le nombre de chemins de longueur $k$ de $i$ à $j$ .⁴
Méthode : numéroter les sommets, écrire $A$ , calculer $A^k$ ligne par ligne, lire le coefficient demandé. La somme des coefficients de $A^k$ donne tous les chemins de longueur $k$ .
Pour un graphe probabiliste, la matrice d'adjacence s'appelle matrice de transition ; c'est le point de départ des chaînes de Markov.¹²

Pourquoi coder un graphe par un tableau de nombres

Un graphe se dessine facilement, mais un dessin ne se calcule pas. Pour répondre à une question comme « de combien de façons peut-on aller du sommet A au sommet D en trois étapes ? », il faut un objet sur lequel on sait faire des opérations. Les matrices que tu as étudiées juste avant, avec leurs produits et leurs puissances, jouent exactement ce rôle.

Le programme de Mathématiques expertes range la matrice d'adjacence parmi les exemples de représentations matricielles, et il demande d'utiliser les puissances de cette matrice pour étudier les chemins d'un graphe.² Ce cours suit trois étapes : construire la matrice à partir d'un graphe, comprendre ce qu'elle contient, puis exploiter ses puissances.

Avant de commencer, rappelle-toi trois choses : savoir multiplier deux matrices carrées, connaître le vocabulaire des graphes (sommet, arête, arc, boucle, ordre), et savoir faire une démonstration par récurrence.

Définition de la matrice d'adjacence

Lire une matrice d'adjacence
Type de graphe	Lecture du coefficient $a_{ij}$	Symétrie	Diagonale
Non orienté, simple	1 si une arête relie i et j	Symétrique	Que des 0
Orienté	1 si un arc va de i vers j	Pas forcément	1 pour chaque boucle
Avec arêtes multiples	Nombre d'arêtes entre i et j	Symétrique si non orienté	Nombre de boucles

Lire une matrice d'adjacence · Résumé des conventions de lecture.

Propriétés de la matrice d'adjacence

Ces propriétés servent de contrôle. Quand tu viens d'écrire une matrice pour un graphe non orienté, regarde si elle est symétrique par rapport à sa diagonale : si ce n'est pas le cas, tu as oublié une arête d'un côté. Pour un graphe orienté, la symétrie n'a aucune raison d'exister : un arc de $1$ vers $2$ n'implique pas d'arc de $2$ vers $1$ .

Chemins et puissances de la matrice

Voici le résultat central du chapitre. Il relie une opération sur les matrices, la puissance, à une question sur les graphes, le dénombrement de chemins. Avant de l'énoncer, regarde pourquoi c'est naturel pour $k=2$ .

Un chemin de longueur $2$ de $i$ à $j$ passe par un sommet intermédiaire $l$ : il faut une liaison de $i$ vers $l$ , puis une liaison de $l$ vers $j$ . Pour un $l$ donné, le nombre de tels chemins vaut $a_{il}\times a_{lj}$ . En additionnant sur tous les sommets $l$ possibles, on obtient

$\sum_{l=1}^{n} a_{il}\,a_{lj},$

qui est exactement la formule du coefficient $(i,j)$ du produit $A\times A$ . Le produit matriciel compte donc les chemins à deux étapes.

Démonstration · Démonstration par récurrence sur $k$

Notons $(A^k)_{ij}$ le coefficient $(i,j)$ de $A^k$ et $P(k)$ la propriété : « pour tous sommets $i$ et $j$ , $(A^k)_{ij}$ est le nombre de chemins de longueur $k$ de $i$ à $j$ ».

Initialisation. Pour $k=1$ , $A^1=A$ et un chemin de longueur $1$ de $i$ à $j$ est une liaison directe : par définition de la matrice d'adjacence, $a_{ij}$ compte ces liaisons. $P(1)$ est vraie.

Hérédité. Soit $k\geq 1$ tel que $P(k)$ soit vraie. On a $A^{k+1}=A^k\times A$ , donc

$(A^{k+1})_{ij}=\sum_{l=1}^{n}(A^k)_{il}\,a_{lj}.$

Classons les chemins de longueur $k+1$ de $i$ à $j$ selon leur avant-dernier sommet $l$ . Un tel chemin se compose d'un chemin de longueur $k$ de $i$ à $l$ , puis d'une liaison de $l$ à $j$ . Par hypothèse de récurrence il y a $(A^k)_{il}$ chemins du premier type, et $a_{lj}$ liaisons du second type. Pour un $l$ fixé, il y a donc $(A^k)_{il}\,a_{lj}$ chemins. En sommant sur tous les $l$ , on retrouve $(A^{k+1})_{ij}$ : $P(k+1)$ est vraie.

Conclusion. $P(1)$ est vraie et $P$ est héréditaire, donc $P(k)$ est vraie pour tout entier $k\geq 1$ .

Méthode et calculs complets

NuméroterFixer et noter l'ordre des sommets.
Écrire ARemplir ligne par ligne, contrôler la symétrie.
Calculer A^kUtiliser A^(k+1) = A^k x A.
LireLigne = départ, colonne = arrivée.
ConclurePhrase : il y a ... chemins de longueur k.

Méthode : compter des chemins · Les étapes à suivre dans l'ordre.

ExempleGraphe non orienté : calcul de $M^2$ et $M^3$

Reprenons la matrice $M$ du graphe $A,B,C,D$ . Une astuce pratique : pour calculer le produit $B\times M$ , la ligne $i$ du résultat est la somme des lignes de $M$ correspondant aux $1$ de la ligne $i$ de $B$ , avec les multiplicités.

Ligne $A$ de $M$ : $(0,1,1,0)$ , donc la ligne $A$ de $M^2$ est la somme des lignes $B$ et $C$ de $M$ : $(1,0,1,0)+(1,1,0,1)=(2,1,1,1)$ . En continuant pour chaque ligne :

$M^2=\begin{pmatrix} 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 0 \\ 1 & 1 & 0 & 1 \end{pmatrix}$

Pour $M^3=M^2\times M$ , la ligne $A$ de $M^3$ vaut $2\times(\text{ligne }A)+(\text{ligne }B)+(\text{ligne }C)+(\text{ligne }D)$ de $M$ , soit $(0,2,2,0)+(1,0,1,0)+(1,1,0,1)+(0,0,1,0)=(2,3,4,1)$ . Au final :

$M^3=\begin{pmatrix} 2 & 3 & 4 & 1 \\ 3 & 2 & 4 & 1 \\ 4 & 4 & 2 & 3 \\ 1 & 1 & 3 & 0 \end{pmatrix}$

Lecture. Le coefficient $(A,D)$ de $M^3$ vaut $1$ : il y a un seul chemin de longueur $3$ de $A$ à $D$ , à savoir $A\to B\to C\to D$ . Le coefficient $(C,D)$ vaut $3$ : trois chemins de longueur $3$ relient $C$ à $D$ , par exemple $C\to A\to C\to D$ et $C\to B\to C\to D$ , et $C\to D\to C\to D$ . Le coefficient $(A,A)=2$ compte les allers-retours en triangle $A\to B\to C\to A$ et $A\to C\to B\to A$ .

ExempleGraphe orienté : calcul de $N^2$ et $N^3$

Reprenons la matrice $N$ du graphe à trois sommets. Ici la ligne $i$ de $N^2$ est la somme des lignes de $N$ désignées par les $1$ de la ligne $i$ de $N$ .

Ligne $1$ de $N$ : $(0,1,0)$ , donc la ligne $1$ de $N^2$ est la ligne $2$ de $N$ : $(0,0,1)$ . Ligne $2$ de $N$ : $(0,0,1)$ , donc la ligne $2$ de $N^2$ est la ligne $3$ de $N$ : $(1,1,0)$ . Ligne $3$ de $N$ : $(1,1,0)$ , donc la ligne $3$ de $N^2$ est la ligne $1$ plus la ligne $2$ de $N$ : $(0,1,1)$ . Ainsi

$N^2=\begin{pmatrix} 0 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix},\qquad N^3=N^2\times N=\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}.$

Lecture. Le coefficient $(3,3)$ de $N^3$ vaut $1$ : un seul circuit de longueur $3$ ramène de $3$ à $3$ , c'est $3\to1\to2\to3$ . Le coefficient $(1,3)$ vaut $0$ : aucun chemin d'exactement trois arcs ne mène de $1$ à $3$ , même si $1\to2\to3$ y mène en deux arcs.

Applications, lectures utiles et erreurs fréquentes

Dans le cas d'un graphe probabiliste, la matrice qui joue le rôle de matrice d'adjacence s'appelle la matrice de transition, ou matrice stochastique.¹ Le programme de Mathématiques expertes relie ensuite ces puissances aux chaînes de Markov : la probabilité de passer de l'état $i$ à l'état $j$ en plusieurs étapes s'exprime à l'aide de la puissance de cette matrice.² C'est l'objet du prochain chapitre ; ce que tu viens d'apprendre sur le produit de matrices et le sens des lignes et des colonnes y sera réutilisé tel quel.

Matrice d'adjacence

Définition
- Tableau n x n
- Ligne = départ
- Colonne = arrivée
Propriétés
- Unique si ordre fixé
- Symétrique si non orienté
- Diagonale = boucles
Chemins
- Coefficient de A^k
- Longueur exacte k
- Somme = total
Suite
- Matrice de transition
- Chaînes de Markov

Carte de la notion · Vue d'ensemble du chapitre.

Exercices corrigés

Exercice 1 Compter des chemins dans un graphe non orienté

★★☆Environ 15 min

On considère le graphe non orienté de sommets $P$ , $Q$ , $R$ , $S$ et d'arêtes $PQ$ , $PR$ , $PS$ , $QR$ et $RS$ . On range les sommets dans l'ordre $P, Q, R, S$ .

Écris la matrice d'adjacence $A$ de ce graphe.
Calcule $A^2$ puis $A^3$ .
Combien y a-t-il de chemins de longueur $3$ de $P$ à $R$ ?

Indice 1

Écris d'abord la ligne de $P$ : $P$ est relié à $Q$ , $R$ et $S$ .

Indice 2

Pour calculer une ligne de $A^2$ , additionne les lignes de $A$ associées aux voisins du sommet.

Voir la correction pas à pas

Ligne $P$ : voisins $Q,R,S$ donc $(0,1,1,1)$ . Ligne $Q$ : voisins $P,R$ donc $(1,0,1,0)$ . Ligne $R$ : voisins $P,Q,S$ donc $(1,1,0,1)$ . Ligne $S$ : voisins $P,R$ donc $(1,0,1,0)$ . La matrice est symétrique, ce qui est bon signe.
Ligne $P$ de $A^2$ : somme des lignes $Q$ , $R$ , $S$ de $A$ = $(1,0,1,0)+(1,1,0,1)+(1,0,1,0)=(3,1,2,1)$ .
On a de même ligne $Q$ de $A^2$ = $(1,2,1,2)$ , ligne $R$ = $(2,1,3,1)$ , ligne $S$ = $(1,2,1,2)$ .
Pour le coefficient $(P,R)$ de $A^3=A^2\times A$ , multiplie la ligne $P$ de $A^2$ par la colonne $R$ de $A$ : $(3,1,2,1)\cdot(1,1,0,1)=3+1+0+1=5$ .
Il y a donc $5$ chemins de longueur $3$ de $P$ à $R$ .

Le coefficient $(P,R)$ de $A^3$ vaut $5$ : il y a $5$ chemins de longueur $3$ de $P$ à $R$ . Il n'est pas nécessaire de calculer toute la matrice $A^3$ quand une seule case est demandée : une ligne de $A^2$ et une colonne de $A$ suffisent.

Exercice 2 Graphe orienté : tous les chemins de longueur 3

★★☆Environ 15 min

Un graphe orienté a trois sommets $1$ , $2$ , $3$ et quatre arcs : $1\to2$ , $2\to3$ , $3\to1$ et $3\to2$ .

Donne sa matrice d'adjacence $N$ .
Calcule $N^2$ puis $N^3$ .
Quel est le nombre total de chemins de longueur $3$ dans ce graphe ?

Indice 1

Ligne = départ, colonne = arrivée : place un $1$ en ligne $i$ , colonne $j$ pour chaque arc $i\to j$ .

Indice 2

Le nombre total de chemins de longueur $3$ est la somme de tous les coefficients de $N^3$ .

Voir la correction pas à pas

Matrice : $N=\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}$ .
Calcul de $N^2$ : la ligne $i$ de $N^2$ est la somme des lignes de $N$ pointées par les $1$ de la ligne $i$ de $N$ . On obtient $N^2=\begin{pmatrix}0&0&1\\1&1&0\\0&1&1\end{pmatrix}$ .
Calcul de $N^3=N^2\times N$ : $N^3=\begin{pmatrix}1&1&0\\0&1&1\\1&1&1\end{pmatrix}$ .
Somme des coefficients de $N^3$ : $2+2+3=7$ .

Il y a $7$ chemins de longueur $3$ dans ce graphe. Tu peux contrôler un coefficient en listant les chemins : le coefficient $(3,3)=1$ correspond à l'unique circuit $3\to1\to2\to3$ .

Exercice 3 Le cycle à quatre sommets et la parité

★★★Environ 20 min

Soit le graphe non orienté « carré » de sommets $1,2,3,4$ et d'arêtes $12$ , $23$ , $34$ , $41$ , avec les sommets rangés dans l'ordre $1,2,3,4$ .

Écris la matrice d'adjacence $A$ et calcule $A^2$ .
En déduire le nombre de chemins de longueur $4$ de $1$ à $1$ .
Sans calcul supplémentaire, explique pourquoi il n'existe aucun chemin de longueur $3$ de $1$ à $1$ .

Indice 1

On a $A^4=A^2\times A^2$ .

Indice 2

Regarde les positions des coefficients non nuls dans $A^2$ : elles forment un motif.

Voir la correction pas à pas

$A=\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}$ .
$A^2=\begin{pmatrix}2&0&2&0\\0&2&0&2\\2&0&2&0\\0&2&0&2\end{pmatrix}$ . La diagonale $(2,2,2,2)$ donne les degrés, tous égaux à $2$ .
Le coefficient $(1,1)$ de $A^4=A^2\times A^2$ est le produit de la ligne $1$ de $A^2$ , $(2,0,2,0)$ , par la colonne $1$ de $A^2$ , $(2,0,2,0)$ : $4+0+4+0=8$ .
Pour la longueur $3$ : le coefficient $(1,1)$ de $A^3=A^2\times A$ est le produit de $(2,0,2,0)$ par la colonne $1$ de $A$ , $(0,1,0,1)$ , soit $0$ . Un chemin de longueur impaire change toujours de parité du numéro de sommet (de $1$ ou $3$ vers $2$ ou $4$ et réciproquement), il ne peut donc pas se terminer à son point de départ.

Il y a $8$ chemins de longueur $4$ de $1$ à $1$ et aucun de longueur $3$ . Les coefficients nuls de $A^2$ et la diagonale nulle de $A^3$ révèlent une propriété du graphe : on y alterne entre deux groupes de sommets.

Les questions qu'on se pose

Que lit-on, ligne ou colonne, pour un graphe orienté ?

On place un $1$ en ligne $i$ , colonne $j$ quand un arc part de $i$ vers $j$ .¹ La ligne d'un sommet donne donc ses successeurs et la colonne ses prédécesseurs. Si le sens d'une convention n'est pas précisé dans un sujet, écris ta convention en une phrase avant de donner la matrice.

À quoi sert la matrice d'adjacence si on peut compter les chemins sur le dessin ?

Sur un petit graphe et pour une longueur $2$ ou $3$ , le dessin suffit. Dès que le graphe a beaucoup de sommets ou que la longueur $k$ est grande, l'énumération à la main devient impraticable, alors que le calcul de $A^k$ est mécanique et programmable. Le programme de Mathématiques expertes l'utilise d'ailleurs pour étudier les chemins.²

Comment vérifier rapidement ma matrice d'adjacence ?

Teste trois points : la matrice est carrée de taille égale à l'ordre du graphe ; pour un graphe non orienté, elle est symétrique ; pour un graphe simple, la diagonale est nulle.⁴ Tu peux aussi comparer la somme d'une ligne au nombre de voisins du sommet (degré, hors boucles) dans un graphe non orienté simple.

Est-ce que $A^k$ donne les chemins de longueur au plus $k$ ?

Non : $A^k$ compte les chemins de longueur exactement $k$ .⁴ Pour « au plus $k$ », additionne $A$ , $A^2$ , ..., $A^k$ (et $A^0$ , la matrice identité, si les chemins de longueur nulle comptent). Lis bien le mot « exactement » ou « au plus » dans l'énoncé.

Quel est le lien avec les chaînes de Markov ?

Dans le cas d'un graphe probabiliste, la matrice qui remplace la matrice d'adjacence est la matrice de transition, ou stochastique.¹ Pour une chaîne de Markov, la probabilité de passer de l'état $i$ à l'état $j$ en plusieurs étapes s'exprime avec les puissances de cette matrice.² Ce cours en est donc l'introduction directe.

Sources

Ressources pédagogiques Éduscol - Graphes et matrices, Éduscol. Consulté le 6 novembre 2026.
Annexes du programme Mathématiques expertes, Éduscol. Consulté le 6 novembre 2026.
Travaux pratiques - Graphes et chemins, CNRS. Consulté le 6 novembre 2026.
Matrice d'adjacence, Wikipédia. Consulté le 6 novembre 2026.

Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.

Signaler une erreur sur cette page

Matrice d'adjacence et chemins : cours de Terminale (maths expertes)

L'essentiel

Pourquoi coder un graphe par un tableau de nombres

Définition de la matrice d'adjacence

Propriétés de la matrice d'adjacence

Chemins et puissances de la matrice

Méthode et calculs complets

Applications, lectures utiles et erreurs fréquentes

Exercices corrigés

Exercice 1 Compter des chemins dans un graphe non orienté

Exercice 2 Graphe orienté : tous les chemins de longueur 3

Exercice 3 Le cycle à quatre sommets et la parité

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur