Matrice d'adjacence

matrice liée à un graphe fini représentant, pour chaque coefficient a_ij, le nombre d'arêtes liant le sommet i et le sommet j

En mathématiques, en théorie des graphes, en informatique, une matrice d'adjacence pour un graphe fini à 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 (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

modifier

Supposons que   est un graphe simple, où  . Supposons aussi que les sommets de G sont numérotés arbitrairement  . La matrice d’adjacence A de G se rapportant à cet ensemble de sommets est la matrice n × n booléenne A avec[1]

 

Exemples

modifier
Graphe étiqueté Matrice d'adjacence
 
Graphe non orienté
 
 
Graphe orienté
 

Propriétés

modifier

Unicité

modifier

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 aij = aji.

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

modifier

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 Ak — ceci si chaque arête entre deux sommets a une longueur égale à 1.

Propriétés spectrales

modifier

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.

  1. M. Gondran et M. Minoux, Graphes et algorithmes, Eyrolles, coll. « Études et recherches d'EdF », (ISSN 0399-4198), « 1. Généralités sur les graphes », p. 7

Voir aussi

modifier

Sur les autres projets Wikimedia :

Articles connexes

modifier

Lien externe

modifier