¿Cuáles son algunos sutil, o no evidente aplicaciones algebraico de la teoría de grafos? Obviamente, esto puede ser usado para estudiar cualquier cosa que implican directamente a los gráficos (por ejemplo, la página de wikipedia menciona synchronizability de redes), pero estoy interesado en los lugares donde no se podría pensar inmediatamente en la teoría de grafos a ser relevante.
Respuestas
¿Demasiados anuncios?
ASCII Advocate
Puntos
1959
Es más probable encontrar sutil, no evidentes aplicaciones algebraico de la teoría de grafos a la teoría de grafos.
Un famoso ejemplo es el Teorema de la Amistad
https://en.wikipedia.org/wiki/Friendship_graph#Friendship_theorem
que tiene una bonita prueba utilizando el espectro de la matriz de adyacencia.
Más recientemente, los grupos críticos de sandpiles en los gráficos son una de las principales de la teoría relativa a la geometría tropical. Hay fuertes analogías con el de Riemann-Roch teoría de los divisores en las curvas algebraicas.
Gráfico Laplacians son de enorme interés, y estrechamente relacionado con el anterior ejemplo.
Espectral de la incrustación de gráficos en el plano es otro buen uso de la matriz de adyacencia.
En aplicaciones fuera de la teoría de grafos, la estructura de un gráfico relevantes para el problema generalmente no es un bien oculto hecho. Si usted está buscando para aplicaciones algebraico de la teoría de grafos en general obvio gráfico de la estructura, tales como los enlaces químicos, hay bastante de eso.
Ashwin Ganesan
Puntos
1279
Una aplicación algebraico de la teoría de grafos es el análisis y diseño de topologías de las redes de interconexión. Las topologías que se utiliza para conectar procesadores en un superordenador, tienen un alto grado de simetría, y generalmente son los grafos de Cayley. Ver el artículo de Wikipedia sobre el Toro de interconexión, una topología utilizada en algunas de las supercomputadoras.
