Matrice d'adjacence

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 aij est le nombre d'arêtes liant le sommet i au sommet j. L'élément diagonal aii est le nombre de boucles au sommet i (ou deux fois ce nombre, selon certains usages).

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[modifier | modifier le code]

Supposons que G=(V,E) est un graphe simple, où \left|V\right|=n. Supposons aussi que les sommets de G sont numérotés 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.

Propriétés[modifier | modifier le code]

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 a_{ij} = a_{ji}.

Exemples[modifier | modifier le code]

Graphe non orienté
Graphe orienté

Les matrices d'adjacence du graphe étiqueté (en) (non orienté) de gauche et de celui (orienté) de droite sont respectivement

\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}\quad\text{et}\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}.

Remarque[modifier | modifier le code]

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 parcours de longueur exactement k allant de i à j est le coefficient en position (i, j) de la matrice A^k — ceci si chaque arête entre deux sommets a une longueur égale à 1.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]