Pour une matrice d'adjacence représentant un graphe avec 
𝑛
n sommets, chaque élément de la matrice indique la présence ou l'absence d'une arête entre deux sommets. Comme il s'agit d'une matrice carrée de taille 
𝑛
×
𝑛
n×n, le nombre total d'éléments est 
𝑛
2
n
2
.

Si chaque élément est stocké sous forme d'un bit (0 pour absence d'arête, 1 pour présence d'arête), alors l'espace nécessaire est :

\[
\text{Espace} = n^2 \text{ bits}
\]

Exemple concret
Pour 
𝑛
=
10
n=10 sommets, l'espace requis est 
1
0
2
=
100
10
2
=100 bits.
Pour 
𝑛
=
100
n=100 sommets, l'espace requis est 
10
0
2
=
10
000
100
2
=10000 bits (soit 1 250 octets, car 1 octet = 8 bits).

Remarques

Graphe non orienté sans boucle : Si le graphe est non orienté et sans boucle (pas d'arête d'un sommet vers lui-même), on peut optimiser l'espace en stockant uniquement la moitié de la matrice (triangle supérieur ou inférieur), ce qui réduit l'espace à :

\[
\frac{n(n-1)}{2} \text{ bits}
\]
(car la diagonale est inutile et la matrice est symétrique).

Graphe orienté : Pour un graphe orienté, la matrice complète 
𝑛
2
n
2
 bits est nécessaire, car une arête 
(
𝑖
,
𝑗
)
(i,j) peut exister sans que 
(
𝑗
,
𝑖
)
(j,i) existe.
Cas pondéré : Si les arêtes ont des poids, chaque élément nécessite plus qu'un bit (par exemple, un entier), et l'espace augmente en conséquence.