En matemáticas , la teoría de grafos espectrales es el estudio de las propiedades de un grafo en relación con el polinomio característico , los valores propios y los vectores propios de las matrices asociadas con el grafo, como su matriz de adyacencia o matriz laplaciana .
La matriz de adyacencia de un grafo simple no dirigido es una matriz simétrica real y, por lo tanto, es diagonalizable ortogonalmente ; sus valores propios son números enteros algebraicos reales .
Si bien la matriz de adyacencia depende del etiquetado de los vértices, su espectro es un gráfico invariante , aunque no completo.
La teoría de grafos espectrales también se ocupa de los parámetros del grafo que se definen a través de multiplicidades de valores propios de matrices asociadas al grafo, como el número de Colin de Verdière .
Dos gráficos se denominan coespectrales o isoespectrales si las matrices de adyacencia de los gráficos son isoespectrales , es decir, si las matrices de adyacencia tienen multiconjuntos iguales de valores propios.
Los gráficos coespectrales no necesitan ser isomorfos , pero los gráficos isomorfos siempre son coespectrales.
Se dice que un grafo está determinado por su espectro si cualquier otro grafo con el mismo espectro que es isomorfo a .
Algunos primeros ejemplos de familias de gráficos que están determinadas por su espectro incluyen:
Se dice que un par de gráficos son compañeros coespectrales si tienen el mismo espectro, pero no son isomorfos.
El par más pequeño de compañeros coespectrales es { K 1,4 , C 4 ∪ K 1 }, que comprende la estrella de 5 vértices y la unión gráfica del ciclo de 4 vértices y el gráfico de un solo vértice, como informaron Collatz y Sinogowitz [1] [2] en 1957.
El par más pequeño de compañeros coespectrales poliédricos son eneaedros con ocho vértices cada uno. [3]
Casi todos los árboles son coespectrales, es decir, a medida que aumenta el número de vértices, la fracción de árboles para los que existe un árbol coespectral tiende a 1. [4]
Un par de gráficos regulares son coespectrales si y sólo si sus complementos son coespectrales. [5]
Un par de gráficos regulares en cuanto a distancia son coespectrales si y solo si tienen la misma matriz de intersecciones.
Los gráficos coespectrales también se pueden construir mediante el método Sunada . [6]
Otra fuente importante de gráficos coespectrales son los gráficos de colinealidad de puntos y los gráficos de intersección de líneas de geometrías de puntos y líneas . Estos gráficos son siempre coespectrales, pero a menudo no son isomorfos. [7]
La famosa desigualdad de Cheeger de la geometría de Riemann tiene un análogo discreto que involucra a la matriz laplaciana; 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 aplicaciones algorítmicas. Aproxima el corte más disperso de un grafo a través del segundo valor propio de su laplaciano.
La constante de Cheeger (también llamada número de Cheeger o número isoperimétrico ) de un grafo es una medida numérica de si un grafo tiene o no un "cuello de botella". La constante de Cheeger como medida de "cuello de botella" es de gran interés en muchas áreas: por ejemplo, la construcción de redes de computadoras bien conectadas , el barajado de cartas y la topología de baja dimensión (en particular, el estudio de variedades hiperbólicas de 3 dimensiones ).
Más formalmente, la constante de Cheeger h ( G ) de un grafo G en n vértices se define como
donde el mínimo es sobre todos los conjuntos no vacíos S de como máximo n /2 vértices y ∂( S ) es el límite de la arista de S , es decir, el conjunto de aristas con exactamente un punto final en S . [8]
Cuando el grafo G es d -regular, existe una relación entre h ( G ) y el gap espectral d − λ 2 de G . Una desigualdad debida a Dodziuk [9] e independientemente a Alon y Milman [10] establece que [11]
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 .
Para gráficos generales conectados que no son necesariamente regulares, Chung [12] da una desigualdad alternativa : 35
donde es el valor propio no trivial más pequeño del laplaciano normalizado, y es la constante de Cheeger (normalizada)
donde es la suma de los grados de los vértices en .
Existe un límite de valor propio para conjuntos independientes en grafos regulares , originalmente debido a Alan J. Hoffman y Philippe Delsarte. [13]
Supongamos que es un grafo regular en vértices con el menor valor propio . Entonces: donde denota su número de independencia .
Este límite se ha aplicado para establecer, por ejemplo, pruebas algebraicas del teorema de Erdős–Ko–Rado y su análogo para familias de subespacios que se intersecan sobre campos finitos . [14]
Para los grafos generales que no son necesariamente regulares, se puede derivar un límite superior similar para el número de independencia utilizando el valor propio máximo del laplaciano normalizado [12] de : donde y denotan el grado máximo y mínimo en , respectivamente. Esto es una consecuencia de una desigualdad más general (pp. 109 en [12] ): donde es un conjunto independiente de vértices y denota la suma de los grados de los vértices en .
La teoría de grafos espectrales surgió en los años 1950 y 1960. Además de la investigación teórica de grafos sobre la relación entre las propiedades estructurales y espectrales de los grafos, otra fuente importante fue la investigación en química cuántica , pero las conexiones entre estas dos líneas de trabajo no se descubrieron hasta mucho después. [15] La monografía Spectra of Graphs [16] de 1980 de Cvetković, Doob y Sachs resumió casi toda la investigación hasta la fecha en el área. En 1988 fue actualizada por la encuesta Recent Results in the Theory of Graph Spectra . [17] La tercera edición de Spectra of Graphs (1995) contiene un resumen de las contribuciones recientes adicionales al tema. [15] El análisis geométrico discreto creado y desarrollado por Toshikazu Sunada en la década de 2000 trata la teoría de grafos espectrales en términos de laplacianos discretos asociados con grafos ponderados, [18] y encuentra aplicación en varios campos, incluido el análisis de formas . En los últimos años, la teoría de grafos espectrales se ha expandido a grafos que varían en los vértices y que suelen encontrarse en muchas aplicaciones de la vida real. [19] [20] [21] [22]
{{cite book}}
: Mantenimiento de CS1: postscript ( enlace ){{cite book}}
: Mantenimiento de CS1: falta la ubicación del editor ( enlace ){{cite book}}
: Mantenimiento de CS1: postscript ( enlace )