Matrice d'adjacence
Période historique : 1950
Matrice carrée binaire A codant la connectivité d'un graphe, où A_ij = 1 si une arête relie i à j.
Contenu & Formulation mathématique
Genèse & Portée historique
Représentation algébrique maîtresse d'un graphe à n sommets. Pour un graphe non orienté, elle est symétrique à coefficients réels, donc diagonalisable d'après le théorème spectral. La puissance k-ième (A^k)_ij donne exactement le nombre de chemins de longueur k reliant le sommet i au sommet j.
La théorie spectrale des graphes étudie les valeurs propres de cette matrice et de la matrice laplacienne L = D - A pour déduire les propriétés d'expansion et de découpage des réseaux.
Filiations & Relations conceptuelles (1)
Objet de collection MathTCG
Matrice d'adjacence
Matrice carrée binaire A codant la connectivité d'un graphe, où A_ij = 1 si une arête relie i à j.
Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.