Construire la matrice d’adjacence d’un graphe
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthode
Pour construire la matrice d'adjacence $M$ d'un graphe d'ordre $n$ :
- Étape 1 : numéroter (ou ordonner alphabétiquement) les sommets de $1$ à $n$. Cet ordre détermine l'ordre des lignes et des colonnes.
- Étape 2 : créer la matrice carrée $M$ d'ordre $n$ et placer les noms des sommets en en-tête de ligne et de colonne (cela aide au remplissage).
- Étape 3 : pour chaque couple de sommets $(i, j)$, écrire dans la case $M_{i,j}$ le nombre d'arêtes (ou d'arcs) reliant directement le sommet $i$ au sommet $j$.
- Étape 4 : pour un graphe non orienté, vérifier que la matrice est symétrique : $M_{i,j} = M_{j,i}$. Une boucle sur le sommet $i$ ajoute $2$ au coefficient $M_{i,i}$.
- Étape 5 : pour un graphe orienté, $M_{i,j}$ compte uniquement les arcs allant de $i$ vers $j$. La matrice n'est pas nécessairement symétrique. Une boucle ajoute $1$ au coefficient $M_{i,i}$.
Graphe non orienté à 5 sommets
On considère le graphe non orienté ci-dessous, dont les sommets sont $A, B, C, D, E$.
Étape 1 : On classe les sommets dans l'ordre alphabétique : $A, B, C, D, E$.
Étape 2 : On crée une matrice carrée d'ordre $5$.
Étape 3 : On lit chaque arête sur le graphe et on remplit les coefficients :
- $A$ est relié à $B$ et $E$ : on écrit $1$ dans $M_{A,B}$ et $M_{A,E}$.
- $B$ est relié à $A$, $C$ et $D$ : on écrit $1$ dans $M_{B,A}$, $M_{B,C}$ et $M_{B,D}$.
- $C$ est relié à $B$ et $D$.
- $D$ est relié à $B$, $C$ et $E$.
- $E$ est relié à $A$ et $D$.
Étape 4 : La matrice obtenue est bien symétrique.
Graphe orienté avec boucle
On considère le graphe orienté ci-dessous, dont les sommets sont $1, 2, 3, 4$. Le sommet $3$ porte une boucle.
Étape 1 : Les sommets sont déjà numérotés de $1$ à $4$.
Étape 2 : On crée une matrice carrée d'ordre $4$.
Étape 3 : On parcourt les arcs en respectant le sens de la flèche :
- de $1$ vers $2$ : un arc, donc $M_{1,2} = 1$.
- de $1$ vers $3$ : un arc, donc $M_{1,3} = 1$.
- de $2$ vers $3$ : un arc, donc $M_{2,3} = 1$.
- de $3$ vers $3$ : une boucle, donc $M_{3,3} = 1$ (et non $2$, car le graphe est orienté).
- de $3$ vers $4$ : un arc, donc $M_{3,4} = 1$.
- de $4$ vers $1$ : un arc, donc $M_{4,1} = 1$.
Étape 5 : La matrice n'est pas symétrique (par exemple, $M_{1,2} = 1$ mais $M_{2,1} = 0$).
Remarque
L'ordre choisi pour les sommets est libre, mais une fois fixé, il doit être identique pour les lignes et pour les colonnes. Changer l'ordre des sommets revient à permuter simultanément les lignes et les colonnes de la matrice.
Attention
Pour un graphe non orienté, oublier la symétrie $M_{i,j} = M_{j,i}$ est l'erreur la plus fréquente : chaque arête doit être comptée une fois dans chaque sens.
Pour les boucles : $+2$ sur la diagonale pour un graphe non orienté, mais $+1$ pour un graphe orienté.