Matrice d'adjacence
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
 |
Cet article est une ébauche à compléter concernant les mathématiques, vous pouvez partager vos connaissances en le modifiant. |
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é en informatique, mais intervient aussi naturellement dans les chaines de Markov. En particulier, la probabilité limite s'interprète comme un vecteur propre.
[modifier] Propriétés
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 dirigé, la matrice d'adjacence est symétrique.
[modifier] Exemple
La matrice d'adjacence du graphe étiqueté suivant
est
[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 k allant de i à j est le coefficient en position (i,j) de la matrice A^k.
|
Portail des mathématiques – Accédez aux articles de Wikipédia concernant les mathématiques. |
