Ressources · Terminale · Maths expertes (option Tle)

Matrice d’adjacence et chemins

Matrice d’adjacence d’un graphe orienté ou non ; degrés et nombre d’arêtes lus sur la matrice ; nombre de chemins de longueur k donné par Mᵏ, avec sa démonstration ; chemins fermés, triangles et coefficients nuls ; distance, diamètre et connexité.

À propos de cette page

Ce cours de maths expertes de Terminale relie graphes et matrices en cinq parties : écrire la matrice d’adjacence d’un graphe orienté ou non ; y lire les degrés et le nombre d’arêtes ; compter les chemins de longueur k avec Mᵏ, théorème démontré par récurrence ; interpréter la diagonale de M² et de M³ (degrés, triangles, circuits) ; distance, diamètre et connexité.

La matrice d’adjacence d’un graphe

Ce qu’il faut savoir

Matrice d’adjacence. Soit un graphe d’ordre $n$ dont les sommets sont rangés dans un ordre fixé et numérotés de $1$ à $n$ . Sa matrice d’adjacence est la matrice carrée $M = (m_{i j})$ de taille $n$ dont le coefficient $m_{i j}$ , ligne $i$ et colonne $j$ , est :

• pour un graphe non orienté, le nombre d’arêtes qui relient les sommets $i$ et $j$ ;
• pour un graphe orienté, le nombre d’arcs qui vont du sommet $i$ vers le sommet $j$ : la ligne est le départ, la colonne l’arrivée.

Graphe simple. Sans boucle ni arête multiple, tous les coefficients valent $0$ ou $1$ et la diagonale est nulle. Les graphes de ce chapitre sont sans boucle.

Symétrie. La matrice d’un graphe non orienté est symétrique : $m_{i j} = m_{j i}$ pour tous $i$ et $j$ , car l’arête qui relie $i$ à $j$ relie aussi $j$ à $i$ . Dans un graphe orienté, $m_{i j} = 1$ dit seulement que l’arc $i \to j$ existe : $m_{j i}$ peut valoir $0$ .

Graphe complet. La matrice de $K_{n}$ a tous ses coefficients égaux à $1$ , sauf ceux de la diagonale, nuls.

Ordre des sommets. La matrice dépend de l’ordre choisi : on l’écrit toujours à côté de $M$ . Changer l’ordre des sommets revient à permuter de la même façon les lignes et les colonnes.

Exemples

Un graphe non orienté. Le graphe ci-dessous a pour sommets A, B, C, D, rangés dans cet ordre.

Sa matrice d’adjacence est $M = (\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}) .$ La ligne $3$ se lit : C est relié à A, à B et à D. La matrice est symétrique, de diagonale nulle : le graphe est non orienté et sans boucle.

Un graphe orienté. Sommets $1$ , $2$ , $3$ et arcs $1 \to 2$ , $2 \to 1$ , $2 \to 3$ : $N = (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}) .$ $N$ n’est pas symétrique : $n_{23} = 1$ (l’arc $2 \to 3$ existe) mais $n_{32} = 0$ (l’arc $3 \to 2$ n’existe pas). Sa troisième ligne est nulle : aucun arc ne part du sommet $3$ .

Changer l’ordre. Si l’on range les sommets du premier graphe dans l’ordre D, C, B, A, la première ligne devient celle de D, soit $(0 1 0 0)$ : on retrouve la même information, rangée autrement.

Réflexe — J’écris l’ordre des sommets, puis je remplis la matrice ligne par ligne : la ligne $i$ contient les arêtes (ou les arcs) qui partent de $i$ . Je contrôle : matrice symétrique si le graphe n’est pas orienté, diagonale nulle s’il n’y a pas de boucle.

Attention — Le coefficient $m_{i j}$ se lit « de $i$ vers $j$ » : dans un graphe orienté, intervertir la ligne et la colonne change la réponse. Et deux matrices différentes peuvent représenter le même graphe, si l’ordre des sommets n’est pas le même.

1 / 5

Degrés et nombre d’arêtes sur la matrice

Ce qu’il faut savoir

