MetMat
← Retour aux méthodes

Comment construire la matrice d'adjacence d'un graphe (orienté ou non) ?

En numérotant les sommets et en plaçant 11 lorsqu'une arête (ou un arc) existe, 00 sinon

L'objectif

Représenter un graphe fini par sa matrice d'adjacence pour en permettre l'exploitation calculatoire.

Le principe

Pour un graphe G=(S,A)G=(S,A) dont les sommets sont numérotés 1,…,n1,\dots,n, la matrice d'adjacence est A=(ai,j)∈Mn(R)A=(a_{i,j})\in\mathcal{M}_n(\mathbb{R}) définie par ai,j=1a_{i,j}=1 s'il existe une arête (cas non orienté) ou un arc de ii vers jj (cas orienté), et ai,j=0a_{i,j}=0 sinon ; dans le cas non orienté, AA est symétrique.

La méthode
  1. 1
    Je numérote les sommets de 11 à nn et je détermine si le graphe est orienté (arcs i→ji\to j) ou non orienté (arêtes {i,j}\{i,j\}).
  2. 2
    Je construis une matrice n×nn\times n en inscrivant ai,j=1a_{i,j}=1 si l'arête {i,j}\{i,j\} (ou l'arc i→ji\to j) existe, et ai,j=0a_{i,j}=0 sinon.
  3. 3
    Je vérifie la cohérence : dans le cas non orienté, je contrôle que AA est symétrique ; dans le cas orienté, je note que AA n'a aucune raison d'être symétrique.

Exemple corrigé

Difficulté croissante de 1 à 3

Exercices aujourd'hui0 / 3

Prêt à t'entraîner ?

Génère un exercice personnalisé sur cette méthode et entraîne-toi avec la correction IA.