A tout graphe non orienté d'ordre
, on peut associer
une matrice carrée 
, symétrique, dont les éléments 
valent 1 si le sommet 
et le sommet 
sont adjacents et 0 sinon.Matrice associée à un graphe non orienté
Définition
A tout graphe non orienté d'ordre , on peut associer
une matrice carrée , symétrique, dont les éléments valent 1 si le sommet et le sommet sont adjacents et 0 sinon.
Propriété
Si M est la matrice associée
au graphe G, si N = M p, l'élément 
de la matrice
N est égal au nombre de chemins de longueur
, qui relient le sommet 
au sommet 
.
Un graphe et sa matrice associée
|
|
|
: il y a donc trois chemins de longueurs 2 pour joindre le sommet 1 à
lui même, ce sont : 
: il y a donc deux chemins de longueurs 2 pour joindre le sommet 2 au sommet
4, ce sont : 
|
|
|
