Théorie spectrale des graphes

En mathématiques, la théorie spectrale des graphes s'intéresse aux rapports entre les spectres des différentes matrices que l'on peut associer à un graphe et ses propriétés. C'est une branche de la théorie algébrique des graphes. On s'intéresse en général à la matrice d'adjacence et à la matrice laplacienne normalisée. Soit un graphe , où désigne l'ensemble des sommets et l'ensemble des arêtes. Le graphe possède sommets, notés et arêtes, notées . Chaque élément de la matrice d'adjacence du graphe est défini par : La matrice des degrés est une matrice diagonale où les éléments correspondent au nombre de liens du sommet , c'est-à-dire à son degré. En utilisant cette matrice et la précédente, on peut également définir la matrice laplacienne non normalisée . On obtient sa forme normalisée par , où est la matrice identité. On obtient aussi directement par chacun de ses éléments : Enfin, la matrice d'incidence d'un graphe est la matrice de dimensions dans laquelle l'élément vaut 1 si le sommet est une extrémité de l'arête , et 0 sinon. On a l'ensemble de relations suivantes, où désigne la matrice identité : Pour la matrice d'adjacence du line graph , Pour la matrice d'adjacence du graphe de subdivision , Le spectre d'une matrice est l'ensemble de ses valeurs propres ; si elles sont réelles, nous convenons de les classer : . Par extension, on parle du spectre du graphe. On rappelle que la multiplicité algébrique d'une valeur propre est la puissance du monôme dans le polynôme caractéristique (c'est-à-dire la multiplicité de la racine dans le polynôme caractéristique). Il est également possible de modifier le polynôme caractéristique pour prendre en compte d'autres propriétés du graphe : on considère par défaut le polynôme (appelé polynôme caractéristique du graphe), mais on peut aussi s'intéresser à des variantes telles que ou . La matrice du graphe est définie positive, et elle ne peut être réduite si le graphe est connexe. Dans le cas d'un graphe non orienté, la matrice est symétrique et hermitienne, c'est-à-dire que où est la matrice adjointe de .