L'essentiel à connaître
Numérote les sommets de $1$ à $n$ : la matrice d'adjacence $M$ est le tableau $n \times n$ où $m_{ij} = 1$ si un arc va de $i$ à $j$ (une arête, si le graphe n'est pas orienté), et $m_{ij} = 0$ sinon. Un coefficient $m_{ii}$ non nul signale une boucle, une arête d'un sommet vers lui-même ; sans boucle, la somme de la ligne $i$ est le degré de $i$, son nombre de voisins.
Exemple : le graphe non orienté $G$ a pour sommets $1, 2, 3, 4$ et pour arêtes $\{1,2\}, \{1,3\}, \{2,3\}, \{3,4\}$. Sa matrice :
$$M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$
Elle est symétrique, sa diagonale est nulle, et la ligne 1 donne le degré de 1 : $0 + 1 + 1 + 0 = 2$.
Dans un graphe orienté, la ligne $i$ porte les arcs qui partent de $i$, la colonne $j$ ceux qui arrivent en $j$ : leurs sommes sont les degrés sortant $d_+(i)$ et entrant $d_-(j)$. La matrice est symétrique exactement quand chaque arc a son arc retour, toujours le cas sans orientation. Sa transposée $M^T$ (lignes et colonnes échangées) retourne tous les arcs. Renuméroter les sommets permute lignes et colonnes de la même façon.
À retenir : sans boucle, une arête $\{i,j\}$ s'écrit deux fois, en $m_{ij}$ et en $m_{ji}$. La matrice d'un graphe non orienté contient donc autant de $1$ que la somme des degrés, soit $2m$ pour $m$ arêtes.
Propriété : le coefficient $(i,j)$ de $M^k$ est le nombre de chemins de longueur exactement $k$ de $i$ à $j$, c'est-à-dire de suites de $k$ arêtes (ou arcs) qui s'enchaînent, en repassant au besoin par un même sommet (on dit aussi chaîne sans orientation). Ce résultat se démontre dès les mathématiques expertes de terminale. Sans orientation, $(M^2)_{ij}$ compte donc les voisins communs de $i$ et $j$ et, sans boucle, la trace de $M^3$ (somme de sa diagonale) compte chaque triangle six fois : trois départs, deux sens.
Côté machine, la matrice occupe $n^2$ cases, quel que soit le nombre $m$ d'arêtes. Tester si $i$ et $j$ sont voisins coûte $O(1)$, une case à lire. Lister les voisins de $i$ coûte $O(n)$, un temps proportionnel à $n$, car il faut lire toute la ligne. Les listes d'adjacence, l'autre représentation du programme d'informatique de MP2I et MPI, tiennent en $O(n + m)$.
Quiz : teste tes connaissances
Les questions qui citent $G$ ou $M$ reprennent l'exemple ci-dessus. Les trois dernières sont les plus piégeuses.
Question 1 : Dans $M$, que vaut $m_{24}$, et que t'apprend ce coefficient ?
Réponse : B. La ligne 2 vaut $(1, 0, 1, 0)$ : pas d'arête entre 2 et 4. Le piège A va trop loin : $M$ ne montre que les arêtes directes, et le chemin $2, 3, 4$ existe bien.
Question 2 : La matrice d'adjacence d'un graphe n'est pas symétrique. Que peux-tu affirmer ?
Réponse : D. Si $m_{ij} \neq m_{ji}$, un arc relie $i$ et $j$ dans un seul sens. Une boucle (A) se lit sur la diagonale, qui ne joue aucun rôle dans la symétrie.
Question 3 : Avec $M$, quel est le degré du sommet 3 ?
Réponse : C. La ligne 3 vaut $(1, 1, 0, 1)$, de somme $3$ : les voisins de 3 sont 1, 2 et 4. Le piège D ne lit que le triangle au-dessus de la diagonale, où la colonne 3 montre 1 et 2 mais pas 4.
Question 4 : Tous les coefficients diagonaux d'une matrice d'adjacence sont nuls. Qu'en déduis-tu ?
Réponse : A. Un $m_{ii}$ non nul code un arc de $i$ vers lui-même : une boucle. Un cycle, chemin qui revient à son départ comme $1, 2, 3, 1$ dans $G$, ne marque pas la diagonale de $M$ : il apparaît sur celle de $M^3$.
Question 5 : Quels arcs code la matrice $\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$ ?
Réponse : C. La ligne $i$ donne les arcs qui partent de $i$ : $1 \to 2$, puis $2 \to 3$, puis $3 \to 1$. La proposition B lit les colonnes comme des départs : c'est le graphe de la transposée, arcs à l'envers.
Question 6 : Un graphe orienté a pour matrice $N = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}$. Quels sont les degrés du sommet 2 ?
Réponse : B. La ligne 2, $(0, 0, 1, 0)$, porte un seul arc sortant, vers 3. La colonne 2, $(1, 0, 1, 0)$, en reçoit deux, depuis 1 et 3. La proposition A échange ligne et colonne.
Question 7 : Un graphe non orienté sans boucle a cinq sommets, de degrés $3, 3, 2, 2, 2$. Combien sa matrice contient-elle de $1$ ?
Réponse : A. Chaque ligne contient autant de $1$ que le degré de son sommet : $3 + 3 + 2 + 2 + 2 = 12$. Le piège B, $6$, compte les arêtes, alors que chacune s'écrit deux fois dans la matrice.
Question 8 : Que décrit la transposée $N^T$ de la matrice $N$ d'un graphe orienté ?
Réponse : D. Transposer échange $n_{ij}$ et $n_{ji}$ : l'arc $i \to j$ devient $j \to i$, et les boucles restent en place. Oublier les sens (B) donnerait une matrice symétrique, ce que $N^T$ n'est que si $N$ l'était déjà.
Question 9 : Avec $M$, que vaut $(M^2)_{14}$ ?
Réponse : B. $(M^2)_{14} = \sum_k m_{1k} m_{k4}$ compte les voisins communs de 1 et 4, donc les chemins $1, k, 4$ : seul $k = 3$ convient. Le piège A répond sur $M$ : 1 et 4 ne sont pas voisins, mais on cherche des chemins de longueur 2.
Question 10 : Un graphe a $n = 10\,000$ sommets et $m = 30\,000$ arêtes. Combien de cases occupe sa matrice d'adjacence ?
Réponse : D. La matrice a $n^2 = (10^4)^2 = 10^8$ cases, cent millions, quel que soit $m$. Le piège B, $n + m$, donne l'ordre de grandeur de la place prise par des listes d'adjacence.
Question 11 : Dans un graphe non orienté sans boucle, de matrice $M$, que vaut $(M^2)_{ii}$ ?
Réponse : C. Un chemin de longueur 2 de $i$ à $i$ est un aller-retour $i, v, i$ vers un voisin $v$ : il y en a un par voisin. Dans l'exemple, $(M^2)_{33} = 3$, le degré de 3. Le piège A oublie qu'un chemin peut revenir à son départ.
Question 12 : Tu échanges les numéros des sommets 1 et 2. Que fais-tu à la matrice ?
Réponse : A. Le sommet a une ligne (arcs sortants) et une colonne (arcs entrants) : son numéro change pour les deux. Échanger seulement les lignes de $M$ mettrait des $1$ en $(1,1)$ et $(2,2)$, deux fausses boucles.
Question 13 : Ton parcours en largeur (sommets visités par distance croissante depuis le départ) lit les voisins dans la matrice d'adjacence. Avec $n$ sommets et $m$ arêtes, quel est son coût ?
Réponse : D. Chaque sommet est traité une fois, et trouver ses voisins oblige à lire sa ligne entière, soit $n$ cases : $n \times n$ lectures au pire. Le $O(n + m)$ du cours (A) suppose des listes d'adjacence.
Question 14 : Dans l'exemple, $(M^2)_{34} = 0$. Que peux-tu en conclure ?
Réponse : B. $M^2$ ne compte que les chemins de longueur exactement 2, et 3 et 4 n'ont aucun voisin commun. Pourtant $m_{34} = 1$ : ils sont voisins. Pour savoir si deux sommets sont reliés, regarde $M, M^2, \dots, M^{n-1}$.
Question 15 : La trace de $M^3$ vaut $6$. Combien le graphe $G$ a-t-il de triangles ?
Réponse : C. Sans boucle, un chemin de longueur 3 qui revient à son départ fait le tour d'un triangle, et chaque triangle est compté $3 \times 2 = 6$ fois : trois départs, deux sens. Donc $6 / 6 = 1$, le triangle $1, 2, 3$. Diviser seulement par 3 (B) oublie les deux sens.
Sources
Programme d'informatique des classes préparatoires MP2I et MPI (ministère de l'Enseignement supérieur, 2021), partie « Structures de données relationnelles » : texte officiel.
Programme de mathématiques expertes de terminale générale (Bulletin officiel de l'Éducation nationale), partie « Graphes et matrices » : texte officiel.