##  [Matrice D'Adjacence](/fr/node/57783) 

 Définition

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

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

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

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

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

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

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

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

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.