Mathématiques expertes (option) · Terminale
Matrice d'adjacence et chemins : quiz de Terminale expertes
Publié le 6 novembre 2026 · Mis à jour le 6 novembre 2026 · Signaler une erreur
L'essentiel
- La matrice d'adjacence d'un graphe à n sommets est un tableau carré n × n, une fois l'ordre des sommets fixé 4.
- Pour un graphe simple, les coefficients sont uniquement 0 ou 1 et la diagonale est faite de zéros ; sans orientation, le tableau est symétrique 4.
- Le coefficient (i, j) de la puissance k de la matrice compte les parcours de longueur k de i à j 4.
- Pour un graphe probabiliste, on parle de matrice de transition ou de matrice stochastique 1.
Avant de commencer
Ce quiz porte sur deux idées liées. La première : traduire un graphe en un tableau de nombres, la matrice d'adjacence. La seconde : utiliser les puissances de cette matrice pour compter des chemins (on dit aussi des parcours). Tu as déjà vu les opérations sur les matrices et le vocabulaire des graphes, c'est tout ce qu'il faut.
Quiz
16 questions · correction immédiate · ton score reste sur ton appareil.
-
Une matrice d'adjacence d'un graphe fini à sommets est de dimension 4. Ici . La réponse « dépend du nombre d'arêtes » est tentante, mais les arêtes changent les valeurs des coefficients, pas la taille du tableau. Une matrice oublierait un sommet.
-
Le coefficient est le nombre d'arêtes liant à 4 ; dans un graphe simple il y a au plus une arête, donc la valeur est 1 si elle existe et 0 sinon. La valeur 2 supposerait deux arêtes distinctes entre les mêmes sommets. La longueur n'intervient pas dans une matrice d'adjacence non valuée.
-
C'est vrai : dans un graphe non orienté, une arête entre et se lit dans les deux sens, donc 4. L'erreur tentante est de croire que la symétrie vaut aussi pour un graphe orienté, où un arc de vers n'implique pas un arc de vers .
-
Un graphe simple n'a pas de boucle, et le coefficient compte les boucles au sommet ; la diagonale est donc nulle 4. Les degrés se lisent plutôt en sommant une ligne, pas en regardant la diagonale.
-
Chaque arête est comptée deux fois : une fois en position et une fois en position , car la matrice est symétrique 4. On obtient . Répondre 5 revient à oublier la symétrie.
-
C'est vrai. Une fois l'ordre des sommets fixé, il existe une matrice d'adjacence unique pour le graphe 4, mais un autre ordre donne en général un autre tableau. Le graphe, lui, reste le même. Penser que la matrice est unique sans condition est l'erreur fréquente.
-
C'est la propriété du cours : le coefficient de est le nombre de parcours de longueur exactement de à 4, et elle figure dans le programme de Mathématiques expertes 2. La troisième proposition est le piège : est un produit matriciel, pas une puissance terme à terme. La quatrième confond « nombre de parcours » et « plus courte distance ».
-
On calcule le coefficient de : ligne 1 par colonne 1, soit 4. Les deux parcours sont et . Répondre 0 vient de l'idée fausse qu'on ne peut pas revenir à son point de départ.
-
Le coefficient de vaut ligne 1 par colonne 2 : 4. Le seul parcours est . Passer par le sommet 2 en premier est impossible, car il faudrait ensuite une boucle en 2, qui n'existe pas.
-
Le coefficient de est 4. Deux sommets voisins sont reliés par un parcours de longueur 1, pas de longueur 2 : il faudrait revenir en arrière puis repartir, ce qui fait une longueur 3. Beaucoup d'élèves répondent 1 en confondant avec la matrice elle-même.
-
Ligne 1 par colonne 3 : 4. Il y a un seul parcours de longueur 2 de 1 à 3, à savoir . La réponse 0 prétend à tort que 1 et 3 ne sont pas liés, alors qu'ils le sont par l'intermédiaire de 2.
-
Le coefficient non diagonal est le nombre d'arêtes liant à 4. Avec deux arêtes, il vaut donc 2. La réponse 1 correspond au cas d'un graphe simple, qui ne s'applique pas ici.
-
Chaque 1 de la ligne marque une arête vers un autre sommet, et le graphe étant simple, il n'y a ni boucle ni arête multiple : on compte donc 3 arêtes issues du sommet, d'après la définition des coefficients 4. Il faut sommer la ligne, pas retenir sa longueur 4, qui est le nombre de sommets.
-
Dans ce cas particulier, la matrice est plus précisément appelée matrice de transition ou matrice stochastique 1. Ce sera l'outil central des chaînes de Markov, notion qui vient juste après dans ton parcours. La matrice d'incidence est une autre représentation, liée aux arêtes et non aux paires de sommets 3.
-
C'est vrai : dans un graphe orienté, la matrice n'est pas forcément symétrique, car un arc se lit dans un seul sens. La symétrie est une conséquence de l'absence d'orientation 4. L'erreur tentante est d'appliquer cette propriété à tous les graphes.
Les questions qu'on se pose
Pourquoi utiliser la matrice d'adjacence plutôt que le dessin du graphe ?
Le dessin est pratique pour de petits graphes, mais il ne se prête pas au calcul. Une fois le graphe traduit en matrice, on peut multiplier, et la puissance donne directement le nombre de parcours de longueur entre deux sommets 4. Cette représentation figure d'ailleurs parmi les exemples de représentations matricielles du programme de Mathématiques expertes 2.
Dois-je toujours calculer $A^k$ en entier pour répondre à une question sur un seul chemin ?
Non. Si on te demande le nombre de parcours de à , il suffit de lire le coefficient de 4. Pour , tu peux même calculer ce seul coefficient : ligne de multipliée par colonne de . Cela évite des erreurs sur les autres cases.
Que se passe-t-il si je change la numérotation des sommets ?
La matrice change en général, mais le graphe reste le même. Pour un ordre donné des sommets, la matrice est unique 4. Pense donc toujours à écrire l'ordre choisi en début de réponse, sinon la lecture d'un coefficient perd son sens.
Sources
- Ressources pédagogiques Éduscol - Graphes et matrices, Éduscol. Consulté le 6 novembre 2026.
- Annexes du programme Mathématiques expertes, Éduscol. Consulté le 6 novembre 2026.
- Travaux pratiques - Graphes et chemins, CNRS. Consulté le 6 novembre 2026.
- Matrice d'adjacence, Wikipédia. Consulté le 6 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.