Lycée · Terminale · Maths complémentaires (option Tle)
Matrices et graphes
Représenter et analyser des réseaux à l'aide de matrices et de la théorie des graphes (programme de l'option Maths complémentaires, Terminale générale)
À propos de cette page
Ce cours de maths complémentaires (option tle) en terminale sur « Matrices et graphes » suit le programme officiel de maths complémentaires (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 : Définitions et vocabulaire des matrices, Opérations sur les matrices : addition et multiplication par un scalaire, Produit de deux matrices, Vocabulaire des graphes. 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 complémentaires (option tle).
1
Définitions et vocabulaire des matrices
Une matrice est un tableau rectangulaire de nombres réels. On la note avec une lettre majuscule.
Définition. Une matrice à $m$ lignes et $n$ colonnes (de type $(m,n)$ ou de taille $m \times n$) est un tableau :
$$A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}$$Le coefficient situé à la ligne $i$ et à la colonne $j$ est noté $a_{ij}$.
$$A = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{pmatrix}$$Le coefficient situé à la ligne $i$ et à la colonne $j$ est noté $a_{ij}$.
Exemple. $A = \begin{pmatrix} 1 & 3 & -2 \\ 0 & 4 & 5 \end{pmatrix}$ est une matrice de type $(2,3)$. On a $a_{12} = 3$ et $a_{23} = 5$.
Quelques cas particuliers :
- Une matrice de type $(1,n)$ est appelée matrice ligne (ou vecteur ligne).
- Une matrice de type $(m,1)$ est appelée matrice colonne (ou vecteur colonne).
- Une matrice de type $(n,n)$ est dite matrice carrée d'ordre $n$.
- La matrice nulle, notée $O$, est une matrice dont tous les coefficients sont nuls.
Matrice identité. La matrice identité d'ordre $n$, notée $I_n$, est la matrice carrée d'ordre $n$ dont les coefficients diagonaux valent 1 et tous les autres 0 :
$$I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad I_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$
$$I_2 = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \quad I_3 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$
Astuce. Pour lire $a_{ij}$, pensez : d'abord la ligne $i$ (rangée horizontale), puis la colonne $j$ (rangée verticale). « Ligne avant colonne ».
2
Opérations sur les matrices : addition et multiplication par un scalaire
Addition de matrices. Deux matrices $A$ et $B$ sont additionnables si et seulement si elles ont le même type. Leur somme $A + B$ est la matrice de même type dont chaque coefficient est la somme des coefficients correspondants :
$$(A+B)_{ij} = a_{ij} + b_{ij}$$
$$(A+B)_{ij} = a_{ij} + b_{ij}$$
Exemple. $$\begin{pmatrix}2&-1\\3&0\end{pmatrix} + \begin{pmatrix}1&4\\-2&5\end{pmatrix} = \begin{pmatrix}3&3\\1&5\end{pmatrix}$$
Multiplication par un scalaire. Si $\lambda$ est un réel et $A$ une matrice, alors $\lambda A$ est la matrice obtenue en multipliant chaque coefficient de $A$ par $\lambda$ :
$$(\lambda A)_{ij} = \lambda \cdot a_{ij}$$
$$(\lambda A)_{ij} = \lambda \cdot a_{ij}$$
Exemple. $$3 \times \begin{pmatrix}1&2\\-1&0\end{pmatrix} = \begin{pmatrix}3&6\\-3&0\end{pmatrix}$$
Ces deux opérations vérifient les mêmes propriétés que pour les réels : commutativité de l'addition, associativité, distributivité du scalaire.
Attention ! On ne peut additionner que deux matrices du même type. Tenter d'additionner une matrice $2\times 2$ et une matrice $2 \times 3$ est une opération interdite.
3
Produit de deux matrices
Produit matriciel. Soient $A$ une matrice de type $(m,p)$ et $B$ une matrice de type $(p,n)$ (le nombre de colonnes de $A$ doit égaler le nombre de lignes de $B$). Leur produit $AB$ est la matrice de type $(m,n)$ définie par :
$$(AB)_{ij} = \sum_{k=1}^{p} a_{ik} \cdot b_{kj}$$C'est-à-dire : le coefficient $(i,j)$ est le produit scalaire de la ligne $i$ de $A$ par la colonne $j$ de $B$.
$$(AB)_{ij} = \sum_{k=1}^{p} a_{ik} \cdot b_{kj}$$C'est-à-dire : le coefficient $(i,j)$ est le produit scalaire de la ligne $i$ de $A$ par la colonne $j$ de $B$.
Exemple. $$A = \begin{pmatrix}1&2\\3&4\end{pmatrix}, \quad B = \begin{pmatrix}0&1\\-1&2\end{pmatrix}$$$$AB = \begin{pmatrix}1\cdot0+2\cdot(-1) & 1\cdot1+2\cdot2 \\ 3\cdot0+4\cdot(-1) & 3\cdot1+4\cdot2\end{pmatrix} = \begin{pmatrix}-2&5\\-4&11\end{pmatrix}$$
Attention ! Le produit matriciel n'est pas commutatif en général : $AB \neq BA$. De plus, $AB = 0$ n'implique pas que $A = 0$ ou $B = 0$.
Propriétés du produit matriciel :
- Associativité : $(AB)C = A(BC)$
- Distributivité : $A(B+C) = AB + AC$
- Élément neutre : $AI_n = I_m A = A$ pour toute matrice $A$ de type $(m,n)$
On définit la puissance d'une matrice carrée $A$ : $A^2 = AA$, $A^3 = A^2 A$, etc., et par convention $A^0 = I$.
Caption : Le produit AB n'est défini que si le nombre de colonnes de A (ici p) égale le nombre de lignes de B.
Méthode. Pour calculer $(AB)_{ij}$ : regardez la ligne $i$ de $A$ et la colonne $j$ de $B$, multipliez terme à terme et additionnez.
4
Vocabulaire des graphes
Graphe. Un graphe $G = (S, A)$ est la donnée d'un ensemble $S$ de sommets et d'un ensemble $A$ d'arêtes (ou d'arcs).
- Si les arêtes ont un sens (flèche), le graphe est dit orienté ; ses arêtes s'appellent des arcs.
- Si les arêtes n'ont pas de sens (pas de flèche), le graphe est dit non orienté.
Vocabulaire essentiel :
| Terme | Définition |
|---|---|
| Sommet | Nœud du graphe (noté $s_1, s_2, \ldots$) |
| Arête (non orienté) | Liaison entre deux sommets $\{s_i, s_j\}$ |
| Arc (orienté) | Liaison orientée de $s_i$ vers $s_j$, notée $(s_i, s_j)$ |
| Degré d'un sommet | Nombre d'arêtes (ou d'arcs) incidentes à ce sommet |
| Chemin | Suite de sommets consécutifs reliés par des arêtes/arcs |
| Longueur d'un chemin | Nombre d'arêtes (ou d'arcs) du chemin |
| Circuit / cycle | Chemin qui revient au sommet de départ |
| Graphe connexe | Tout sommet est relié à tout autre par au moins un chemin |
Exemple. Un réseau de villes reliées par des routes est un graphe : les villes sont les sommets, les routes sont les arêtes. Si on s'intéresse aux trajets aller seulement, le graphe est orienté.
Caption : Grandes familles de graphes étudiées en Terminale Maths complémentaires.
5
Matrice d'adjacence d'un graphe
Matrice d'adjacence. Soit $G$ un graphe à $n$ sommets numérotés $s_1, \ldots, s_n$. La matrice d'adjacence $M$ de $G$ est la matrice carrée d'ordre $n$ définie par :
$$m_{ij} = \text{nombre d'arcs de } s_i \text{ vers } s_j$$
$$m_{ij} = \text{nombre d'arcs de } s_i \text{ vers } s_j$$
En pratique, pour un graphe simple (sans boucle ni arête multiple) :
- $m_{ij} = 1$ s'il existe une arête/arc entre $s_i$ et $s_j$, $0$ sinon.
- Pour un graphe non orienté, la matrice est symétrique : $m_{ij} = m_{ji}$.
- Les coefficients diagonaux sont nuls s'il n'y a pas de boucle.
Exemple. Considérons le graphe orienté à 3 sommets $\{s_1, s_2, s_3\}$ avec les arcs : $s_1 \to s_2$, $s_1 \to s_3$, $s_2 \to s_3$, $s_3 \to s_1$.
La matrice d'adjacence est :
$$M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$La somme de la ligne $i$ donne le degré sortant de $s_i$ ; la somme de la colonne $j$ donne le degré entrant de $s_j$.
La matrice d'adjacence est :
$$M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$$La somme de la ligne $i$ donne le degré sortant de $s_i$ ; la somme de la colonne $j$ donne le degré entrant de $s_j$.
Astuce. Pour construire la matrice d'adjacence : la ligne $i$ correspond aux arcs partant de $s_i$. La colonne $j$ correspond aux arcs arrivant à $s_j$.
6
Puissances d'une matrice d'adjacence et chemins
Théorème fondamental. Soit $M$ la matrice d'adjacence d'un graphe à $n$ sommets. Le coefficient $(i,j)$ de la matrice $M^k$ (puissance $k$-ième de $M$) est égal au nombre de chemins de longueur $k$ allant du sommet $s_i$ au sommet $s_j$.
Exemple. Avec $M = \begin{pmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}$, calculons $M^2$ :
$$M^2 = \begin{pmatrix}0\cdot0+1\cdot0+1\cdot1 & 0\cdot1+1\cdot0+1\cdot0 & 0\cdot1+1\cdot1+1\cdot0 \\ 0\cdot0+0\cdot0+1\cdot1 & 0\cdot1+0\cdot0+1\cdot0 & 0\cdot1+0\cdot1+1\cdot0 \\ 0\cdot0+0\cdot0+0\cdot1 & 1\cdot1+0\cdot0+0\cdot0 & 1\cdot1+0\cdot1+0\cdot0\end{pmatrix}$$
$$= \begin{pmatrix}1&0&1\\1&0&0\\0&1&1\end{pmatrix}$$Le coefficient $(1,3)$ de $M^2$ vaut $1$ : il y a bien un chemin de longueur $2$ de $s_1$ à $s_3$ (le chemin $s_1 \to s_2 \to s_3$).
$$M^2 = \begin{pmatrix}0\cdot0+1\cdot0+1\cdot1 & 0\cdot1+1\cdot0+1\cdot0 & 0\cdot1+1\cdot1+1\cdot0 \\ 0\cdot0+0\cdot0+1\cdot1 & 0\cdot1+0\cdot0+1\cdot0 & 0\cdot1+0\cdot1+1\cdot0 \\ 0\cdot0+0\cdot0+0\cdot1 & 1\cdot1+0\cdot0+0\cdot0 & 1\cdot1+0\cdot1+0\cdot0\end{pmatrix}$$
$$= \begin{pmatrix}1&0&1\\1&0&0\\0&1&1\end{pmatrix}$$Le coefficient $(1,3)$ de $M^2$ vaut $1$ : il y a bien un chemin de longueur $2$ de $s_1$ à $s_3$ (le chemin $s_1 \to s_2 \to s_3$).
Pour savoir si $s_i$ et $s_j$ sont reliés par un chemin de longueur au plus $k$, on examine les coefficients correspondants de $M, M^2, \ldots, M^k$.
Astuce. La matrice $M + M^2 + \cdots + M^k$ donne en chaque coefficient $(i,j)$ le nombre total de chemins de longueur $1, 2, \ldots, k$ entre $s_i$ et $s_j$.
7
Applications aux réseaux et à la connexité
Les graphes et matrices trouvent de nombreuses applications concrètes :
| Application | Modélisation |
|---|---|
| Réseaux de communication | Sommets = utilisateurs ; arcs = liens de communication |
| Réseaux routiers | Sommets = villes ; arêtes = routes |
| Réseaux sociaux | Sommets = personnes ; arêtes = relations d'amitié |
| Pages web | Sommets = pages ; arcs = liens hypertextes |
Connexité. Un graphe non orienté est connexe si, pour toute paire de sommets $(s_i, s_j)$, il existe un chemin reliant $s_i$ à $s_j$. Un graphe orienté est dit fortement connexe si pour tout couple $(s_i, s_j)$, il existe un chemin orienté de $s_i$ vers $s_j$ ET de $s_j$ vers $s_i$.
Grâce aux puissances de la matrice d'adjacence $M$, on peut tester la connexité :
- Si tous les coefficients de $M + M^2 + \cdots + M^{n-1}$ (avec $n$ = nombre de sommets) sont strictement positifs, alors le graphe est fortement connexe.
- Si un coefficient reste nul, les sommets correspondants ne sont pas reliés.
Exemple — Réseau de diffusion. Dans un réseau de 4 personnes $(A, B, C, D)$, chacune peut transmettre une information à ses voisines directes. Représenter le réseau par un graphe permet de savoir si tout le monde peut être informé en au plus $k$ étapes, en lisant les coefficients de $M^k$.
Caption : Exemple de graphe cyclique à 4 sommets. Sa matrice d'adjacence est circulante.
Astuce. Dès que le nombre de sommets est grand, on préfère la matrice d'adjacence au dessin du graphe pour faire des calculs.
En bref
- Une matrice de type $(m,n)$ est un tableau de $m$ lignes et $n$ colonnes de réels.
- On peut additionner deux matrices de même type et multiplier par un scalaire terme à terme.
- Le produit $AB$ est défini si le nombre de colonnes de $A$ = nombre de lignes de $B$ ; il n'est pas commutatif.
- Un graphe est composé de sommets reliés par des arêtes (non orienté) ou des arcs (orienté).
- La matrice d'adjacence $M$ code les connexions du graphe : $m_{ij}=1$ s'il y a un arc de $i$ vers $j$.
- Le coefficient $(i,j)$ de $M^k$ donne le nombre de chemins de longueur $k$ de $s_i$ à $s_j$.
- Applications : réseaux de communication, réseaux routiers, détection de connexité.
Bloqué sur ce chapitre ?
Cours particuliers de maths complémentaires (option tle) à Marseille, en présentiel ou à distance — un prof qui s'adapte à ton rythme et reprend ce qui coince.
Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs