Matrice d'adjacence

Modèle:Ébauche En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à Modèle:Mvar sommets est une matrice de dimension Modèle:Math dont l'élément non diagonal Modèle:Mvar est le nombre d'arêtes liant le sommet Modèle:Mvar au sommet Modèle:Mvar. L'élément diagonal Modèle:Mvar est le nombre de boucles au sommet Modèle:Mvar (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 $G=(V,E)$ est un graphe simple, où $\left|V\right|=n$. Supposons aussi que les sommets de Modèle:Mvar sont numérotés arbitrairement $v_1,\dots ,v_n$. La matrice d’adjacence Modèle:Mvar de Modèle:Mvar se rapportant à cet ensemble de sommets est la matrice Modèle:Math booléenne Modèle:Mvar avec

$a_{ij}=\{\begin{array}{cc}1& \text{si }(v_i,v_j)\in E\\ 0& \text{sinon.}\end{array}$

Exemples

Graphe étiqueté	Matrice d'adjacence
Graphe non orienté	$\left(\begin{array}{cccccc}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{array}\right)$
Graphe orienté	$\left(\begin{array}{cccccccc}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{array}\right).$

Propriétés

Unicité

Une fois que l'on fixe l'ordre des n sommets (il y a n! choix possibles pour cet ordre), il existe une matrice d'adjacence unique pour chaque graphe. Celle-ci n'est la matrice d'adjacence d'aucun autre graphe. Dans le cas particulier d'un graphe simple et fini, la matrice d'adjacence est une matrice binaire avec des zéros sur la diagonale. Si le graphe n'est pas orienté, la matrice d'adjacence est symétrique, ce qui veut dire que Modèle:Mvar.

Propriété de l'itérée

Si Modèle:Mvar est la matrice d'adjacence d'un graphe fini Modèle:Mvar dont les sommets sont numérotés de Modèle:Math à Modèle:Mvar, le nombre de parcours de longueur exactement Modèle:Mvar allant de Modèle:Mvar à Modèle:Mvar est le coefficient en position Modèle:Math de la matrice Modèle:Mvar — ceci si chaque arête entre deux sommets a une longueur égale à Modèle:Math.

Propriétés spectrales

La théorie spectrale des graphes étudie les propriétés du spectre de plusieurs matrices, dont la matrice d'adjacence. En particulier la deuxième plus grande valeur propre est reliée au taux d'expansion du graphe.

Voir aussi

Articles connexes

• Matrice d'incidence
• Matrice laplacienne
• Matrice de distance euclidienne

Lien externe

• Modèle:En Café math : Adjacency Matrices of Graphs : Application des matrices d'adjacence au calcul des séries génératrices de chemins.