Considérons un graphe d'ordre \( n \in \mathbb{N}^{\star} \). On numérote ces sommets de 1 à \( n \).

On appelle matrice d'adjacence associée à ce graphe la matrice A dont le terme \( a_{ij} \) vaut 1 si les sommets \( i \) et \( j \) sont reliés par une arête et 0 sinon.

Dans le cas d'un graphe non orienté, les coefficients \( a_{ij} \) et \( a_{ji} \) sont égaux pour tout \(i \) et tout \( j \) compris entre 1 et \( n \). Autrement dit, la matrice d'adjacence est symétrique.

Dans le cas d'un graphe orienté, la matrice d'adjacence n'est pas a priori symétrique.

Exemple

Matrice d'adjacence associée à un graphe

	En numérotant les sommets de ce graphe par ordre alphabétique, sa matrice d'adjacence s'écrit \( \begin{pmatrix} 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \end{pmatrix} \)