Hispanopedia Wiki
Articulo de referencia

Teoría espectral de grafos

En matemáticas , la teoría espectral de grafos es el estudio de las propiedades de un grafo en relación con el polinomio característico , los valores propios y los vectores prop...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas , la teoría espectral de grafos 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 enteros algebraicos reales .

Si bien la matriz de adyacencia depende del etiquetado de los vértices, su espectro es un invariante de grafo , aunque no completo .

La teoría espectral de grafos también se ocupa de parámetros de grafos 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 .

gráficos coespectrales

Dos grafos se denominan coespectrales o isoespectrales si las matrices de adyacencia de los grafos son isoespectrales , es decir, si las matrices de adyacencia tienen los mismos valores propios con multiplicidad.

Dos eneaedros coespectrales, los gráficos poliédricos coespectrales más pequeños posibles.

Los grafos coespectrales no tienen por qué ser isomorfos , pero los grafos isomorfos siempre son coespectrales.

Gráficos determinados por su espectro

Un gráficoGRAMO{\displaystyle G}Se dice que está determinado por su espectro si cualquier otro gráfico con el mismo espectro queGRAMO{\displaystyle G}es isomorfo aGRAMO{\displaystyle G}.

Algunos primeros ejemplos de familias de gráficos que están determinadas por su espectro incluyen:

compañeros coespectrales

Se dice que dos grafos son coespectrales si son coespectrales pero no 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. [ 1 ] El primer ejemplo de gráficos coespectrales fue reportado por Collatz y Sinogowitz [ 2 ] en 1957.

El par más pequeño de poliedros coespectrales son eneaedros con ocho vértices cada uno. [ 3 ]

Cómo encontrar gráficos coespectrales

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 grafos regulares son coespectrales si y solo si sus complementos son coespectrales. [ 5 ]

Un par de grafos regulares en distancia son coespectrales si y solo si tienen la misma matriz de intersección.

Los gráficos coespectrales también pueden construirse mediante el método de Sunada . [ 6 ]

Otra fuente importante de grafos coespectrales son los grafos de colinealidad de puntos y los grafos de intersección de líneas de geometrías de puntos y líneas . Estos grafos son siempre coespectrales, pero a menudo no son isomorfos. [ 7 ]

Desigualdad de Cheeger

La famosa desigualdad de Cheeger de la geometría riemanniana tiene un análogo discreto que involucra la matriz laplaciana; este es quizás el teorema más importante en la teoría espectral de grafos 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 autovalor de su matriz laplaciana.

Cheeger constante

La constante de Cheeger (también llamada número de Cheeger o número isoperimétrico ) de un grafo es una medida numérica que indica si un grafo presenta o no un "cuello de botella". La constante de Cheeger, como medida de la presencia de "cuellos de botella", es de gran interés en diversas áreas: por ejemplo, la construcción de redes informáticas bien conectadas , el barajado de cartas y la topología de baja dimensión (en particular, el estudio de variedades hiperbólicas tridimensionales ).

De manera más formal, la constante de Cheeger h ( G ) de un grafo G con n vértices se define como

h(GRAMO)=min0<|S|≤norte2|∂(S)||S|,{\displaystyle h(G)=\min _{0<|S|\leq {\frac {n}{2}}}{\frac {|\partial (S)|}{|S|}},}

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 aristas de S , es decir, el conjunto de aristas con exactamente un extremo en S. [ 8 ]

Desigualdad de Cheeger

Cuando el grafo 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 ] establece que [ 11 ]

12(d−λ2)≤h(GRAMO)≤2d(d−λ2).{\displaystyle {\frac {1}{2}}(d-\lambda _{2})\leq h(G)\leq {\sqrt {2d(d-\lambda _{2})}}.}

Esta desigualdad está estrechamente relacionada con la cota de Cheeger para cadenas de Markov y puede verse como una versión discreta de la desigualdad de Cheeger en geometría riemanniana .

Para grafos conexos generales que no son necesariamente regulares, Chung [ 12 ] da una desigualdad alternativa : 35

12λ≤h(GRAMO)≤2λ,{\displaystyle {\frac {1}{2}}{\lambda }\leq {\mathbf {h} }(G)\leq {\sqrt {2\lambda }},}

dóndeλ{\displaystyle \lambda }es el autovalor no trivial menos significativo del laplaciano normalizado, yh(GRAMO){\displaystyle {\mathbf {h} }(G)}es la constante de Cheeger (normalizada)

h(GRAMO)=min∅≠S⊂V(GRAMO)|∂(S)|min(vol(S),vol(S¯)){\displaystyle {\mathbf {h} }(G)=\min _{\emptyset \not =S\subset V(G)}{\frac {|\partial (S)|}{\min({\mathrm {vol} }(S),{\mathrm {vol} }({\bar {S}}))}}}

dóndevol(Y){\displaystyle {\mathrm {vol} }(Y)}es la suma de los grados de los vértices enY{\displaystyle Y}.