Graphe non orienté sans boucle. La somme des coefficients de la ligne $i$ (ou de la colonne $i$ ) est le degré du sommet $i$ . La somme de tous les coefficients de $M$ vaut $2 m$ , où $m$ est le nombre d’arêtes : c’est le lemme des poignées de main lu sur la matrice.

Graphe orienté. La somme de la ligne $i$ est le degré sortant $d^{+} (i)$ ; la somme de la colonne $j$ est le degré entrant $d^{-} (j)$ ; la somme de tous les coefficients est le nombre d’arcs.

Graphe complet. Chaque ligne de la matrice de $K_{n}$ a pour somme $n - 1$ ; la somme totale vaut $n (n - 1)$ , soit le double des $\frac{n (n - 1)}{2}$ arêtes.

Exemples

Pourquoi $2 m$ . Dans un graphe non orienté, une arête entre $i$ et $j$ est comptée deux fois dans $M$ : une fois en $m_{i j}$ , une fois en $m_{j i}$ . La somme de tous les coefficients vaut donc le double du nombre d’arêtes. Dans un graphe orienté, l’arc $i \to j$ n’est compté qu’une fois, en $m_{i j}$ .

Avec la matrice $M$ du graphe de la partie précédente : la ligne $1$ donne $0 + 1 + 1 + 0 = 2$ , donc A est de degré $2$ . Les quatre lignes ont pour sommes $2$ , $2$ , $3$ et $1$ ; la somme totale vaut $8$ , donc le graphe a $8 \div 2 = 4$ arêtes, ce que confirme la liste A–B, A–C, B–C, C–D.

Un graphe orienté. Sommets P, Q, R, S, dans cet ordre.

$M' = (\begin{matrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{matrix})$ Les sommes des lignes donnent les degrés sortants : $d^{+} (P) = 2$ , $d^{+} (Q) = 1$ , $d^{+} (R) = 1$ , $d^{+} (S) = 2$ . Les sommes des colonnes donnent les degrés entrants : $d^{-} (P) = 1$ , $d^{-} (Q) = 2$ , $d^{-} (R) = 2$ , $d^{-} (S) = 1$ . La somme de tous les coefficients vaut $6$ : le graphe a $6$ arcs, sans division par $2$ . Sur le dessin, l’arc P → Q passe sous S sans le rencontrer : seuls comptent les arcs de la liste.

Réflexe — Degré d’un sommet : somme de sa ligne. Nombre d’arêtes d’un graphe non orienté : somme de tous les coefficients divisée par $2$ . Graphe orienté : la ligne donne le degré sortant, la colonne le degré entrant, et la somme totale le nombre d’arcs.

Attention — La division par $2$ ne vaut que pour un graphe non orienté. Dans un graphe orienté, la somme totale est directement le nombre d’arcs, et la somme d’une ligne n’est pas celle de la colonne correspondante.

2 / 5

Puissances de M : compter les chemins

Ce qu’il faut savoir

Longueur d’un chemin. La longueur d’un chemin (graphe orienté) ou d’une chaîne (graphe non orienté) est son nombre d’arcs ou d’arêtes, répétitions comprises : un chemin peut repasser par un sommet ou par une arête. Dans un graphe non orienté, chaque arête se parcourt dans les deux sens ; dans ce chapitre, on dit « chemin » dans les deux cas.

Rappel : produit de deux matrices carrées. Le coefficient ligne $i$ , colonne $j$ de $A B$ est la ligne $i$ de $A$ multipliée par la colonne $j$ de $B$ : $(A B)_{i j} = \sum_{r = 1}^{n} a_{i r} b_{r j} .$

Théorème. Soit $M$ la matrice d’adjacence d’un graphe dont les sommets sont numérotés de $1$ à $n$ , et $k$ un entier naturel non nul. Le coefficient ligne $i$ , colonne $j$ de $M^{k}$ , noté $(M^{k})_{i j}$ , est égal au nombre de chemins de longueur $k$ allant du sommet $i$ au sommet $j$ .

Exemples

Démonstration (exigible, par récurrence). Pour tout entier $k ⩾ 1$ , on note $P (k)$ la propriété : « pour tous $i$ et $j$ , $(M^{k})_{i j}$ est le nombre de chemins de longueur $k$ de $i$ à $j$ ».

