Comment lire une matrice d’adjacence d’un graphe orienté ?
Réponse courte
Repère le sommet de la ligne i et celui de la colonne j. La case (i, j) indique si un arc va du sommet i vers le sommet j ; dans une matrice binaire, 1 signifie présent et 0 absent.
Comprendre
Fixer l’ordre des sommets
Une matrice d’adjacence dépend d’un ordre choisi pour numéroter ou nommer les sommets. La ligne correspond au sommet de départ et la colonne au sommet d’arrivée : l’entrée de ligne i et colonne j décrit donc un éventuel arc de i vers j. Pour une matrice binaire, la valeur 1 code la présence de cet arc et 0 son absence.
Lire un exemple
Prends les sommets A, B et C, dans cet ordre, et la matrice suivante : ligne A : 0, 1, 0 ; ligne B : 0, 0, 1 ; ligne C : 1, 0, 0. La case de ligne A, colonne B vaut 1 : l’arc A→B existe. Celle de ligne B, colonne A vaut 0 : l’arc inverse B→A n’est pas présent. La case de ligne C, colonne A vaut 1, donc C→A complète un cycle orienté.
Lire sans inverser le sens
Pour trouver les arcs qui partent de B, lis toute la ligne B. Pour trouver les arcs qui arrivent en B, lis la colonne B. La diagonale décrit les boucles éventuelles d’un sommet vers lui-même ; elle n’est pas nécessairement nulle, sauf si la définition du graphe l’interdit. N’inverse pas l’ordre ligne-colonne : cela ferait lire les arcs entrants à la place des arcs sortants.
Étapes
- Note l’ordre associé aux lignes et aux colonnes de la matrice.
- Pour un arc de i vers j, lis la case de la ligne i et de la colonne j.
- Interprète sa valeur selon le codage annoncé, puis vérifie séparément la case inverse.
Exemples
- Avec la ligne A, colonne B égale à 1, l’arc A→B est présent.
- Si ligne B, colonne A vaut 0, cela ne signifie pas que l’arc A→B est absent ; il faut lire la case A,B.
Pièges fréquents
- Lire la case (i,j) comme un arc de j vers i : la ligne indique le départ et la colonne l’arrivée dans la convention donnée.
- Supposer que la matrice d’un graphe orienté est symétrique : un arc peut exister sans son inverse.
