Teoría de grafos espectrales

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 27 de octubre de 2021; las comprobaciones requieren 2 ediciones .

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 .

Gráficos isoespectrales

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] .

Desigualdad de Cheeger

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.

Constante de Cheeger

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] .

Desigualdad de Cheeger

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 .

Historia

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] .

Véase también

Notas

  1. ↑ Collatz, L. y Sinogowitz, U. Spektren endlicher Grafen, Abh. Matemáticas. Sem. Universidad Hamburgo. - 1957. - Nº 21 . — S. 63–77 .
  2. ↑ Weisstein, Eric W. Gráficos coespectrales  en el sitio web de Wolfram MathWorld .
  3. ↑ Haruo Hosoya, Umpei Nagashima, Sachiko Hyugaji. Gráficos gemelos topológicos. El par más pequeño de gráficos poliédricos isoespectrales con ocho vértices // Journal of Chemical Information and Modeling. - 1994. - T. 34 , núm. 2 . - S. 428-431 . -doi : 10.1021/ ci00018a033 .
  4. ↑ AJ Schwenk. Casi todos los árboles son coespectrales // Nuevas direcciones en la teoría de grafos / F. Harary. - Nueva York: Academic Press, 1973. - S. 275-307.
  5. ↑ Toshikazu Sunada. Coberturas riemannianas y variedades isoespectrales // Ann. de Matemáticas. - 1985. - T. 21 . - S. 169-186 .
  6. ↑ Hoory, Linial, Widgerson, 2006 , Definición 2.1.
  7. ↑ Alon, Spencer, 2011 .
  8. ↑ Hoory, Linial, Widgerson, 2006 , Teorema 2.4.
  9. ↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs. Espectros de grafos. — 1980.
  10. ↑ Dragoš M. Cvetković, Michael Doob, Horst Sachs, A. Torgasev. Resultados Recientes en la Teoría de Espectros de Grafos . - 1988. - (Anales de matemáticas discretas). — ISBN 0-444-70361-6 . Archivado el 5 de noviembre de 2017 en Wayback Machine .
  11. ↑ 1 2 Dragoš Cvetković, Peter Rowlinson, Slobodan Simić. Espacios propios de Grafos. - 1997. - ISBN 0-521-57352-1 .

Literatura

Enlaces