Matrice d'adjacence et chemins : fiche 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 : le coefficient aij compte les arêtes qui relient le sommet i au sommet j4.
Pour un graphe simple, la matrice ne contient que des 0 et des 1, avec des 0 sur la diagonale ; sans orientation des arêtes, elle est symétrique4.
Le coefficient (i,j) de Ak donne le nombre de chemins de longueur k de i à j4.
Méthode : numéroter les sommets, remplir la matrice, calculer la puissance Ak, lire le coefficient demandé.
Construire la matrice d'adjacence
Reconnaître les propriétés de la matrice
Compter les chemins avec les puissances
Questions flash
4 questions · correction immédiate · ton score reste sur ton appareil.
Un graphe non orienté donne une matrice symétrique (aij=aji), et un graphe simple n'a pas de boucle, donc la diagonale est nulle 4. Mettre des 1 sur la diagonale reviendrait à ajouter une boucle à chaque sommet, ce qui contredit « simple ».
C'est le théorème du cours : le coefficient (i,j) de Ak compte les parcours de longueur exactement k de i à j4. Ici k=3. L'erreur tentante serait de croire qu'il compte aussi les chemins plus courts : ce n'est pas le cas.
Les chemins sont B–A–B et B–C–B, soit 2, ce qui correspond au coefficient (2,2) de M2. Répondre 0 vient de l'idée qu'on ne peut pas revenir à son point de départ, alors qu'un chemin peut repasser par un sommet.
Sans orientation, la matrice est symétrique 4 ; si elle ne l'est pas, c'est que les liaisons ont un sens, donc le graphe est orienté. Une boucle se lit sur la diagonale et ne casse pas la symétrie.
Les questions qu'on se pose
À quoi sert la matrice d'adjacence ?
Elle représente un graphe sous forme de tableau, ce qui permet d'appliquer le calcul matriciel : avec les puissances de la matrice, on compte les chemins de longueur donnée 24. Elle sert aussi à écrire un graphe de façon exploitable par un programme 3.
Faut-il calculer toutes les puissances pour avoir un seul coefficient ?
Il faut calculer Ak en entier, car un coefficient de Ak dépend de plusieurs coefficients de Ak−1 et de A. À la calculatrice, la touche puissance de matrice le fait directement ; à la main, on multiplie pas à pas en gardant les produits utiles.
Le résultat change-t-il si je numérote les sommets autrement ?
La matrice change d'aspect, car l'ordre des sommets détermine les lignes et les colonnes ; une fois cet ordre fixé, elle est unique 4. Le nombre de chemins, lui, ne change pas : il suffit de lire la ligne et la colonne correspondant aux bons sommets.