Initialisation. $M^{1} = M$ , et $m_{i j}$ est par définition le nombre d’arcs de $i$ vers $j$ , c’est-à-dire le nombre de chemins de longueur $1$ de $i$ à $j$ : $P (1)$ est vraie.

Hérédité. Soit $k ⩾ 1$ tel que $P (k)$ est vraie. Un chemin de longueur $k + 1$ de $i$ à $j$ se découpe d’une seule façon en un chemin de longueur $k$ de $i$ jusqu’à un sommet $r$ (l’avant-dernier sommet), suivi d’un arc de $r$ vers $j$ . Pour un sommet $r$ fixé, il y a $(M^{k})_{i r}$ chemins pour la première partie, d’après $P (k)$ , et $m_{r j}$ arcs pour la seconde : soit $(M^{k})_{i r} \times m_{r j}$ chemins. En additionnant sur tous les sommets $r$ possibles, le nombre de chemins de longueur $k + 1$ de $i$ à $j$ vaut $\sum_{r = 1}^{n} (M^{k})_{i r} m_{r j},$ qui est exactement le coefficient ligne $i$ , colonne $j$ du produit $M^{k} \times M = M^{k + 1}$ : $P (k + 1)$ est vraie.

Conclusion. $P (1)$ est vraie et la propriété est héréditaire : par récurrence, $P (k)$ est vraie pour tout entier $k ⩾ 1$ .

Exemple. Avec le graphe A, B, C, D de la première partie, $M^{2} = (\begin{matrix} 2 & 1 & 1 & 1 \\ 1 & 2 & 1 & 1 \\ 1 & 1 & 3 & 0 \\ 1 & 1 & 0 & 1 \end{matrix}) et M^{3} = (\begin{matrix} 2 & 3 & 4 & 1 \\ 3 & 2 & 4 & 1 \\ 4 & 4 & 2 & 3 \\ 1 & 1 & 3 & 0 \end{matrix}) .$ $(M^{2})_{33} = 3$ : il y a trois chemins de longueur $2$ de C à C, à savoir C–A–C, C–B–C et C–D–C. $(M^{3})_{14} = 1$ : le seul chemin de longueur $3$ de A à D est A–B–C–D.

Un seul coefficient. Inutile de tout calculer : $(M^{4})_{14}$ est la ligne $1$ de $M^{3}$ multipliée par la colonne $4$ de $M$ , soit $2 \times 0 + 3 \times 0 + 4 \times 1 + 1 \times 0$ $= 4$ : il y a $4$ chemins de longueur $4$ de A à D.

Deux raccourcis. Comme $M^{2} = M \times M$ , la ligne $i$ de $M^{2}$ est la somme des lignes de $M$ des voisins de $i$ : D n’a qu’un voisin, C, donc la ligne $4$ de $M^{2}$ est la ligne $3$ de $M$ , $(1 1 0 1)$ . Et $M^{p + q} = M^{p} \times M^{q}$ : on obtient $M^{6}$ en élevant $M^{3}$ au carré. À la calculatrice, on entre $M$ puis on calcule directement $M^{k}$ .

Réflexe — Pour compter les chemins de longueur $k$ de $i$ à $j$ , je lis le coefficient ligne $i$ , colonne $j$ de $M^{k}$ et je cite le théorème. S’il ne faut qu’un coefficient, je multiplie une ligne par une colonne.

Attention — $M^{2}$ n’est pas la matrice des carrés des coefficients : $(M^{2})_{i j}$ se calcule par un produit ligne par colonne. Et les chemins comptés peuvent repasser par un même sommet ou une même arête : A–B–A–B est un chemin de longueur $3$ de A à B.

3 / 5

Chemins fermés, triangles et coefficients nuls

Ce qu’il faut savoir

Coefficients diagonaux. $(M^{k})_{i i}$ est le nombre de chemins fermés de longueur $k$ qui partent du sommet $i$ et y reviennent.

Graphe non orienté simple. $(M^{2})_{i i}$ est le degré de $i$ : un chemin fermé de longueur $2$ est un aller-retour vers un voisin. $(M^{3})_{i i}$ vaut le double du nombre de triangles qui contiennent $i$ : chaque triangle se parcourt dans deux sens. La somme des coefficients diagonaux de $M^{3}$ (on l’appelle la trace de $M^{3}$ ) vaut donc $6$ fois le nombre de triangles du graphe : trois sommets de départ, deux sens.

Graphe orienté sans boucle. $(M^{3})_{i i}$ est le nombre de circuits de longueur $3$ passant par $i$ ; la somme des coefficients diagonaux de $M^{3}$ vaut $3$ fois le nombre de ces circuits.

Coefficients nuls. $(M^{k})_{i j} = 0$ signifie qu’aucun chemin de longueur $k$ ne va de $i$ à $j$ . Si les sommets se partagent en deux groupes et que chaque arête relie un sommet d’un groupe à un sommet de l’autre, tout chemin change de groupe à chaque pas : un chemin de longueur impaire relie deux groupes différents, un chemin de longueur paire reste dans le même groupe.

Exemples

Une maison. Sommets A, B, C, D, E, dans cet ordre.

$M^{2} = (\begin{matrix} 3 & 1 & 2 & 0 & 1 \\ 1 & 3 & 0 & 2 & 1 \\ 2 & 0 & 2 & 0 & 1 \\ 0 & 2 & 0 & 2 & 1 \\ 1 & 1 & 1 & 1 & 2 \end{matrix}), M^{3} = (\begin{matrix} 2 & 6 & 1 & 5 & 4 \\ 6 & 2 & 5 & 1 & 4 \\ 1 & 5 & 0 & 4 & 2 \\ 5 & 1 & 4 & 0 & 2 \\ 4 & 4 & 2 & 2 & 2 \end{matrix}) .$ La diagonale de $M^{2}$ , $(3, 3, 2, 2, 2)$ , donne les degrés ; sa somme $12$ est le double des $6$ arêtes. La diagonale de $M^{3}$ vaut $(2, 2, 0, 0, 2)$ , de somme $6$ : le graphe a $6 \div 6 = 1$ triangle, A–B–E. $(M^{3})_{33} = 0$ : C n’appartient à aucun triangle.

Deux groupes. La grille d’arêtes 1–2, 2–3, 4–5, 5–6, 1–4, 2–5, 3–6 a ses sommets répartis en ${1, 3, 5}$ et ${2, 4, 6}$ , et chaque arête relie les deux groupes. Donc $(M^{3})_{13} = 0$ et $(M^{2})_{12} = 0$ , sans aucun calcul : aucun chemin de longueur impaire ne relie $1$ à $3$ , aucun chemin de longueur paire ne relie $1$ à $2$ . En particulier, la grille n’a aucun triangle.

Un graphe orienté. Arcs $1 \to 2$ , $2 \to 3$ , $3 \to 1$ , $3 \to 4$ , $4 \to 1$ : la diagonale de $M^{3}$ vaut $(1, 1, 1, 0)$ , de somme $3$ , et le graphe a un seul circuit de longueur $3$ , $1 \to 2 \to 3 \to 1$ , compté une fois depuis chacun de ses trois sommets. La diagonale de $M^{4}$ vaut $(1, 1, 1, 1)$ : c’est le circuit $1 \to 2 \to 3 \to 4 \to 1$ , vu depuis ses quatre sommets.

Réflexe — Diagonale de $M^{k}$ = chemins fermés. Nombre de triangles d’un graphe non orienté simple : somme de la diagonale de $M^{3}$ divisée par $6$ . Nombre de circuits de longueur $3$ d’un graphe orienté : divisée par $3$ .

Attention — Les chemins fermés comptés peuvent être des allers-retours : $(M^{4})_{i i}$ compte aussi $i$ – $a$ – $i$ – $b$ – $i$ , ce n’est pas le nombre de cycles de longueur $4$ . Seule la longueur $3$ donne directement des triangles, car un chemin fermé de longueur $3$ sans boucle passe par trois sommets distincts.

4 / 5

