Tableau bidimensionnel représentant un graphe fini dont l'élément (i,j) indique la présence et éventuellement le poids d'une arête entre le nœud i et le nœud j.

Principe

Coder la connectivité discrète dans un objet d'algèbre linéaire afin que les opérations sur le graphe se traduisent en opérations matricielles.

Démonstration

Pour un graphe simple non orienté à nœuds {1,2,3,4} et arêtes {1–2,2–3,3–4}, la matrice d'adjacence A a des zéros sur la diagonale et des uns aux positions (1,2),(2,1),(2,3),(3,2),(3,4),(4,3).

Mauvaise application

Utiliser la même matrice d'adjacence comme descripteur complet pour un multigraphe sans étendre les entrées à des comptes fait perdre l'information de multiplicité.

Conséquence

Permet d'utiliser l'algèbre matricielle (puissances, produits, calcul d'indices) pour étudier les marches, la connexité et les propriétés combinatoires du graphe.

Inversion

Une matrice d'incidence enregistre plutôt les incidences nœud–arête que les connexions nœud–nœud, déplaçant l'analyse de l'adjacence vers l'appartenance aux arêtes.

Limite

Définie pour les graphes finis ; pour les hypergraphes, réseaux à couches multiples ou structures à arêtes étiquetées, l'adjacence binaire de base doit être étendue ou remplacée.

Tension sémantique

Par rapport à une adjacency pondérée : la matrice d'adjacence non qualifiée implique souvent des entrées binaires, tandis que de nombreuses analyses supposent ou exigent des poids réels.

Synthèse

Une matrice compacte dont le motif d'entrées est un codage direct en algèbre linéaire de quels nœuds sont reliés et de l'intensité de ces liens dans un graphe fini.