Matrice d'adjacence : définition (Maths expertes)

Soit un graphe d'ordre $m$ dont les sommets sont numérotés de $1$ à $m$. Sa matrice d'adjacence est la matrice carrée $M=(m_{ij})$ d'ordre $m$ telle que :

• pour un graphe non orienté, $m_{ij}=1$ si les sommets $i$ et $j$ sont adjacents, $m_{ij}=0$ sinon ;
• pour un graphe orienté, $m_{ij}=1$ s'il existe un arc de $i$ vers $j$, $m_{ij}=0$ sinon.

La matrice dépend de la numérotation choisie pour les sommets.