En matemáticas , la teoría de grafos espectrales es el estudio de las propiedades de un gráfico en relación con el polinomio característico , los valores propios y los vectores propios de matrices asociadas con el gráfico, como su matriz de adyacencia o matriz laplaciana .
La matriz de adyacencia de un gráfico no dirigido simple es una matriz simétrica real y, por tanto, es ortogonalmente diagonalizable ; 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 de grafos que se definen mediante multiplicidades de valores propios de matrices asociadas al gráfico, como el número de Colin de Verdière .
Dos gráficos se llaman coespectrales o isoespectrales si las matrices de adyacencia de los gráficos son isoespectrales , es decir, si las matrices de adyacencia tienen múltiples conjuntos iguales de valores propios.
Los gráficos coespectrales no tienen por qué ser isomórficos , pero los gráficos isomórficos siempre son coespectrales.
Se dice que un gráfico está determinado por su espectro si cualquier otro gráfico con el mismo espectro 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 crece el número de vértices, la fracción de árboles para los que existe un árbol coespectral pasa a 1. [4]
Un par de grafos regulares son coespectrales si y sólo si sus complementos son coespectrales. [5]
Un par de gráficos de distancia regular son coespectrales si y sólo si tienen la misma matriz de intersecciones.
También se pueden construir gráficos coespectrales 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 líneas de puntos . Estos gráficos son siempre coespectrales pero a menudo no isomorfos. [7]
La famosa desigualdad de Cheeger de la geometría de Riemann tiene un análogo discreto que involucra 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. Se aproxima al corte más escaso de un gráfico a través del segundo valor propio de su laplaciano.
La constante de Cheeger (también número de Cheeger o número isoperimétrico ) de un gráfico es una medida numérica de si un gráfico 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 3 variedades hiperbólicas ).
Más formalmente, la constante de Cheeger h ( G ) de un gráfico G en n vértices se define como
donde el mínimo está sobre todos los conjuntos no vacíos S de como máximo n /2 vértices y ∂( S ) es el límite de arista de S , es decir, el conjunto de aristas con exactamente un punto final en S . [8]
Cuando el gráfico G es d -regular, existe una relación entre h ( G ) y la brecha espectral d − λ 2 de G . Una desigualdad debida a Dodziuk [9] e independientemente a Alon y Milman [10] afirma 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 menos no trivial del laplaciano normalizado y es la constante de Cheeger (normalizada)
donde es la suma de los grados de los vértices en .
Hay un valor propio vinculado a conjuntos independientes en gráficos regulares , originalmente debido a Alan J. Hoffman y Philippe Delsarte. [13]
Supongamos que es un gráfico 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 la intersección de familias de subespacios sobre campos finitos . [14]
Para gráficas 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 consecuencia de una desigualdad más general (págs. 109 en [12] ): donde es un conjunto independiente de vértices y denota la suma de grados de vértices en .
La teoría de grafos espectrales surgió en las décadas de 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 más tarde. [15] La monografía de 1980 Spectra of Graphs [16] de Cvetković, Doob y Sachs resumió casi toda la investigación hasta la fecha en el área. En 1988 fue actualizado por la encuesta Resultados Recientes en la Teoría de Espectros de Grafos . [17] La tercera edición de Spectra of Graphs (1995) contiene un resumen de las contribuciones recientes al tema. [15] El análisis geométrico discreto creado y desarrollado por Toshikazu Sunada en la década de 2000 se ocupa de la teoría de grafos espectrales en términos de laplacianos discretos asociados con gráficos ponderados, [18] y encuentra aplicación en varios campos, incluido el análisis de formas . En los años más recientes, la teoría de gráficos espectrales se ha expandido a gráficos con variación de vértices que a menudo se encuentran en muchas aplicaciones de la vida real. [19] [20] [21] [22]
{{cite book}}
: Mantenimiento CS1: posdata ( enlace ){{cite book}}
: Mantenimiento CS1: falta el editor de la ubicación ( enlace ){{cite book}}
: Mantenimiento CS1: posdata ( enlace )