La teoría de grafos algebraicas es una rama de las matemáticas en la que se aplican métodos algebraicos a problemas sobre gráficas . Esto contrasta con los enfoques geométricos , combinatorios o algorítmicos . Hay tres ramas principales de la teoría de grafos algebraicas, que implican el uso del álgebra lineal , el uso de la teoría de grupos y el estudio de invariantes de grafos .
La primera rama de la teoría de grafos algebraica implica el estudio de gráficos en relación con el álgebra lineal . Especialmente, estudia el espectro de la matriz de adyacencia , o matriz laplaciana de un grafo (esta parte de la teoría algebraica de grafos también se llama teoría de grafos espectrales ). Para el gráfico de Petersen , por ejemplo, el espectro de la matriz de adyacencia es (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Varios teoremas relacionan las propiedades del espectro con otras propiedades del gráfico . Como ejemplo simple, un gráfico conectado con diámetro D tendrá al menos D +1 valores distintos en su espectro. [1] Se han utilizado aspectos de los espectros gráficos para analizar la sincronizabilidad de redes .
La segunda rama de la teoría de grafos algebraica implica el estudio de grafos en conexión con la teoría de grupos , particularmente los grupos de automorfismos y la teoría de grupos geométricos . La atención se centra en varias familias de gráficos basados en simetría (como gráficos simétricos , gráficos transitivos de vértice , gráficos transitivos de aristas , gráficos transitivos de distancia , gráficos regulares de distancia y gráficos fuertemente regulares ), y en las relaciones de inclusión entre estas familias. Algunas de estas categorías de gráficos son lo suficientemente escasas como para que se puedan elaborar listas de gráficos. Según el teorema de Frucht , todos los grupos pueden representarse como el grupo de automorfismos de un grafo conexo (de hecho, de un grafo cúbico ). [2] Otra conexión con la teoría de grupos es que, dado cualquier grupo, se pueden generar gráficos simétricos conocidos como gráficos de Cayley , y estos tienen propiedades relacionadas con la estructura del grupo. [1]
Esta segunda rama de la teoría de grafos algebraica está relacionada con la primera, ya que las propiedades de simetría de un grafo se reflejan en su espectro. En particular, el espectro de un gráfico altamente simétrico, como el gráfico de Petersen, tiene pocos valores distintos [1] (el gráfico de Petersen tiene 3, que es el mínimo posible, dado su diámetro). Para los gráficos de Cayley, el espectro se puede relacionar directamente con la estructura del grupo, en particular con sus caracteres irreductibles . [1] [3]
Finalmente, la tercera rama de la teoría de grafos algebraica se refiere a las propiedades algebraicas de los invariantes de los grafos, y especialmente el polinomio cromático , el polinomio de Tutte y los invariantes de nudo . El polinomio cromático de un gráfico, por ejemplo, cuenta el número de coloraciones propias de sus vértices . Para la gráfica de Petersen, este polinomio es . [1] En particular, esto significa que el gráfico de Petersen no se puede colorear correctamente con uno o dos colores, pero se puede colorear de 120 maneras diferentes con 3 colores. Gran parte del trabajo en esta área de la teoría de grafos algebraicos estuvo motivado por intentos de demostrar el teorema de los cuatro colores . Sin embargo, todavía quedan muchos problemas abiertos , como caracterizar gráficas que tienen el mismo polinomio cromático y determinar qué polinomios son cromáticos.
Medios relacionados con la teoría de grafos algebraicos en Wikimedia Commons
