Lycée · Terminale · Maths expertes (option Tle)
Graphes — matrice d'adjacence et chemins
Représenter un graphe par une matrice, calculer la puissance d'une matrice pour compter les chemins (programme Maths expertes Terminale)
À propos de cette page
Calculatrice interdite · Tous les calculs doivent figurer sur la copie. Les résultats seront donnés sous la forme la plus simple possible.
Devoir surveillé de fin de chapitre, tout en niveau difficile. Travaille seul et sans aide, puis vérifie tes réponses avec le corrigé détaillé dépliable en bas de page.
Exercice 1 — Matrice d'adjacence d'un graphe non orienté
/ 4 pts- On considère le graphe non orienté $G$ à 4 sommets $\{A, B, C, D\}$ avec les arêtes : $\{A,B\}$, $\{A,D\}$, $\{B,C\}$, $\{C,D\}$, $\{B,D\}$.
- 1. Écrire la matrice d'adjacence $A$ de $G$ (en numérotant les sommets dans l'ordre A=1, B=2, C=3, D=4).
- 2. Vérifier que la matrice est symétrique.
- 3. Donner le degré de chaque sommet à partir de la matrice.
Exercice 2 — Calcul de $A^2$ et dénombrement de chemins
/ 5 pts- On reprend le graphe de l'exercice précédent avec $A = \begin{pmatrix}0&1&0&1\\1&0&1&1\\0&1&0&1\\1&1&1&0\end{pmatrix}$.
- 1. Calculer $A^2$ (produit matriciel).
- 2. Combien y a-t-il de chaînes de longueur 2 entre A et C ? Lesquelles ?
- 3. Combien y a-t-il de chaînes de longueur 2 entre B et B (retour au point de départ) ?
Exercice 3 — Graphe orienté et accessibilité
/ 5 pts- Soit le graphe orienté $G$ à 3 sommets avec la matrice $A = \begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}$.
- 1. Lister tous les arcs du graphe.
- 2. Calculer $A^2$.
- 3. Le sommet $s_2$ est-il accessible depuis $s_1$ en exactement 2 étapes ? Justifier.
- 4. Calculer $B_2 = A + A^2$ et interpréter le coefficient $(1,2)$ de $B_2$.
Exercice 4 — Connexité et fermeture transitive
/ 3 pts- On donne $B_2 = A + A^2 = \begin{pmatrix}0&1&1\\1&1&1\\1&2&1\end{pmatrix}$ pour un graphe orienté à 3 sommets.
- 1. Construire la matrice de fermeture transitive $T$ (binariser $B_2$).
- 2. $s_2$ peut-il atteindre lui-même ($t_{22}$) ? Que cela signifie-t-il pour le graphe ?
- 3. Le graphe est-il fortement connexe ? Justifier.
Exercice 5 — Problème de synthèse — Réseau de communication
/ 3 pts- Un réseau de 4 routeurs $\{R_1,R_2,R_3,R_4\}$ est modélisé par un graphe orienté avec la matrice :
- $A = \begin{pmatrix}0&1&1&0\\0&0&0&1\\0&1&0&0\\1&0&0&0\end{pmatrix}$
- 1. Combien y a-t-il de chemins de longueur 2 de $R_1$ à $R_4$ ?
- 2. En calculant $B_3 = A + A^2 + A^3$, déterminer si $R_3$ peut atteindre $R_4$ en au plus 3 sauts.
- 3. Ce réseau est-il fortement connexe ?
Corrigé détaillé — à n'ouvrir qu'après avoir rendu la copie
Exercice 1 — Matrice d'adjacence d'un graphe non orienté
1. $A = \begin{pmatrix}0&1&0&1\\1&0&1&1\\0&1&0&1\\1&1&1&0\end{pmatrix}$
2. On vérifie que $a_{ij}=a_{ji}$ pour tous $i,j$ : la matrice est bien symétrique (graphe non orienté).
3. Somme des lignes : $\deg(A)=2$, $\deg(B)=3$, $\deg(C)=2$, $\deg(D)=3$. Vérification : $\sum \deg = 10 = 2 \times 5$ arêtes.
Exercice 2 — Calcul de $A^2$ et dénombrement de chemins
1. $A^2 = A \times A$. Calcul ligne par ligne :
$(A^2)_{13}=(0)(0)+(1)(1)+(0)(0)+(1)(1)=0+1+0+1=2$
$(A^2)_{11}=(0)(0)+(1)(1)+(0)(0)+(1)(1)=2$, $(A^2)_{22}=(1)(1)+(0)(0)+(1)(1)+(1)(1)=3$, etc.
$$A^2=\begin{pmatrix}2&1&2&1\\1&3&1&2\\2&1&2&1\\1&2&1&3\end{pmatrix}$$
2. $(A^2)_{13}=2$ : 2 chaînes de longueur 2 entre A et C. Ce sont A→B→C et A→D→C.
3. $(A^2)_{22}=3$ : 3 chaînes de longueur 2 partant et revenant à B. Ce sont B→A→B, B→C→B, B→D→B (via chaque voisin de B).
Exercice 3 — Graphe orienté et accessibilité
1. Arcs : $1\to2$, $2\to3$, $3\to1$, $3\to2$.
2. $A^2 = \begin{pmatrix}0&0&1\\1&1&0\\0&1&1\end{pmatrix}$. Vérification : $(A^2)_{13}=0\cdot0+1\cdot1+0\cdot0=1$ (chemin $1\to2\to3$).
3. $(A^2)_{12}=0$ : il n'existe pas de chemin de longueur 2 de $s_1$ à $s_2$. En effet, depuis $s_1$, on atteint $s_2$ directement (longueur 1) ou on va en $s_3$ puis en $s_2$ (longueur 2 via $s_3$... mais $(A^2)_{12}=0+0+0=0$). Non, $s_2$ n'est pas accessible depuis $s_1$ en exactement 2 étapes.
4. $B_2 = A + A^2 = \begin{pmatrix}0&1&1\\1&1&1\\1&2&1\end{pmatrix}$. Le coefficient $(1,2)=1$ : il existe 1 chemin de longueur 1 ou 2 de $s_1$ à $s_2$ (l'arc direct $1\to2$).
Exercice 4 — Connexité et fermeture transitive
1. On remplace tout coefficient $\geq1$ par 1 :
$T = \begin{pmatrix}0&1&1\\1&1&1\\1&1&1\end{pmatrix}$
2. $t_{22}=1$ : $s_2$ peut se retrouver lui-même en 1 ou 2 étapes. Cela signifie qu'il existe un circuit passant par $s_2$ (par exemple $2\to3\to2$ de longueur 2).
3. Les coefficients hors-diagonale de $T$ : $t_{12}=t_{13}=t_{21}=t_{23}=t_{31}=t_{32}=1$. Tous sont égaux à 1, donc tout sommet atteint tout autre : le graphe est fortement connexe.
Exercice 5 — Problème de synthèse — Réseau de communication
1. $(A^2)_{14}=a_{11}\cdot a_{14}+a_{12}\cdot a_{24}+a_{13}\cdot a_{34}+a_{14}\cdot a_{44}=0+1\cdot1+1\cdot0+0=1$. Exactement 1 chemin de longueur 2 : $R_1\to R_2\to R_4$.
2. $A^2 = \begin{pmatrix}0&1&0&1\\1&0&0&0\\0&0&0&1\\0&1&1&0\end{pmatrix}$. $(A^2)_{34}=1$ : $R_3$ atteint $R_4$ en 2 sauts ($R_3\to R_2\to R_4$). Donc $(B_3)_{34}\geq1$ : oui, $R_3$ atteint $R_4$.
3. On calcule $A^3$ et $B_3$. Pour vérifier la forte connexité, on vérifie que $B_3$ a tous ses coefficients strictement positifs. Après calcul, $(B_3)_{24}=2\geq1$, $(B_3)_{42}=1\geq1$, etc. : le réseau est fortement connexe (chaque routeur peut atteindre tous les autres en au plus 3 sauts).
Ce contrôle de maths expertes (option tle) Terminale en bref
Un devoir surveillé type contrôle en classe sur « Graphes — matrice d'adjacence et chemins » : 5 exercices, 60 minutes, noté sur 20. Le corrigé détaillé est dépliable sous le sujet.
- Exercice 1 — Matrice d'adjacence d'un graphe non orienté/ 4 pts
- Exercice 2 — Calcul de $A^2$ et dénombrement de chemins/ 5 pts
- Exercice 3 — Graphe orienté et accessibilité/ 5 pts
- Exercice 4 — Connexité et fermeture transitive/ 3 pts
- Exercice 5 — Problème de synthèse — Réseau de communication/ 3 pts
Notions évaluées
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, Puissance $A^k$ et dénombrement des chemins, Connexité et accessibilité via la matrice.
Pour préparer ce contrôle
- Relire le cours.
- Refaire les exercices corrigés et les problèmes.
- Se tester avec le QCM (36 questions).
- Faire ce sujet en conditions réelles — 60 min, sans le cours — puis se corriger et noter les points à revoir.
Voir tous les contrôles de maths expertes (option tle) Terminale · tous les devoirs surveillés corrigés
Questions fréquentes sur ce sujet
- Combien de temps dure ce contrôle sur « Graphes — matrice d'adjacence et chemins » ?
- 60 minutes pour 5 exercices notés sur 20. Prévois le double si tu enchaînes avec la correction.
- Le corrigé est-il fourni ?
- Oui : le corrigé détaillé se déplie sous le sujet, à n'ouvrir qu'après avoir rendu la copie.
- Ce sujet peut-il servir de DS, de contrôle ou d'interrogation ?
- Oui : c'est un devoir surveillé complet de 60 minutes. Pour une interrogation courte, garde un ou deux exercices ; pour un DS ou un contrôle de fin de chapitre, fais le sujet entier en temps limité.
- Ce sujet suit-il le programme de maths expertes (option tle) de terminale ?
- Oui : il évalue uniquement les notions du chapitre « Graphes — matrice d'adjacence et chemins » du programme officiel de maths expertes (option tle) en terminale, soit 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.
Cours particuliers de maths expertes (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