Distance, diamètre et connexité

Ce qu’il faut savoir

Existence d’un chemin. Il existe un chemin de longueur $k$ de $i$ à $j$ si et seulement si $(M^{k})_{i j} > 0$ .

Distance. Pour deux sommets distincts $i$ et $j$ , la distance $d (i; j)$ est la plus petite longueur d’un chemin de $i$ à $j$ : c’est le plus petit entier $k ⩾ 1$ tel que $(M^{k})_{i j} > 0$ . Dans un graphe orienté, $d (i; j)$ et $d (j; i)$ peuvent différer. (Ne pas confondre avec le degré $d (s)$ , qui ne porte que sur un sommet.)

Diamètre. Le diamètre d’un graphe connexe (fortement connexe s’il est orienté) est la plus grande distance entre deux de ses sommets. Pour le trouver, on cherche, pour chaque sommet, sa plus grande distance aux autres, puis le maximum de ces valeurs.

Connexité. Un graphe orienté est fortement connexe lorsque, pour tous sommets distincts $i$ et $j$ , il existe un chemin de $i$ vers $j$ . Un graphe d’ordre $n ⩾ 2$ est connexe (fortement connexe s’il est orienté) si et seulement si tous les coefficients hors de la diagonale de $S = M + M^{2} + \dots + M^{n - 1}$ sont non nuls.

Exemples

Pourquoi s’arrêter à $M^{n - 1}$ . Un plus court chemin de $i$ à $j$ ne passe jamais deux fois par le même sommet : sinon, en supprimant la portion entre les deux passages, on obtiendrait un chemin plus court. Il visite donc au plus $n$ sommets distincts, et compte au plus $n - 1$ arcs. Deux sommets reliés par un chemin le sont donc par un chemin de longueur au plus $n - 1$ : $d (i; j) ⩽ n - 1$ .

Distances du graphe A, B, C, D. La matrice $M$ donne $d (A; B)$ $= d (A; C)$ $= d (B; C)$ $= d (C; D)$ $= 1$ . $(M)_{14} = 0$ et $(M^{2})_{14} = 1$ , donc $d (A; D) = 2$ ; de même $d (B; D) = 2$ . Le diamètre vaut $2$ .

Un graphe orienté. Arcs X → Y, Y → Z, Z → Y, Z → T et T → X, sommets dans l’ordre X, Y, Z, T. Il est d’ordre $4$ , on calcule donc $S = M + M^{2} + M^{3} = (\begin{matrix} 0 & 2 & 1 & 1 \\ 1 & 1 & 2 & 1 \\ 1 & 3 & 1 & 2 \\ 1 & 1 & 1 & 0 \end{matrix}) .$ Tous les coefficients hors de la diagonale sont non nuls : le graphe est fortement connexe. Pour X vers T, le coefficient ligne $1$ , colonne $4$ vaut $0$ dans $M$ , $0$ dans $M^{2}$ et $1$ dans $M^{3}$ : $d (X; T) = 3$ , par X → Y → Z → T. En sens inverse, $d (T; X) = 1$ .

Réflexe — Pour une distance, je lis le coefficient $(i; j)$ dans $M$ , $M^{2}$ , $M^{3}$ … dans cet ordre et je m’arrête au premier qui n’est pas nul. Pour la connexité, je calcule $S$ jusqu’à $M^{n - 1}$ et je regarde les coefficients hors de la diagonale.

Attention — $(M^{3})_{i j} > 0$ ne prouve pas que $d (i; j) = 3$ : la distance peut valoir $1$ ou $2$ , il faut regarder les puissances inférieures. Et un coefficient nul dans $M + M^{2} + M^{3}$ ne prouve rien pour un graphe d’ordre $5$ : il faut aller jusqu’à $M^{4}$ .

5 / 5

Pour aller plus loin

Vocabulaire des graphes. Sommets, arêtes, degré, chaînes, cycles, connexité et théorème d’Euler : chapitre Vocabulaire et propriétés.

Graphes probabilistes. Quand chaque arc porte une probabilité, la matrice d’adjacence est remplacée par la matrice de transition $P$ , et le coefficient $(i; j)$ de $P^{n}$ est une probabilité : chapitre Graphes probabilistes et chaînes de Markov.

Suites de matrices. Quand $M^{2}$ s’écrit à l’aide de $M$ et de la matrice identité, les puissances de $M$ se calculent par des suites récurrentes : chapitre Suites de matrices.

Pour aller plus loin (hors programme de maths expertes). Dans un graphe pondéré, chaque arête porte un nombre positif, son poids (une distance, une durée, un coût) ; le poids d’une chaîne est la somme des poids de ses arêtes. L’algorithme de Dijkstra trouve une chaîne de poids minimal entre deux sommets, à condition que les poids soient positifs : on part du sommet de départ (valeur $0$ ), on marque à chaque étape le sommet de plus petite valeur provisoire, puis on met à jour ses voisins. Une chaîne de poids minimal n’a pas forcément le moins d’arêtes : les puissances de $M$ comptent les arêtes, Dijkstra additionne les poids.

À retenir

Matrice d’adjacence : $m_{i j}$ = nombre d’arêtes entre $i$ et $j$ , ou d’arcs de $i$ vers $j$ ; symétrique si le graphe n’est pas orienté ; l’ordre des sommets est toujours écrit.
Somme d’une ligne = degré (degré sortant si orienté), d’une colonne = degré entrant ; somme totale = $2 m$ (non orienté) ou nombre d’arcs (orienté).
Théorème (démonstration exigible) : $(M^{k})_{i j}$ est le nombre de chemins de longueur $k$ de $i$ à $j$ ; un seul coefficient = une ligne multipliée par une colonne.
Diagonale de $M^{k}$ = chemins fermés ; $(M^{2})_{i i}$ = degré ; trace de $M^{3}$ = $6$ × nombre de triangles (non orienté), $3$ × nombre de circuits de longueur $3$ (orienté).
Distance = plus petit $k$ tel que $(M^{k})_{i j} > 0$ ; diamètre = plus grande distance ; connexe si $M + M^{2} + \dots + M^{n - 1}$ n’a aucun zéro hors de la diagonale.

Questions fréquentes

Qu’est-ce que la matrice d’adjacence d’un graphe ?

C’est la matrice carrée dont le coefficient ligne i, colonne j est le nombre d’arêtes entre les sommets i et j (ou d’arcs de i vers j si le graphe est orienté). Elle dépend de l’ordre choisi pour les sommets, et elle est symétrique quand le graphe n’est pas orienté.

Comment lire les degrés sur la matrice d’adjacence ?

Pour un graphe non orienté, la somme de la ligne i est le degré du sommet i, et la somme de tous les coefficients vaut le double du nombre d’arêtes. Pour un graphe orienté, la ligne donne le degré sortant, la colonne le degré entrant, et la somme totale le nombre d’arcs.

Comment compter les chemins de longueur n dans un graphe ?

Le coefficient ligne i, colonne j de la puissance Mⁿ de la matrice d’adjacence est le nombre de chemins de longueur n de i à j. Cela se démontre par récurrence sur n, à partir de la définition du produit de matrices. Pour un seul coefficient, on multiplie une ligne par une colonne.

Comment compter les triangles d’un graphe avec sa matrice ?

Dans un graphe non orienté simple, la somme des coefficients diagonaux de M³ vaut six fois le nombre de triangles, car chaque triangle est parcouru depuis trois sommets et dans deux sens. Les coefficients diagonaux de M², eux, sont les degrés.

Comment trouver la distance entre deux sommets avec les puissances de M ?

La distance de i à j est la plus petite puissance k telle que le coefficient (i ; j) de Mᵏ n’est pas nul. Un graphe d’ordre n est connexe si la somme M + M² + … + Mⁿ⁻¹ n’a aucun coefficient nul hors de sa diagonale.

Bloqué sur ce chapitre ?

Moi c'est Ben, j'ai créé ce site pour aider le plus d'élèves possible, partout en France. Je peux aussi reprendre avec toi ce qui coince en cours particulier : en visio, ou à domicile si tu es à Marseille.

Réserver un 1^er cours → Voir les tarifs

Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs