Rédigé et vérifié par un professeur diplômé de l’École Polytechnique. Découvrir le professeur
La matrice d’adjacence d’un graphe à \(n\) sommets est une matrice carrée de taille \(n \times n\) dont le coefficient situé à la ligne \(i\) et à la colonne \(j\) indique si les sommets \(i\) et \(j\) sont reliés : il vaut \(1\) s’il existe une arête entre eux, et \(0\) sinon. C’est l’outil qui transforme un dessin en calcul.
En maths expertes, cet objet est au cœur du chapitre « Graphes et matrices » : il sert à compter des chemins grâce aux puissances de la matrice. Tu vas apprendre ici à la construire sans erreur, à distinguer les cas orienté et non orienté, à démontrer le théorème des chemins au programme, et à exploiter \(A^n\) en DS comme en prépa.
Au programme
- 🔵 Terminale – Maths expertes : chapitre « Graphes et matrices » (BO spécial n°8 du 25 juillet 2019). Démonstration au programme : les coefficients de \(A^n\) comptent les chemins de longueur \(n\).
- 🟠 Prépa ECG1 – Maths appliquées (BO spécial n°1 du 11 février 2021) : matrice d’adjacence, critère matriciel de connexité \(I + A + \dots + A^{n-1}\), graphes pondérés.
I. Définition et construction de la matrice d’adjacence
Un graphe se dessine avec des sommets (des points) reliés par des arêtes (des traits). Tant que le graphe est petit, le dessin suffit. Mais dès qu’on veut calculer, dessiner ne sert plus à rien : il faut traduire le graphe en nombres. C’est exactement le rôle de la matrice d’adjacence.
Définition — Matrice d’adjacence
Soit \(G\) un graphe non pondéré, sans arêtes multiples, dont les sommets sont numérotés de \(1\) à \(n\). La matrice d’adjacence de \(G\) est la matrice carrée \(A = (a_{i,j})\) de taille \(n \times n\) définie par :
\(a_{i,j} = 1\) s’il existe une arête reliant le sommet \(i\) au sommet \(j\), et \(a_{i,j} = 0\) sinon.
Prenons un graphe non orienté à quatre sommets pour fixer les idées : les sommets \(1, 2, 3, 4\) et les arêtes \(1\text{–}2\), \(1\text{–}3\), \(2\text{–}3\) et \(3\text{–}4\).
On construit la matrice ligne par ligne. À la ligne \(i\), on place un \(1\) dans chaque colonne correspondant à un voisin de \(i\). On obtient :
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 |
Remarque immédiate : la diagonale ne contient que des zéros, car aucun sommet n’est relié à lui-même (le graphe n’a pas de boucle). Et la matrice est symétrique : \(a_{i,j} = a_{j,i}\), parce qu’une arête entre \(i\) et \(j\) est aussi une arête entre \(j\) et \(i\). C’est une propriété de \(G\) non orienté qui rejoint la notion de matrice symétrique.
Ne pas confondre — trois matrices aux noms voisins
- Matrice d’adjacence \(A\) : décrit les arêtes du graphe (des \(0\) et des \(1\)).
- Matrice adjointe : transposée de la comatrice, utilisée pour inverser une matrice. Rien à voir avec les graphes, malgré le nom presque identique.
- Matrice laplacienne \(L = D- A\), où \(D\) est la matrice diagonale des degrés : c’est une autre représentation, plus avancée.
II. Graphe orienté ou non orienté : ce qui change dans la matrice
Tout repose sur une seule distinction. Dans un graphe non orienté, une arête se parcourt dans les deux sens : la matrice est symétrique. Dans un graphe orienté, chaque flèche (on parle d’arc) a un sens unique, et la matrice peut être non symétrique. Deux arcs réciproques peuvent toutefois conserver la symétrie.
Reprenons un petit graphe orienté à trois sommets avec les arcs \(1 \to 2\), \(1 \to 3\), \(2 \to 3\) et \(3 \to 1\). La règle de construction est la même, mais cette fois \(a_{i,j} = 1\) signifie « il existe un arc de \(i\) vers \(j\) ».
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 |
Ici \(a_{1,2} = 1\) (il y a un arc \(1 \to 2\)) mais \(a_{2,1} = 0\) (pas d’arc \(2 \to 1\)) : la matrice n’est pas symétrique. Retiens les implications suivantes :
- Un graphe non orienté a une matrice symétrique.
- Une matrice non symétrique impose un graphe orienté. Une matrice symétrique peut aussi représenter un graphe orienté dont chaque arc possède son arc réciproque.
Pour un graphe pondéré, on remplace les \(1\) par le poids de l’arête (une distance, une probabilité, un coût). C’est précisément ce qui relie la matrice d’adjacence aux chaînes de Markov, où chaque coefficient devient une probabilité de transition. On retrouve aussi ces familles dans notre page sur les types de graphes.
Attention : les puissances d’une matrice de poids additionnent des produits de poids, pas des nombres de chemins. De plus, si une boucle non orientée est codée par 1 sur la diagonale, elle compte deux fois dans le degré : il faut adapter la formule de somme de ligne.
La fiche-méthode « Matrice d’adjacence » en recto-verso
Construction, cas orienté / non orienté et puissances de A : tout le chapitre condensé sur une fiche à imprimer.
📄 Télécharger la fiche-méthode PDFPrête à glisser dans ton classeur avant le prochain DS.
III. Puissances de A et nombre de chemins
Voici la propriété qui fait tout l’intérêt de la matrice d’adjacence. Élever \(A\) à la puissance \(n\) ne sert pas à décorer : chaque coefficient de \(A^n\) compte un nombre de chemins. C’est le résultat central du chapitre, et la démonstration tombe régulièrement en DS.
A. Le théorème des chemins
Théorème — Nombre de chemins de longueur \(n\)
Soit \(A\) la matrice d’adjacence d’un graphe. Pour tout entier \(n \geq 1\), le coefficient situé ligne \(i\), colonne \(j\) de la matrice \(A^n\) est égal au nombre de chemins de longueur \(n\) reliant le sommet \(i\) au sommet \(j\) (les répétitions de sommets sont autorisées).
Un chemin de longueur \(n\) est une suite de \(n\) arêtes consécutives : on part de \(i\), on franchit \(n\) arêtes, on arrive en \(j\). Le calcul s’appuie sur le produit matriciel et sur les puissances d’une matrice.
B. Démonstration au programme (par récurrence)
Démonstration au programme. Notons \(N\) le nombre de sommets. On raisonne par récurrence sur la longueur \(n\), avec une propriété portant sur tous les couples de sommets.
Initialisation (\(n = 1\)). Par définition, \(a_{i,j} = 1\) s’il existe une arête de \(i\) à \(j\) et \(0\) sinon. Un chemin de longueur \(1\) est exactement une arête : le coefficient \((i,j)\) de \(A^1 = A\) compte bien le nombre de chemins de longueur \(1\). La propriété est vraie au rang \(1\), pour tous les couples de sommets.
Hérédité. Supposons que pour un entier \(n \geq 1\) et pour tous les sommets \(i,j\), le coefficient \((A^n)_{i,j}\) soit le nombre de chemins de longueur \(n\) de \(i\) à \(j\). Un chemin de longueur \(n+1\) de \(i\) à \(j\) se décompose de façon unique en un chemin de longueur \(n\) de \(i\) vers un sommet intermédiaire \(k\), suivi d’une arête de \(k\) à \(j\). Le nombre de tels chemins est donc :
\(\displaystyle\sum_{k=1}^{N} (A^n)_{i,k} \times a_{k,j}\)
Or cette somme est exactement le coefficient \((i,j)\) du produit \(A^n \times A = A^{n+1}\). La propriété est donc vraie au rang \(n+1\).
Conclusion. Par principe de récurrence, pour tout \(n \geq 1\), le coefficient \((A^n)_{i,j}\) compte les chemins de longueur \(n\) de \(i\) à \(j\). ∎
Ce que le correcteur attend sur cette démonstration
- Une initialisation explicite : relier « coefficient de \(A\) » et « chemin de longueur 1 ». Beaucoup l’oublient, c’est un point perdu bêtement.
- L’argument clé de l’hérédité : la décomposition d’un chemin de longueur \(n+1\) par son dernier sommet intermédiaire \(k\), qui fait apparaître la somme \(\sum_k (A^n)_{i,k} a_{k,j}\).
- Reconnaître explicitement cette somme comme le coefficient du produit matriciel \(A^n \times A\). C’est le cœur de la preuve.
C. Exemples résolus : lire A² et A³
Reprenons la matrice \(A\) du graphe à quatre sommets. En appliquant la règle du produit matriciel, on obtient :
| A² | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 2 | 1 | 1 | 1 |
| 2 | 1 | 2 | 1 | 1 |
| 3 | 1 | 1 | 3 | 0 |
| 4 | 1 | 1 | 0 | 1 |
Exemple 1 — chemins de longueur 2. Le coefficient \((A^2)_{1,4} = 1\) : il existe exactement un chemin de longueur 2 reliant \(1\) à \(4\), à savoir \(1\text{–}3\text{–}4\). On le vérifie à la main, ça colle.
Exemple 2 — la diagonale. Le coefficient \((A^2)_{3,3} = 3\) : il y a trois chemins de longueur 2 partant de \(3\) et y revenant, par les trois voisins de \(3\) (qui sont \(1\), \(2\) et \(4\)). On retrouve ici le degré du sommet \(3\) : dans un graphe simple non orienté, \((A^2)_{i,i}\) est toujours égal au degré de \(i\).
Exemple 3 — chemins de longueur 3. En calculant \(A^3 = A^2 \times A\), on trouve \((A^3)_{1,4} = 1\) : un seul chemin de longueur 3 relie \(1\) à \(4\), le chemin \(1\text{–}2\text{–}3\text{–}4\). Inutile de dessiner tous les chemins possibles : le calcul matriciel les compte pour toi.
IV. Méthode pas à pas et choix de la représentation
Voici la marche à suivre, applicable à tout exercice, qu’on te donne le dessin ou qu’on te demande de le lire à l’envers.
- Numérote les sommets de \(1\) à \(n\) et garde cette numérotation jusqu’à la fin. Changer l’ordre en cours de route est la première cause d’erreur.
- Oriente-toi. Le graphe est-il orienté ? Si oui, chaque arc compte dans son sens : la symétrie n’est pas garantie.
- Remplis ligne par ligne. À la ligne \(i\), mets un \(1\) dans chaque colonne \(j\) correspondant à un voisin de \(i\) (un arc \(i \to j\) si orienté), un \(0\) ailleurs.
- Vérifie. Non orienté ? La matrice doit être symétrique. Pas de boucle ? La diagonale est nulle. Dans le cas non orienté sans boucle, la somme d’une ligne donne le degré du sommet.
Mais quand faut-il vraiment passer par une matrice plutôt que garder le dessin ? Le tableau suivant positionne la matrice d’adjacence face aux autres représentations.
| Représentation | Quand l’utiliser | Atout | Limite |
|---|---|---|---|
| Dessin | Petit graphe, raisonnement visuel (connexité, cycle) | Intuitif, immédiat | Inexploitable pour calculer |
| Matrice d’adjacence | Compter des chemins, calculer avec \(A^n\), démontrer | Se prête au calcul matriciel | Lourde si beaucoup de sommets et peu d’arêtes |
| Liste d’adjacence | Programmation, parcours (NSI, prépa info) | Économe en mémoire pour un graphe creux | Pas de calcul matriciel direct |
| Matrice d’incidence | Relier sommets et arêtes individuellement | Visualise chaque arête | Rarement au programme lycée |
En clair : dès qu’un énoncé parle de « nombre de chemins » ou te demande de calculer \(A^2\), \(A^3\)…, la matrice d’adjacence est l’outil obligatoire. Pour la programmation, on bascule vers la liste d’adjacence, détaillée dans notre cours sur les graphes en Python.
V. Lire un graphe à partir de sa matrice
Jusqu’ici on partait du graphe. L’exercice inverse — retrouver des informations à partir de la seule matrice — est tout aussi fréquent au bac et en concours.
A. Degrés, boucles et sommets isolés
Sur une matrice d’adjacence d’un graphe non orienté :
- Dans un graphe non orienté sans boucle, le degré du sommet \(i\) est la somme des coefficients de la ligne \(i\) (nombre de ses voisins).
- Dans le cas non orienté, un sommet isolé correspond à une ligne entièrement nulle.
- Une boucle (sommet relié à lui-même) se lit par un \(1\) sur la diagonale.
B. Arêtes et triangles par la trace (culture)
Pour aller plus loin, la trace d’une matrice — la somme des coefficients diagonaux — livre deux informations élégantes sur un graphe simple non orienté :
- \(\mathrm{tr}(A^2)\) vaut deux fois le nombre d’arêtes du graphe.
- \(\displaystyle\frac{\mathrm{tr}(A^3)}{6}\) donne le nombre de triangles du graphe.
Une curiosité qui fait son effet en DS, et qui montre à quel point la matrice « sait » des choses que le dessin ne crie pas.
C. 🟠 Connexité : le critère matriciel (ECG1)
Critère matriciel de connexité 🟠 Prépa ECG1
Un graphe non orienté à \(n \geq 1\) sommets est connexe si et seulement si tous les coefficients de la matrice
\(I + A + A^2 + \dots + A^{n-1}\)
sont strictement positifs. En effet, le coefficient \((i,j)\) de cette somme compte les chemins de longueur \(0\) à \(n-1\) reliant \(i\) à \(j\) ; s’il existe un chemin entre deux sommets, il en existe un de longueur au plus \(n-1\).
Ce critère transforme une question visuelle (« peut-on relier tous les sommets ? ») en un calcul matriciel vérifiable. Pour la définition exacte et les méthodes manuelles, va voir notre page graphe connexe.
VI. 🟠 Prépa ECG : poids, spectre et graphes réguliers
En prépa, la matrice d’adjacence devient aussi un objet d’algèbre : on peut étudier ses valeurs propres, sa diagonalisation et les graphes réguliers.
- Graphes pondérés : les coefficients encodent des poids réels, ce qui relie directement la matrice d’adjacence à la matrice de transition d’une chaîne de Markov.
- Spectre : on étudie les valeurs propres de \(A\). Comme \(A\) est symétrique pour un graphe non orienté, elle est diagonalisable en base orthonormée. C’est l’occasion de relier le sujet aux valeurs propres et vecteurs propres et au procédé pour diagonaliser une matrice.
- Graphes réguliers : si tous les sommets ont le même degré \(d\), alors \(d\) est une valeur propre de \(A\), associée au vecteur dont toutes les composantes valent \(1\).
En rédaction : pour un graphe simple non orienté, la symétrie permet d’appliquer le théorème spectral. Ne confonds pas degré et valeur propre : dans un graphe régulier de degré \(d\), le vecteur dont toutes les composantes valent 1 est propre pour \(d\). Les autres valeurs propres ne sont pas, en général, des degrés.
VII. Ne pas confondre et erreurs fréquentes
Les fautes sur ce chapitre sont presque toujours les mêmes. Les voici, avec le diagnostic et la correction.
Erreur 1 — oublier la symétrie. ❌ On remplit \(a_{1,2} = 1\) mais on laisse \(a_{2,1} = 0\) dans un graphe non orienté.
Diagnostic : une arête non orientée se parcourt dans les deux sens. ✅ Dans un graphe non orienté, dès qu’on pose \(a_{i,j} = 1\), on pose aussi \(a_{j,i} = 1\). La matrice doit être symétrique.
Erreur 2 — confondre « longueur » et « valeur ». ❌ Lire \((A^3)_{1,4} = 1\) comme « un chemin de valeur 3 ».
Diagnostic : l’exposant \(3\) est la longueur du chemin (le nombre d’arêtes), pas une distance. ✅ \((A^n)_{i,j}\) est le nombre de chemins ; la longueur, c’est \(n\).
Erreur 3 — croire que \(A^n\) se lit comme \(A\) élément par élément. ❌ Calculer \(A^2\) en élevant chaque coefficient au carré.
Diagnostic : \(A^2 = A \times A\) est un produit matriciel, pas un carré terme à terme. ✅ Chaque coefficient de \(A^2\) est une somme de produits : \((A^2)_{i,j} = \sum_k a_{i,k}\, a_{k,j}\).
VIII. Exercices d’application
Quatre exercices classés par difficulté croissante, chacun corrigé en étapes. Essaie avant d’ouvrir la correction.
Exercice 1 — Construire la matrice ★
On considère un graphe non orienté à quatre sommets \(1, 2, 3, 4\) avec les arêtes \(1\text{–}2\), \(2\text{–}3\), \(3\text{–}4\) et \(4\text{–}1\). Écris sa matrice d’adjacence et donne le degré de chaque sommet.
Voir la correction de l’exercice 1
On remplit ligne par ligne. Le sommet \(1\) est voisin de \(2\) et \(4\), etc. :
\(A = \begin{pmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{pmatrix}\)La matrice est bien symétrique et de diagonale nulle. Chaque ligne contient deux \(1\) : tous les sommets ont pour degré \(2\) (le graphe est un cycle à quatre sommets, il est régulier).
Exercice 2 — Graphe orienté ★
Un graphe orienté à trois sommets a pour matrice d’adjacence \(A = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}\). Dessine ce graphe et explique pourquoi sa matrice n’est pas symétrique.
Voir la correction de l’exercice 2
On lit les arcs ligne par ligne : \(a_{1,2}=1\) donne \(1 \to 2\) ; \(a_{2,3}=1\) donne \(2 \to 3\) ; \(a_{3,1}=1\) et \(a_{3,2}=1\) donnent \(3 \to 1\) et \(3 \to 2\).
La matrice n’est pas symétrique (par exemple \(a_{1,2}=1\) mais \(a_{2,1}=0\)) : le graphe est orienté.
Exercice 3 — Compter des chemins ★★
On reprend le graphe du cours (sommets \(1,2,3,4\), arêtes \(1\text{–}2\), \(1\text{–}3\), \(2\text{–}3\), \(3\text{–}4\)). Combien existe-t-il de chemins de longueur \(2\) reliant le sommet \(1\) au sommet \(2\) ? Explicite-les.
Voir la correction de l’exercice 3
On lit le coefficient \((A^2)_{1,2}\). D’après le tableau de \(A^2\) du cours, \((A^2)_{1,2} = 1\).
Il existe donc un seul chemin de longueur 2 de \(1\) à \(2\). On le retrouve à la main : \(1\text{–}3\text{–}2\) (passage par le voisin commun \(3\)).
Ce qu’il faut rédiger : annoncer qu’on utilise le théorème des chemins, citer le coefficient \((A^2)_{1,2}\), puis conclure par la valeur.
Exercice 4 — Degré et nombre d’arêtes ★★★
Soit \(A\) la matrice d’adjacence d’un graphe simple non orienté à \(n\) sommets. Montre que la somme de tous les coefficients de \(A\) vaut le double du nombre d’arêtes du graphe.
Voir la correction de l’exercice 4
La somme de tous les coefficients vaut \(\displaystyle\sum_{i=1}^{n}\sum_{j=1}^{n} a_{i,j}\). Chaque arête reliant deux sommets \(i\) et \(j\) produit un \(1\) en position \((i,j)\) et un \(1\) en position \((j,i)\), par symétrie de la matrice.
Chaque arête est donc comptée exactement deux fois dans la somme. La somme totale des coefficients vaut donc \(2 \times (\text{nombre d'arêtes})\).
C’est l’écriture matricielle du lemme des poignées de main : la somme des degrés vaut le double du nombre d’arêtes.
IX. Questions fréquentes
Quelle est la différence entre matrice d’adjacence et matrice adjointe ?
Les noms se ressemblent mais ce sont deux objets sans aucun rapport. La matrice d’adjacence décrit un graphe : ses coefficients valent \(1\) ou \(0\) selon qu’il y a une arête ou non. La matrice adjointe est la transposée de la comatrice d’une matrice carrée, utilisée pour calculer un inverse. L’une relève de la théorie des graphes, l’autre du calcul matriciel classique.
Faut-il utiliser une matrice ou une liste d’adjacence ?
Tout dépend de l’objectif. Pour calculer (compter des chemins avec \(A^n\), démontrer une propriété), la matrice d’adjacence est idéale. Pour programmer un parcours de graphe, surtout si le graphe a beaucoup de sommets et peu d’arêtes, la liste d’adjacence est plus économe. On détaille ce choix dans le cours sur les graphes en Python.
Comment lit-on le nombre d’arêtes sur une matrice d’adjacence ?
Pour un graphe simple non orienté sans boucle, on additionne tous les coefficients de la matrice, puis on divise par \(2\) (chaque arête est comptée deux fois, en \((i,j)\) et en \((j,i)\)). Autrement dit, le nombre d’arêtes vaut la moitié de la somme des degrés.
Que signifie la diagonale d’une matrice d’adjacence ?
Un coefficient diagonal \(a_{i,i}\) indique si le sommet \(i\) est relié à lui-même, c’est-à-dire s’il porte une boucle. Dans un graphe simple sans boucle, la diagonale est entièrement nulle. En revanche, la diagonale de \(A^2\), elle, donne le degré de chaque sommet.
À quoi servent les puissances de la matrice d’adjacence ?
Elles comptent les chemins. Le coefficient \((i,j)\) de \(A^n\) donne le nombre de chemins de longueur \(n\) entre les sommets \(i\) et \(j\). C’est ce résultat qui permet d’étudier la connexité, de modéliser des déplacements, ou encore d’alimenter les chaînes de Markov et l’algorithme PageRank.
X. Pour aller plus loin
Tu sais désormais construire une matrice d’adjacence, l’élever à la puissance \(n\) pour compter des chemins et démontrer le théorème au programme. Pour prolonger :
- Inégalité de Markov : énoncé, démonstration et applications (du lycée à la prépa)
- Réussir les maths expertes en terminale et viser la prépa
- Arbre de Probabilité (Seconde) : Méthode et Exercices
- Combinatoire et Dénombrement : Cours Complet, Vocabulaire et Formules
Pour t’entraîner spécifiquement sur ce chapitre, va voir nos exercices corrigés de graphes en maths expertes.
