AlgèbreObjet mathématique · Glossaire
matrice d'adjacence
La matrice d'adjacence d'un graphe est un tableau carré qui indique quels sommets sont reliés. Après avoir fixé leur ordre, on lit chaque case comme « ligne de départ, colonne d'arrivée » : elle vaut 1 si un arc va du premier sommet vers le second, et 0 sinon. Dans un graphe non orienté, la même règle indique simplement la présence ou l'absence d'une arête entre les deux sommets.
Sommaire
Ce que vous allez apprendre
- Construire une matrice d'adjacence à partir d'un ordre de sommets et d'une liste d'arcs.
- Lire le sens d'une entrée selon la convention ligne de départ, colonne d'arrivée.
- Vérifier sur un graphe orienté à quatre sommets les matrices A et A².
- Interpréter les puissances comme un comptage de marches et non de chemins simples.
- Repérer les effets d'un changement d'ordre, d'une convention transposée, des boucles et des arêtes multiples.
En clair
Imaginez quatre villes et des routes à sens unique entre certaines d'entre elles. On dessine un quadrillage : une ligne pour la ville de départ, une colonne pour la ville d'arrivée. À leur croisement, on écrit 1 si la route existe et 0 sinon. Ce quadrillage de nombres est la matrice d'adjacence du réseau.
Elle remplace ainsi un dessin par une forme que l'on peut calculer. Dans un réseau sans sens de circulation, chaque liaison se lit dans les deux directions : les nombres se répondent alors de part et d'autre de la diagonale.
Définition
Soit un graphe G dont les n sommets sont rangés dans un ordre fixé. Sa matrice d'adjacence A est une matrice carrée à n lignes et n colonnes. Avec la convention « ligne de départ, colonne d'arrivée », l'entrée située à la ligne i et à la colonne j indique s'il existe un arc du sommet i vers le sommet j :
Pour un graphe simple non orienté, une arête entre i et j produit deux entrées égales : aij = aji. La matrice est donc symétrique. Pour un graphe orienté, aij et aji peuvent différer. Certains ouvrages adoptent la convention transposée ; il faut alors vérifier le sens attribué aux lignes.
La matrice dépend de l'ordre choisi pour les sommets, mais elle encode le même graphe si l'on permute simultanément les lignes et les colonnes. Pour cette convention 0–1, on suppose un graphe simple ; boucles et arêtes multiples demandent de préciser ce que les entrées comptent.
De quoi c'est fait
Quatre éléments structurent l'objet. Le graphe G fournit les sommets et les liaisons. L'ordre des sommets associe chaque sommet à un numéro de ligne et de colonne. Les lignes représentent les départs, tandis que les colonnes représentent les arrivées selon la convention retenue. Enfin, chaque entrée aij traduit la liaison de i vers j par 0 ou 1.
L'ordre détermine donc la position des entrées, et les arcs déterminent leur valeur. Ces données suffisent à reconstruire toutes les liaisons d'un graphe simple étiqueté. Elles permettent aussi de calculer des puissances de A : l'entrée (i, j) de Ak compte les marches de longueur k allant de i à j, avec répétitions de sommets ou d'arcs autorisées.
Un exemple, pas à pas
Considérons les quatre sommets A, B, C et D. Le graphe orienté possède les six arcs A→B, A→C, B→C, C→A, C→D et D→C. Nous utilisons les lignes pour les départs et les colonnes pour les arrivées. Le graphe et son codage matriciel rendent ces six données directement contrôlables.
1. On fixe l'ordre A, B, C, D pour les lignes comme pour les colonnes.
2. On parcourt les départs. Depuis A, deux arcs mènent à B et C ; la première ligne vaut donc (0, 1, 1, 0). Les trois autres lignes se lisent de la même manière :
3. L'entrée de la ligne C et de la colonne D vaut 1, ce qui confirme l'arc C→D. L'entrée de la ligne B et de la colonne A vaut 0 : aucun arc B→A n'est annoncé.
4. Pour compter les marches de longueur 2, on multiplie A par elle-même :
Le 2 situé en ligne C et colonne C correspond exactement aux deux marches C→A→C et C→D→C. Ce décompte direct contrôle l'entrée (C, C) de A2.
En pratique
Pour tester rapidement si deux sommets sont voisins, on consulte une entrée de la matrice. Cette représentation est particulièrement commode quand le graphe contient beaucoup de liaisons ; pour un graphe très peu dense, une liste d'adjacence évite de stocker une majorité de zéros.
Pour compter des marches de longueur fixée entre tous les couples de sommets, on calcule une puissance de la matrice. Si l'on cherche au contraire des chemins simples, sans sommet répété, la puissance ne suffit pas : il faut ajouter un mécanisme qui mémorise les sommets déjà visités.
Pour repérer une liaison réciproque dans un graphe orienté, on compare aij et aji. Une matrice symétrique convient à un graphe non orienté ; dès qu'un seul couple diffère, le codage décrit des sens de parcours distincts.
À ne pas confondre
La matrice d'incidence ne met pas un sommet en face d'un autre. Ses lignes représentent les sommets et ses colonnes les arêtes ou les arcs. Dans l'exemple, la matrice d'adjacence a quatre colonnes ; une matrice d'incidence en aurait six, une par arc.
La matrice des degrés est diagonale : elle place le degré de chaque sommet sur sa diagonale et des zéros ailleurs. La matrice d'adjacence place au contraire les liaisons entre sommets dans les cases correspondantes ; sa diagonale est nulle dans un graphe simple sans boucle.
Limites et pièges
Changer l'ordre des sommets. Deux matrices différentes peuvent coder le même graphe. Le symptôme est un déplacement cohérent des mêmes liaisons. Il faut comparer les matrices après avoir appliqué la même permutation aux lignes et aux colonnes.
Inverser la convention d'orientation. Certains textes mettent les arrivées en ligne et les départs en colonne. Une lecture naïve renverse alors tous les arcs. Il faut annoncer la convention ; passer de l'une à l'autre transpose la matrice.
Rencontrer des boucles ou des arêtes multiples. Une boucle peut rendre une entrée diagonale non nulle, tandis qu'une simple valeur 1 ne conserve pas le nombre d'arêtes parallèles. Il faut préciser si aij signale seulement une adjacence ou compte les liaisons.
Lire les puissances comme des chemins simples. L'entrée (i, j) de Ak compte des marches de longueur k, qui peuvent repasser par un sommet. Dans l'exemple, (A2)CC = 2 compte C→A→C et C→D→C ; aucune n'est un chemin simple au sens strict.
Pour aller plus loin
Sous-graphe — Voir comment conserver seulement une partie des sommets ou des arêtes avant d'en étudier le codage.
Des matrices et des graphes en comptabilité — Prolonger la lecture par un article où matrices et graphes sont mobilisés ensemble dans un autre contexte.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres