La teoría de grafos espectrales es una dirección en la teoría de grafos que estudia las propiedades de los gráficos , los polinomios característicos , los vectores propios y los valores propios de las matrices asociadas con un gráfico, como su matriz de adyacencia o la matriz de Kirchhoff .
Un gráfico no dirigido tiene una matriz de adyacencia simétrica y, por lo tanto, tiene valores propios reales (cuyo conjunto múltiple se denomina espectro del gráfico ) y un conjunto completo de vectores propios .
Mientras que la matriz de adyacencia de un gráfico depende de la numeración de los vértices, su espectro es un gráfico invariante .
La teoría de gráficos espectrales también se ocupa de los parámetros que se determinan multiplicando los valores propios de las matrices asociadas con el gráfico, como el número de Colin de Verdière .
Se dice que dos gráficos son isoespectrales o coespectrales si las matrices de adyacencia de los gráficos tienen los mismos conjuntos múltiples de valores propios.
Los gráficos isoespectrales no son necesariamente isomorfos , pero los gráficos isomorfos siempre son isoespectrales. El par mínimo de grafos coespectrales no isomórficos no dirigidos es , es decir, una estrella de cinco vértices y la unión de un ciclo de 4 vértices y un grafo de un solo vértice, como muestran Kollatz y Singovich [1] [2] en 1957. El par más pequeño de gráficos poliédricos coespectrales no isomorfos son dos eneaedros con ocho vértices cada uno [3] .
Casi todos los árboles tienen gráficos coespectrales a ellos, es decir, la proporción de árboles de orden , para cada uno de los cuales hay un gráfico coespectral, tiende a 1 a medida que crece [4] .
Los gráficos isoespectrales se construyen utilizando el método Sunada [5] .
La famosa desigualdad de Cheeger de la geometría de Riemann tiene un análogo discreto usando la matriz de Kirchhoff. Este es quizás el teorema más importante en la teoría de grafos espectrales y uno de los hechos más útiles en las aplicaciones algorítmicas. La desigualdad evalúa el corte más pequeño de la gráfica mediante el segundo valor propio de la matriz de Kirchhoff.
La constante de Cheeger (o número de Cheeger , o número isoperimétrico ) de un gráfico es una medida numérica de si un gráfico tiene un cuello de botella. La constante de Cheeger como medida de la presencia de un cuello de botella es de gran interés en muchos campos. Por ejemplo, al construir redes informáticas fuertemente conectadas , mapas aleatorios y topología de baja dimensión (en particular, al estudiar 3 variedades hiperbólicas ).
Formalmente, la constante de Cheeger de un gráfico con vértices se define como
donde el mínimo se toma sobre todos los conjuntos no vacíos, el máximo con vértices y es el borde límite del conjunto , es decir, el conjunto de bordes que tienen exactamente un vértice final en [6] .
Si el gráfico es -regular, existe una conexión entre y el intervalo espectral del gráfico . La desigualdad de Cheeger fue estudiada por Tanner, Alon y Milman [7] . La desigualdad establece que [8]
Esta desigualdad está estrechamente relacionada con el límite de Cheeger para las cadenas de Markov y puede verse como una versión discreta de la desigualdad de Cheeger en la geometría de Riemann .
La teoría de grafos espectrales surgió en las décadas de 1950 y 1960. La monografía de 1980 " Spectra of Graphs " [9] de Cvetković, Michael Doob y Sachs resumió casi toda la investigación en esta área conocida hasta ese momento. En 1988, se publicó una revisión actualizada " Investigación reciente en la teoría del espectro de grafos " [10] . La tercera edición del libro Spectra of Graphs (1995) contiene los resultados de otras contribuciones en esta área [11] .
Además de los estudios teóricos sobre la relación entre las propiedades estructurales y espectrales de los gráficos, los estudios en química cuántica se convirtieron en otra fuente , pero la relación entre estas dos áreas se aclaró mucho más tarde [11] .