En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à n sommets est une matrice de dimension n × n dont l'élément non diagonal a_ij est le nombre d'arêtes liant le sommet i au sommet j. L'élément diagonal a_ii est le nombre de boucles au sommet i (pour des graphes simples, ce nombre est donc toujours égal à 0 ou 1).

Cet outil mathématique est très utilisé comme structure de données en informatique (tout comme la représentation par liste d'adjacence), mais intervient aussi naturellement dans les chaînes de Markov. En particulier, la probabilité limite s'interprète comme un vecteur propre.

Définition

Supposons que ${\displaystyle G=(V,E)}$ est un graphe simple, où ${\displaystyle \left|V\right|=n}$. Supposons aussi que les sommets de G sont numérotés arbitrairement ${\displaystyle v_{1},\ldots ,v_{n}}$. La matrice d’adjacence A de G se rapportant à cet ensemble de sommets est la matrice n × n booléenne A avec^[1]

${\displaystyle a_{ij}=\left\{{\begin{array}{rl}1&{\mbox{si }}(v_{i},v_{j})\in E\\0&{\mbox{sinon.}}\end{array}}\right.}$

Exemples

Graphe étiqueté	Matrice d'adjacence
Graphe non orienté	${\displaystyle {\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\end{pmatrix}}}$
Graphe orienté	${\displaystyle \quad {\begin{pmatrix}0&1&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&0&0&0\\0&0&1&0&0&0&1&0\\0&0&0&0&0&0&0&0\\1&1&1&0&0&0&0&0\\0&0&0&0&0&0&0&0\\0&0&0&0&0&0&1&0\\\end{pmatrix}}.}$

Propriétés

Notes

Voir aussi