Desigualdad de Hoffman-Delsarte

Existe una cota de autovalores para conjuntos independientes en grafos regulares , debida originalmente a Alan J. Hoffman y Philippe Delsarte. [ 13 ]

Supongamos queGRAMO{\displaystyle G}es unk{\displaystyle k}-gráfico regular ennorte{\displaystyle n}vértices con el menor valor propioλmetroinorte{\displaystyle \lambda _ {\mathrm {min} }}. Entonces:α(GRAMO)≤norte1−kλmetroinorte{\displaystyle \alpha (G)\leq {\frac {n}{1-{\frac {k}{\lambda _{\mathrm {min} }}}}}}dóndeα(GRAMO){\displaystyle \alpha (G)}denota su número de independencia .

Esta cota se ha aplicado para establecer, por ejemplo, demostraciones algebraicas del teorema de Erdős-Ko-Rado y su análogo para familias intersecantes de subespacios sobre cuerpos finitos . [ 14 ]

Para grafos generales que no son necesariamente regulares, se puede derivar una cota superior similar para el número de independencia utilizando el valor propio máximo. λmetroaincógnita′{\displaystyle \lambda '_{max}}del laplaciano normalizado [ 12 ] deGRAMO{\displaystyle G}: α(GRAMO)≤norte(1−1λmetroaincógnita′)metroaincógnitadmigramometroinortedmigramo{\displaystyle \alpha (G)\leq n(1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\frac {\mathrm {maxdeg} }{\mathrm {mindeg} }}} dóndemetroaincógnitadmigramo{\displaystyle {\mathrm {maxdeg} }}ymetroinortedmigramo{\displaystyle {\mathrm {mindeg} }}denotan el grado máximo y mínimo enGRAMO{\displaystyle G}, respectivamente. Esto es consecuencia de una desigualdad más general (págs. 109 en [ 12 ] ): vol(incógnita)≤(1−1λmetroaincógnita′)vol(V(GRAMO)){\displaystyle {\mathrm {vol} }(X)\leq (1-{\frac {1}{\lambda '_{\mathrm {max} }}}){\mathrm {vol} }(V(G))} dóndeincógnita{\displaystyle X}es un conjunto independiente de vértices yvol(Y){\displaystyle {\mathrm {vol} }(Y)}denota la suma de los grados de los vértices enY{\displaystyle Y}.

Reseña histórica

La teoría espectral de grafos 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 realizada hasta la fecha en el área. En 1988, se actualizó con el estudio 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 al tema. [ 15 ]

El campo del análisis geométrico discreto, creado y desarrollado por Toshikazu Sunada en la década de 2000, se ocupa de la teoría espectral de grafos en términos de laplacianos discretos asociados con grafos ponderados. [ 18 ] Encuentra aplicación en varios otros campos, incluido el análisis de formas .

Un desarrollo más reciente en la teoría espectral de grafos es el análisis de frecuencia de vértices, un conjunto de técnicas para resolver problemas en muchas aplicaciones de la vida real, como el procesamiento de señales . [ 19 ] [ 20 ] [ 21 ] [ 22 ]

Véase también

