Comment construire la matrice d’adjacence d’un graphe orienté ?

Réponse courte

Pour construire une matrice d’adjacence, fixe l’ordre des sommets puis place en ligne i et colonne j un 1 si un arc va de i vers j, et 0 sinon. La ligne indique le départ, la colonne l’arrivée.

Comprendre

Fixer l’ordre des sommets

Écris d’abord la liste des sommets dans un ordre précis, par exemple A, B, C. La matrice d’adjacence est carrée et a autant de lignes et de colonnes que de sommets. Garde le même ordre pour lire les lignes et les colonnes : ici ligne 1 et colonne 1 désignent A, ligne 2 et colonne 2 désignent B, etc.

Coder le sens des arcs

Pour chaque arc orienté, mets 1 dans la case correspondant à son départ en ligne et à son arrivée en colonne. Mets 0 s’il n’existe pas d’arc dans ce sens. Par exemple, avec les arcs A vers B, A vers C et C vers B, dans l’ordre A, B, C, on obtient (0, 1, 1 ; 0, 0, 0 ; 0, 1, 0).

Vérifier le tableau

La somme d’une ligne donne le nombre d’arcs sortants du sommet correspondant ; la somme d’une colonne donne le nombre d’arcs entrants. La matrice n’est pas nécessairement symétrique : l’arc A vers B ne signifie pas que B vers A existe. Une boucle autorisée se place sur la diagonale.

Étapes

  1. Écris les sommets dans un ordre fixé, qui servira pour les lignes et les colonnes.
  2. Pour chaque case (i ; j), vérifie s’il existe un arc du sommet i vers le sommet j.
  3. Inscris 1 si cet arc existe et 0 sinon.
  4. Contrôle chaque ligne et chaque colonne en les comparant aux arcs sortants et entrants du graphe.

Exemples

  • Avec A→B, A→C et C→B, l’ordre A, B, C donne (0, 1, 1 ; 0, 0, 0 ; 0, 1, 0).
  • Si l’ordre des sommets est B, A et que le seul arc est A→B, la matrice est (0, 0 ; 1, 0).

Pièges fréquents

  • Mettre 1 dans la case (B ; A) pour l’arc A→B : la convention ligne-départ, colonne-arrivée impose la case (A ; B).
  • Rendre automatiquement la matrice symétrique : dans un graphe orienté, les arcs inverses doivent être vérifiés séparément.

Et maintenant ?

Questions proches

← Toutes les questions-réponses