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
Choisis ton niveau. Questions et réponses mélangées à chaque partie. Bonne chance !
Les 36 questions du QCM en version texte
Pour réviser sans écran ou imprimer : chaque question avec ses propositions ; la bonne réponse et son explication se déplient.
Niveau facile — 12 questions
Que représente la matrice d'adjacence d'un graphe ?
- A. La distance entre deux sommets
- B. La relation d'adjacence entre sommets
- C. Le poids des arêtes
- D. Le degré de chaque sommet
Réponse
B. La relation d'adjacence entre sommets — La matrice d'adjacence code les liens directs entre sommets : $a_{ij}=1$ si l'arête (ou l'arc) $s_i$–$s_j$ existe.
La matrice d'adjacence d'un graphe non orienté à $n$ sommets est de taille :
- A. $1\times n$
- B. $n\times n$
- C. $n\times 1$
- D. $n\times 2$
Réponse
B. $n\times n$ — Elle est toujours carrée de taille $n\times n$, une ligne et une colonne par sommet.
Dans la matrice d'adjacence d'un graphe non orienté, $a_{ij}$ est toujours égal à :
- A. $a_{ii}$
- B. $a_{ji}$
- C. $0$
- D. $1$
Réponse
B. $a_{ji}$ — La matrice est symétrique : $a_{ij}=a_{ji}$ car une arête est non orientée.
Que vaut $a_{ii}$ (coefficient diagonal) si le graphe n'a pas de boucle ?
- A. 1
- B. 0
- C. $n$
- D. Indéfini
Réponse
B. 0 — Sans boucle, $a_{ii}=0$ : un sommet n'est pas adjacent à lui-même.
Si $A$ est la matrice d'adjacence, que représente la somme des éléments de la ligne $i$ ?
- A. Le nombre d'arcs
- B. Le degré de $s_i$
- C. Le nombre de composantes
- D. Le nombre de sommets
Réponse
B. Le degré de $s_i$ — La somme de la ligne $i$ donne le nombre de voisins de $s_i$, c'est-à-dire son degré.
Un graphe à 5 sommets a une matrice d'adjacence de taille :
- A. $4\times 4$
- B. $5\times 5$
- C. $5\times 4$
- D. $10\times 10$
Réponse
B. $5\times 5$ — $n=5$ sommets → matrice $5\times 5$.
Dans un graphe orienté, si $a_{12}=1$ et $a_{21}=0$, alors :
- A. Il y a une arête non orientée entre 1 et 2
- B. Il y a un arc de 1 vers 2 mais pas de 2 vers 1
- C. Il y a un arc de 2 vers 1 mais pas de 1 vers 2
- D. Les deux sommets sont isolés
Réponse
B. Il y a un arc de 1 vers 2 mais pas de 2 vers 1 — $a_{12}=1$ signifie arc $1\to2$ et $a_{21}=0$ signifie pas d'arc $2\to1$.
Le nombre total d'arêtes d'un graphe non orienté est égal à :
- A. La somme de tous les coefficients de $A$
- B. La moitié de la somme de tous les coefficients de $A$
- C. Le double de la somme des coefficients
- D. La trace de $A$
Réponse
B. La moitié de la somme de tous les coefficients de $A$ — Chaque arête $\{i,j\}$ contribue à $a_{ij}=1$ ET $a_{ji}=1$, donc on divise par 2.
Quelle est la valeur de $a_{ij}$ s'il n'existe pas d'arête entre $s_i$ et $s_j$ ?
- A. $-1$
- B. $0$
- C. Quelconque
- D. $n$
Réponse
B. $0$ — Par convention, $a_{ij}=0$ en l'absence d'arête ou d'arc.
Pour un graphe orienté, la matrice $A$ est-elle nécessairement symétrique ?
- A. Oui, toujours
- B. Non, pas nécessairement
- C. Oui, si le graphe est connexe
- D. Oui, si tous les sommets ont le même degré
Réponse
B. Non, pas nécessairement — Non : dans un graphe orienté, l'arc $s_i\to s_j$ peut exister sans que $s_j\to s_i$ existe.
Lire la colonne $j$ de la matrice d'adjacence d'un graphe orienté donne :
- A. Les successeurs de $s_j$
- B. Les prédécesseurs de $s_j$
- C. Les sommets de même degré que $s_j$
- D. Les arêtes incidentes à $s_j$
Réponse
B. Les prédécesseurs de $s_j$ — La colonne $j$ liste les sommets $s_i$ tels que l'arc $s_i\to s_j$ existe : ce sont les prédécesseurs de $s_j$.
Un graphe non orienté à 4 sommets sans arête a une matrice d'adjacence égale à :
- A. La matrice identité $I_4$
- B. La matrice nulle $O_4$
- C. Une matrice avec que des 1
- D. Une matrice avec que des $-1$
Réponse
B. La matrice nulle $O_4$ — Sans arête, tous les coefficients valent 0 : la matrice est la matrice nulle.
Niveau moyen — 12 questions
Que représente le coefficient $(i,j)$ de la matrice $A^2$ ?
- A. Le degré du sommet $i$
- B. Le nombre de chemins de longueur 2 de $s_i$ à $s_j$
- C. La distance entre $s_i$ et $s_j$
- D. Le poids de l'arête $\{i,j\}$
Réponse
B. Le nombre de chemins de longueur 2 de $s_i$ à $s_j$ — $(A^2)_{ij} = \sum_k a_{ik}a_{kj}$ = nombre de sommets intermédiaires par lesquels passer, i.e. chemins de longueur 2.
Le coefficient $(i,j)$ de $A^k$ représente :
- A. La $k$-ième puissance du degré de $s_i$
- B. Le nombre de chemins de longueur $k$ de $s_i$ à $s_j$
- C. La longueur du plus court chemin
- D. Le nombre de composantes connexes
Réponse
B. Le nombre de chemins de longueur $k$ de $s_i$ à $s_j$ — C'est le théorème fondamental : $(A^k)_{ij}$ = nombre de chemins (ou chaînes) de longueur $k$ entre $s_i$ et $s_j$.
Pour compter le nombre de chemins de longueur AU PLUS $k$ entre deux sommets, on utilise :
- A. $A^k$
- B. $A + A^2 + \cdots + A^k$
- C. $k \cdot A$
- D. $(A+I)^k$
Réponse
B. $A + A^2 + \cdots + A^k$ — On somme les matrices $A^1, A^2, \ldots, A^k$ pour couvrir toutes les longueurs de 1 à $k$.
Si $(A^3)_{12} = 5$, cela signifie qu'il y a :
- A. 5 sommets entre $s_1$ et $s_2$
- B. 5 chemins de longueur 3 de $s_1$ à $s_2$
- C. 5 arêtes entre $s_1$ et $s_2$
- D. 5 composantes connexes
Réponse
B. 5 chemins de longueur 3 de $s_1$ à $s_2$ — $(A^k)_{ij}$ = nombre de chemins de longueur $k$ entre $s_i$ et $s_j$.
Le produit de deux matrices d'adjacence $A \times B$ est défini par $c_{ij} = \sum_k a_{ik}b_{kj}$. Si $A=B$, le coefficient $(i,j)$ de $A^2$ est :
- A. $\sum_k a_{ik}+a_{kj}$
- B. $\sum_k a_{ik} \cdot a_{kj}$
- C. $a_{ij}^2$
- D. $2a_{ij}$
Réponse
B. $\sum_k a_{ik} \cdot a_{kj}$ — Produit matriciel standard : $(A^2)_{ij}=\sum_k a_{ik}a_{kj}$.
Un graphe à 4 sommets en cycle $1\to2\to3\to4\to1$ a pour matrice $A^4$ :
- A. $A$
- B. La matrice nulle
- C. La matrice identité $I_4$
- D. $4A$
Réponse
C. La matrice identité $I_4$ — Après 4 arcs dans un cycle de longueur 4, on revient toujours au sommet de départ : $A^4=I_4$.
Si $(A^2)_{ij}=0$, alors il n'existe pas de chemin de longueur ___ entre $s_i$ et $s_j$ :
- A. 1
- B. 2
- C. 3
- D. 4
Réponse
B. 2 — $(A^2)_{ij}=0$ signifie qu'il n'y a aucun chemin de longueur exactement 2 entre $s_i$ et $s_j$.
La trace de $A^2$ (somme des éléments diagonaux) pour un graphe non orienté est égale à :
- A. Au nombre de sommets
- B. Au nombre d'arêtes
- C. Au double du nombre d'arêtes
- D. Au carré du nombre de sommets
Réponse
C. Au double du nombre d'arêtes — $(A^2)_{ii}=\deg(s_i)$ pour un graphe non orienté, donc $\text{tr}(A^2) = \sum_i \deg(s_i) = 2|A|$ (double du nombre d'arêtes).
Si tous les coefficients hors-diagonale de $B_{n-1}=A+A^2+\cdots+A^{n-1}$ sont positifs, le graphe est :
- A. Eulériens
- B. Connexe (ou fortement connexe)
- C. Biparti
- D. Complet
Réponse
B. Connexe (ou fortement connexe) — Des coefficients strictement positifs signifient que tout sommet atteint tout autre, donc le graphe est connexe (ou fortement connexe si orienté).
Pour un graphe orienté, le demi-degré extérieur de $s_i$ est donné par :
- A. La somme de la colonne $i$ de $A$
- B. La somme de la ligne $i$ de $A$
- C. Le coefficient diagonal $a_{ii}$
- D. La trace de $A$
Réponse
B. La somme de la ligne $i$ de $A$ — La ligne $i$ liste les successeurs de $s_i$ : la somme donne le nombre d'arcs sortants.
Le coefficient $(i,j)$ de $A^k$ peut-il être supérieur à 1 ?
- A. Non, toujours 0 ou 1
- B. Oui, si plusieurs chemins de longueur $k$ existent
- C. Non, car $a_{ij}\in\{0,1\}$
- D. Oui, mais uniquement si $k\geq n$
Réponse
B. Oui, si plusieurs chemins de longueur $k$ existent — Oui : $(A^k)_{ij}$ compte le nombre de chemins de longueur $k$, qui peut être supérieur à 1.
Si $A$ est la matrice d'adjacence d'un graphe non orienté connexe à $n$ sommets, alors $A^{n-1}$ a :
- A. Tous ses coefficients nuls
- B. Tous ses coefficients strictement positifs
- C. Tous ses coefficients égaux à 1
- D. Une trace nulle
Réponse
B. Tous ses coefficients strictement positifs — Dans un graphe connexe, il existe toujours un chemin de longueur $\leq n-1$ entre deux sommets quelconques.
Niveau difficile — 12 questions
Soit $A$ la matrice d'adjacence d'un graphe simple non orienté. Que vaut $(A^2)_{ii}$ ?
- A. 0
- B. 1
- C. $\deg(s_i)$
- D. $n$
Réponse
C. $\deg(s_i)$ — $(A^2)_{ii}=\sum_k a_{ik}^2 = \sum_k a_{ik}$ (car $a_{ik}\in\{0,1\}$) $= \deg(s_i)$.
Pour un graphe $K_3$ (triangle complet non orienté), quelle est la valeur de $(A^2)_{11}$ ?
- A. 0
- B. 1
- C. 2
- D. 3
Réponse
C. 2 — $s_1$ a 2 voisins ($s_2$ et $s_3$), donc $(A^2)_{11}=\deg(s_1)=2$.
Si $A^k = O$ (matrice nulle) pour un certain $k$, que peut-on conclure sur le graphe orienté ?
- A. Il est complet
- B. Il est acyclique et donc DAG
- C. Il est fortement connexe
- D. Il a des boucles
Réponse
B. Il est acyclique et donc DAG — Si $A^k=O$, aucun chemin de longueur $k$ n'existe entre aucune paire de sommets : le graphe est acyclique (DAG).
La matrice de fermeture transitive $T$ est obtenue à partir de $B_{n-1}$ en :
- A. Transposant la matrice
- B. Remplaçant tout coefficient non nul par 1
- C. Ajoutant la matrice identité
- D. Divisant par $n$
Réponse
B. Remplaçant tout coefficient non nul par 1 — On binarise $B_{n-1}$ : 0 reste 0, tout entier $\geq1$ devient 1.
Quel est le lien entre la matrice d'adjacence $A$ et l'existence d'un chemin eulérien ?
- A. Tous les coefficients de $A^n$ doivent être 1
- B. Tous les sommets doivent avoir un degré pair (ou exactement 2 de degré impair)
- C. La trace de $A$ doit être nulle
- D. $A^2 = I$
Réponse
B. Tous les sommets doivent avoir un degré pair (ou exactement 2 de degré impair) — Un chemin eulérien existe si le graphe est connexe et si tous ses sommets ont un degré pair (circuit eulérien) ou exactement deux sommets de degré impair.
Pour un cycle orienté de longueur $p$ ($C_p$), que vaut $A^p$ ?
- A. $A$
- B. La matrice nulle
- C. La matrice identité $I_p$
- D. $p \cdot I_p$
Réponse
C. La matrice identité $I_p$ — Après $p$ arcs dans un cycle de longueur $p$, on revient toujours au point de départ : $A^p = I_p$.
Si $G$ est un graphe non orienté et $A$ sa matrice d'adjacence, alors $A$ est :
- A. Orthogonale
- B. Symétrique
- C. Anti-symétrique
- D. Diagonale
Réponse
B. Symétrique — $A=A^T$ car $a_{ij}=a_{ji}$ (arête non orientée).
Quel est le nombre de chemins de longueur 2 entre le sommet $i$ et lui-même dans un graphe non orienté ?
- A. 0
- B. 1
- C. $\deg(s_i)$
- D. $\deg(s_i)-1$
Réponse
C. $\deg(s_i)$ — $(A^2)_{ii}=\deg(s_i)$ : chaque voisin $s_k$ de $s_i$ offre un chemin $s_i\to s_k\to s_i$ de longueur 2.
Si la matrice d'adjacence $A$ d'un graphe orienté vérifie $A^3 \neq O$ mais $A^4 = O$, le graphe :
- A. Contient un cycle de longueur 3
- B. Est acyclique avec des chemins de longueur 3 au plus
- C. Est fortement connexe
- D. Admet un circuit eulérien
Réponse
B. Est acyclique avec des chemins de longueur 3 au plus — $A^k=O$ pour $k \geq 4$ signifie qu'aucun chemin de longueur $\geq4$ n'existe, mais il en existe de longueur 3 : DAG de profondeur 3.
Pour un graphe complet $K_n$ (non orienté, sans boucle), la matrice d'adjacence vérifie :
- A. $A=I_n$
- B. $A=J_n - I_n$ où $J_n$ est la matrice de 1
- C. $A=O_n$
- D. $A^2=A$
Réponse
B. $A=J_n - I_n$ où $J_n$ est la matrice de 1 — $K_n$ a toutes les arêtes sauf les boucles : $a_{ij}=1$ si $i\neq j$, 0 sinon, soit $A=J_n-I_n$.
Le coefficient $(i,j)$ de $A + A^2 + A^3$ est nul si et seulement si :
- A. $s_j$ n'est pas adjacent à $s_i$
- B. $s_j$ n'est pas accessible depuis $s_i$ en 1, 2 ou 3 étapes
- C. $s_j$ est adjacent à $s_i$
- D. $s_j$ est accessible en plus de 3 étapes seulement
Réponse
B. $s_j$ n'est pas accessible depuis $s_i$ en 1, 2 ou 3 étapes — $(B_3)_{ij}=0$ signifie qu'aucun des chemins de longueur 1, 2 ou 3 ne relie $s_i$ à $s_j$.
Si $G$ est un graphe biparti non orienté avec bipartition $(X, Y)$, alors $(A^2)_{ij}$ pour $s_i, s_j \in X$ :
- A. Vaut toujours 0
- B. Compte les voisins communs dans $Y$
- C. Vaut toujours 1
- D. Est négatif
Réponse
B. Compte les voisins communs dans $Y$ — Un chemin de longueur 2 de $s_i \in X$ à $s_j \in X$ passe obligatoirement par un sommet intermédiaire dans $Y$. Le coefficient compte ces voisins communs.
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