Referencias

  1. ↑ Weisstein, Eric W. "Gráficos coespectrales" . MathWorld .
  2. ^ Collatz, L. y Sinogowitz, U. "Spektren endlicher Grafen". Abh. Matemáticas. Sem. Univ. Hamburgo 21, 63–77, 1957.
  3. ↑ Hosoya, Haruo ; Nagashima, Umpei; Hyugaji, Sachiko (1994), "Grafos gemelos topológicos. Par más pequeño de grafos poliédricos isoespectrales con ocho vértices", Journal of Chemical Information and Modeling , 34 (2): 428–431 , doi : 10.1021/ci00018a033.
  4. ^ Schwenk (1973) , págs .
  5. ↑ Godsil, Chris (7 de noviembre de 2007). "¿Son casi todos los gráficos coespectrales?" (PDF) .
  6. ↑ Sunada, Toshikazu (1985), "Recubrimientos riemannianos y variedades isoespectrales", Annals of Mathematics , 121 (1): 169–186 , doi : 10.2307/1971195 , JSTOR 1971195 .
  7. ↑ Brouwer y Haemers 2011
  8. ↑ Definición 2.1 en Hoory, Linial y Wigderson (2006)
  9. ↑ J.Dodziuk, Ecuaciones en diferencias, desigualdad isoperimétrica y transitoriedad de ciertos paseos aleatorios, Trans. Amer. Math. Soc. 284 (1984), n.º 2, 787-794.
  10. ↑ Alon y Spencer 2011 .
  11. ↑ Teorema 2.4 en Hoory, Linial y Wigderson (2006)
  12. 1 2 3 Chung, Fan (1997). American Mathematical Society (ed.). Teoría espectral de grafos . Providence, RI ISBN 0821803158MR 1421568 [ los primeros 4 capítulos están disponibles en el sitio web] {{cite book}}: CS1 mantenimiento: postscript ( enlace )
  13. ^ Godsil, Chris (mayo de 2009). "Teoremas de Erdős-Ko-Rado" (PDF) .
  14. ↑ Godsil, CD; Meagher, Karen (2016). Teoremas de Erdős-Ko-Rado : enfoques algebraicos . Cambridge, Reino Unido. ISBN  9781107128446OCLC 935456305​​ {{cite book}}: CS1 mantenimiento: falta el editor de ubicación ( enlace )
  15. ^ Espacios propios de gráficos , por Dragoš Cvetković , Peter Rowlinson, Slobodan Simić (1997) ISBN 0-521-57352-1
  16. ↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs , Espectros de gráficos (1980)
  17. ↑ Cvetković, Dragoš M.; Doob, Michael; Gutman, Ivan; Torgasev, A. (1988). Resultados recientes en la teoría de espectros de grafos . Anales de Matemáticas Discretas. ISBN 0-444-70361-6.
  18. ↑ Sunada, Toshikazu (2008), "Análisis geométrico discreto", Análisis de grafos y sus aplicaciones , Actas de simposios de matemáticas puras, vol. 77, pp. 51–83 , doi : 10.1090/pspum/077/2459864 , ISBN   9780821844717.
  19. ↑ Shuman, David I; Ricaud, Benjamin; Vandergheynst, Pierre (marzo de 2016). "Análisis de frecuencia de vértices en grafos". Applied and Computational Harmonic Analysis . 40 (2): 260– 291. arXiv : 1307.5708 . Bibcode : 2016ACHA...40..260S . doi : 10.1016/j.acha.2015.02.005 . ISSN 1063-5203 . S2CID 16487065 .  
  20. ↑ Stankovic, Ljubisa; Dakovic, Milos; Sejdic, Ervin (julio de 2017). "Análisis de frecuencia de vértice: una forma de localizar componentes espectrales de grafos [notas de clase]". IEEE Signal Processing Magazine . 34 (4): 176– 182. Bibcode : 2017ISPM...34..176S . doi : 10.1109/msp.2017.2696572 . ISSN 1053-5888 . S2CID 19969572 .  
  21. ↑ Sakiyama, Akie; Watanabe, Kana; Tanaka, Yuichi (septiembre de 2016). "Ondículas gráficas espectrales y bancos de filtros con bajo error de aproximación". IEEE Transactions on Signal and Information Processing over Networks . 2 (3): 230– 245. Bibcode : 2016ITSIP...2..230S . doi : 10.1109/tsipn.2016.2581303 . ISSN 2373-776X . S2CID 2052898 .  
  22. ↑ Behjat, Hamid; Richter, Ulrike; Van De Ville, Dimitri; Sornmo, Leif (2016-11-15). "Signal-Adapted Tight Frames on Graphs" . IEEE Transactions on Signal Processing . 64 (22): 6017– 6029. Bibcode : 2016ITSP...64.6017B . doi : 10.1109/tsp.2016.2591513 . ISSN 1053-587X . S2CID 12844791 .  
  • Alon; Spencer (2011), El método probabilístico , Wiley.
  • Brouwer, Andries ; Haemers, Willem H. (2011), Espectros de gráficos (PDF) , Springer
  • Hoory; Linial; Wigderson (2006), Grafos expansores y sus aplicaciones (PDF)
  • Chung, Fan (1997). American Mathematical Society (ed.). Teoría espectral de grafos . Providence, RI ISBN 0821803158MR 1421568 [ los primeros 4 capítulos están disponibles en el sitio web] {{cite book}}: CS1 mantenimiento: postscript ( enlace )
  • Schwenk, AJ (1973). «Casi todos los árboles son coespectrales». En Harary, Frank (ed.). Nuevas direcciones en la teoría de grafos . Nueva York: Academic Press . ISBN 012324255XOCLC 890297242​​ 
  • Bogdan, Nica (2018). «Una breve introducción a la teoría espectral de grafos» . Zúrich: EMS Press. ISBN 978-3-03719-188-0.
  • Pavel Kurasov (2024), Geometría espectral de grafos , Springer (Birkhauser), Acceso abierto (CC4.0).
  • Naderi, Kiyan; Pankrashkin, Konstantin (2025), Introducción a la teoría espectral de grafos , Springer, doi : 10.1007/978-3-032-01708-6 , ISBN 978-3-032-01708-6
  • Spielman, Daniel (2011). "Teoría espectral de grafos" (PDF) .[capítulo de Computación Científica Combinatoria]
  • Spielman, Daniel (2007). "Teoría espectral de grafos y sus aplicaciones" .[Presentado en la Conferencia FOCS 2007]
  • Spielman, Daniel (2004). "Teoría espectral de grafos y sus aplicaciones" .[Página del curso y apuntes de clase]