À propos de cette page
Ce cours de maths expertes (option tle) en terminale sur « Graphes — matrice d'adjacence et chemins » suit le programme officiel de maths expertes (option tle) de terminale. Il présente les définitions, les propriétés et les méthodes essentielles, accompagnées d'exemples résolus pour bien comprendre. Au programme : De la représentation graphique à la représentation matricielle, Matrice d'adjacence d'un graphe non orienté, Matrice d'adjacence d'un graphe orienté, Produit de matrices d'adjacence. Chaque notion est expliquée pas à pas, puis mise en pratique grâce à des exercices interactifs, un QCM et une évaluation corrigée. Idéal pour réviser à son rythme, combler ses lacunes et progresser, en autonomie ou avec un professeur. Cours rédigé par un professeur particulier à Marseille pour aider les élèves de terminale à réussir en maths expertes (option tle).
Au programme
1 · De la représentation graphique à la représentation matricielle
2 · Matrice d'adjacence d'un graphe non orienté
3 · Matrice d'adjacence d'un graphe orienté
4 · Produit de matrices d'adjacence
5 · Puissance $A^k$ et dénombrement des chemins
6 · Connexité et accessibilité via la matrice
7 · Algorithme de fermeture transitive (bonus)
1De la représentation graphique à la représentation matricielle
Un graphe $G = (S, A)$ est défini par un ensemble de sommets $S = \{s_1, s_2, \ldots, s_n\}$ et un ensemble d'arêtes (graphe non orienté) ou d'arcs (graphe orienté) $A$.
Jusqu'ici, on représentait un graphe par un dessin (points reliés par des traits). Cette représentation est utile mais difficile à traiter algorithmiquement. Pour les calculs, on lui préfère la matrice d'adjacence.
Pourquoi une matrice ? La représentation matricielle permet d'utiliser l'algèbre des matrices (produit, puissance) pour répondre à des questions combinatoires : combien y a-t-il de chemins de longueur $k$ entre deux sommets ?
On fixe un numérotage des sommets $s_1, s_2, \ldots, s_n$ (l'ordre n'a pas d'importance mais doit rester fixe dans tout le calcul).
Du dessin à l'outil algébrique : les étapes.
2Matrice d'adjacence d'un graphe non orienté
Définition. Soit $G$ un graphe non orienté à $n$ sommets $s_1,\ldots,s_n$. La matrice d'adjacence de $G$ est la matrice $A = (a_{ij})$ de taille $n \times n$ définie par :
$$a_{ij} = \begin{cases} 1 & \text{si } \{s_i, s_j\} \in A \\ 0 & \text{sinon} \end{cases}$$
Par convention, on pose $a_{ii} = 0$ (on ne considère pas les boucles dans le cadre du programme).
Attention ! La matrice d'adjacence d'un graphe non orienté est toujours symétrique ($a_{ij} = a_{ji}$), car une arête $\{s_i,s_j\}$ est à la fois de $i$ vers $j$ et de $j$ vers $i$.
Exemple. Graphe $G$ avec $S = \{1,2,3,4\}$ et arêtes $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{3,4\}$.
$$A = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$
La somme de la ligne $i$ donne le degré de $s_i$ : ici $\deg(1)=2$, $\deg(3)=3$.
Lecture de la matrice. La ligne $i$ liste les voisins de $s_i$ : là où $a_{ij}=1$, $s_j$ est voisin de $s_i$.
3Matrice d'adjacence d'un graphe orienté
Définition. Soit $G$ un graphe orienté à $n$ sommets. La matrice d'adjacence $A = (a_{ij})$ est définie par :
$$a_{ij} = \begin{cases} 1 & \text{si l'arc } (s_i \to s_j) \in A \\ 0 & \text{sinon} \end{cases}$$
Ici $a_{ij} \neq a_{ji}$ en général : la matrice n'est plus nécessairement symétrique.
Exemple. Graphe orienté $S=\{1,2,3\}$, arcs : $1\to2$, $1\to3$, $2\to3$, $3\to1$.
$$A = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$
Ligne $i$ : successeurs de $s_i$ ; colonne $j$ : prédécesseurs de $s_j$.
| Lecture | Signification |
|---|
| Ligne $i$ | Sommets que $s_i$ peut atteindre en un arc |
| Colonne $j$ | Sommets dont $s_j$ est l'extrémité (prédécesseurs) |
| Somme ligne $i$ | Demi-degré extérieur de $s_i$ |
| Somme colonne $j$ | Demi-degré intérieur de $s_j$ |
Demi-degrés extérieurs (somme des lignes) du graphe orienté exemple.
4Produit de matrices d'adjacence
Rappel : si $A = (a_{ij})$ et $B = (b_{ij})$ sont deux matrices $n \times n$, leur produit $C = AB$ vérifie :
$$c_{ij} = \sum_{k=1}^{n} a_{ik} \, b_{kj}$$
Propriété fondamentale. Le coefficient $(i,j)$ de la matrice $A^2 = A \times A$ est égal au nombre de chemins de longueur 2 du sommet $s_i$ vers le sommet $s_j$ dans $G$.
En effet, $c_{ij} = \sum_{k} a_{ik} a_{kj}$ : on somme sur tous les sommets intermédiaires $s_k$. Le terme $a_{ik} a_{kj}$ vaut 1 si et seulement si les arcs $s_i \to s_k$ et $s_k \to s_j$ existent tous les deux.
Exemple. Avec $A = \begin{pmatrix}0&1&1\\0&0&1\\1&0&0\end{pmatrix}$, on calcule :
$$A^2 = A \times A = \begin{pmatrix}1&0&1\\1&0&0\\0&1&1\end{pmatrix}$$
Le coefficient $(1,1)=1$ : il existe exactement 1 chemin de longueur 2 de $s_1$ à $s_1$ (via $s_3$ : $1\to3\to1$). Le coefficient $(1,3)=1$ : 1 chemin de longueur 2 de $s_1$ à $s_3$ (via $s_2$ : $1\to2\to3$).
Vérification. En listant explicitement les chemins de longueur 2, on retrouve bien les coefficients de $A^2$.
5Puissance $A^k$ et dénombrement des chemins
Théorème. Soit $A$ la matrice d'adjacence d'un graphe orienté (ou non orienté) à $n$ sommets. Le coefficient $(i,j)$ de $A^k$ est égal au nombre de chemins (ou de chaînes) de longueur $k$ du sommet $s_i$ vers le sommet $s_j$.
Attention ! Pour un graphe non orienté, un « chemin » au sens de la puissance de matrice est une chaîne (succession d'arêtes), pas nécessairement un chemin sans répétition de sommet. Les coefficients de $A^k$ comptent toutes les chaînes de longueur $k$, y compris celles qui repassent par un sommet déjà visité.
Pour trouver le nombre total de chemins de longueur au plus $k$ entre $s_i$ et $s_j$, on somme :
$$B_k = A + A^2 + \cdots + A^k$$
Le coefficient $(i,j)$ de $B_k$ est le nombre de chemins de longueur $1$ à $k$ de $s_i$ à $s_j$.
Exemple. Avec $A = \begin{pmatrix}0&1&1\\0&0&1\\1&0&0\end{pmatrix}$, on a calculé $A^2 = \begin{pmatrix}1&0&1\\1&0&0\\0&1&1\end{pmatrix}$. Calculons $A^3$ :
$$A^3 = A^2 \times A = \begin{pmatrix}1&0&1\\1&0&0\\0&1&1\end{pmatrix}\begin{pmatrix}0&1&1\\0&0&1\\1&0&0\end{pmatrix}=\begin{pmatrix}1&1&1\\0&1&1\\1&0&1\end{pmatrix}$$
Le coefficient $(1,2)$ de $A^3$ vaut 1 : il existe exactement 1 chemin de longueur 3 de $s_1$ à $s_2$.
Nombre total de chemins de longueur $k$ dans le graphe orienté exemple (somme de tous les coefficients de $A^k$).
6Connexité et accessibilité via la matrice
La matrice $B_k = A + A^2 + \cdots + A^k$ (à coefficients dans $\mathbb{N}$) permet de tester l'accessibilité entre deux sommets.
Propriété. $s_j$ est accessible depuis $s_i$ en au plus $k$ étapes si et seulement si le coefficient $(i,j)$ de $B_k$ est strictement positif.
Pour un graphe à $n$ sommets :
- Si le graphe est connexe (non orienté) ou fortement connexe (orienté), tous les coefficients de $B_{n-1}$ sont strictement positifs.
- On n'a pas besoin d'aller au-delà de $k = n-1$ : si un sommet est accessible, il l'est en au plus $n-1$ étapes (sinon il y aurait un cycle, et le chemin ne serait pas élémentaire).
Application pratique. Pour tester si $G$ est connexe, calculer $B_{n-1}$ et vérifier que tous ses coefficients hors-diagonale sont $\geq 1$ (pour un graphe non orienté, vérifier aussi la diagonale si besoin).
Attention ! Cette méthode est correcte mais coûteuse pour les grands graphes. En pratique, des algorithmes dédiés (BFS, DFS) sont préférés. En Maths expertes, on se limite à des graphes de petite taille.
7Algorithme de fermeture transitive (bonus)
La matrice booléenne d'accessibilité (ou matrice de fermeture transitive) $T = (t_{ij})$ est définie par :
$$t_{ij} = 1 \text{ si } s_j \text{ est accessible depuis } s_i \text{ (en ≥1 étape)}, \text{ sinon } 0$$
On l'obtient à partir de $B_{n-1}$ en remplaçant tout coefficient non nul par 1.
Exemple. Pour le graphe orienté $S=\{1,2,3\}$ ci-dessus, $B_2 = A + A^2 = \begin{pmatrix}1&1&2\\1&0&1\\1&1&1\end{pmatrix}$. En binarisant :
$$T = \begin{pmatrix}1&1&1\\1&0&1\\1&1&1\end{pmatrix}$$
Donc $s_2$ peut atteindre $s_1$ ($t_{21}=1$) et $s_3$ ($t_{23}=1$) mais pas lui-même directement ($t_{22}=0$).
L'algorithme de Warshall calcule efficacement cette fermeture transitive sans calculer toutes les puissances. Son principe est similaire à celui de Floyd-Warshall pour les plus courts chemins (hors programme mais utile à connaître).
★À retenir
À retenir :
• La matrice d'adjacence $A$ d'un graphe à $n$ sommets est une matrice $n\times n$ : $a_{ij}=1$ si l'arête (ou l'arc) $s_i \to s_j$ existe, $0$ sinon.
• Elle est symétrique pour un graphe non orienté.
• Le coefficient $(i,j)$ de $A^k$ = nombre de chemins de longueur $k$ de $s_i$ à $s_j$.
• Pour compter les chemins de longueur au plus $k$ : calculer $B_k = A + A^2 + \cdots + A^k$.
• Si un coefficient de $B_{n-1}$ est nul hors diagonale → les sommets correspondants ne sont pas connectés.