Matrice d'adjacence

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

En mathématiques, une matrice d'adjacence pour un graphe fini $G$ à 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$ (ou deux fois ce nombre, selon certains usages).

Cet outil mathématique est très utilisé en informatique, mais intervient aussi naturellement dans les chaînes de Markov. En particulier, la probabilité limite s'interprète comme un vecteur propre.

[modifier] Définition

Supposez que $G = (V, E)$ est un graphe simple, où $\left|V\right|=n$ . Supposez aussi que les sommets de $G$ sont, arbitrairement, $v_1,\ldots,v_n$ . La matrice d’adjacence $A$ de $G$ se rapportant à cet ensemble de sommets est la matrice $n\times n$ booléenne $A$ avec

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

À noter qu’une matrice d’adjacence d’un graphe est fondée sur la relation d’ordre établie pour les sommets.

Donc, il existe (au plus) $n!$ matrices d’adjacences différentes pour un graphe comportant $n$ sommets puisqu’il y a $n!$ possibilités d’ordonner ces sommets.

[modifier] Propriétés

Une fois que l'on fixe l'ordre des sommets, 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 $a i j = a j i$ .

[modifier] Exemple

La matrice d'adjacence du graphe étiqueté suivant

est

$\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}.$

[modifier] Remarque

Si $A$ est la matrice d'adjacence d'un graphe fini $G$ dont les sommets sont numérotés de $1$ à $n$ , le nombre de chemins de longueur exactement $k$ allant de $i$ à $j$ est le coefficient en position $(i, j)$ de la matrice $A k$ — ceci si chaque arrête entre deux sommets à une longueur égale à 1.