La teoría algebraica de grafos es una rama de las matemáticas en la que se aplican métodos algebraicos a problemas sobre grafos . Esto contrasta con los enfoques geométricos , combinatorios o algorítmicos . Existen tres ramas principales de la teoría algebraica de grafos, que implican el uso del álgebra lineal , el uso de la teoría de grupos y el estudio de los invariantes de grafos .
La primera rama de la teoría de grafos algebraicos implica el estudio de grafos en conexión con el álgebra lineal . Especialmente, estudia el espectro de la matriz de adyacencia , o la matriz laplaciana de un grafo (esta parte de la teoría de grafos algebraicos también se llama teoría de grafos espectrales ). Para el grafo 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 propiedades del espectro con otras propiedades de grafos . Como un ejemplo simple, un grafo conexo con diámetro D tendrá al menos D +1 valores distintos en su espectro. [1] Se han utilizado aspectos de los espectros de grafos para analizar la sincronizabilidad de redes .
La segunda rama de la teoría de grafos algebraicos implica el estudio de los grafos en conexión con la teoría de grupos , particularmente los grupos de automorfismos y la teoría geométrica de grupos . El enfoque se centra en varias familias de grafos basados en la simetría (como grafos simétricos , grafos transitivos de vértice , grafos transitivos de arista , grafos transitivos de distancia , grafos regulares de distancia y grafos fuertemente regulares ), y en las relaciones de inclusión entre estas familias. Algunas de estas categorías de grafos son lo suficientemente dispersas como para que se puedan elaborar listas de grafos. Por 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 grafos simétricos conocidos como grafos de Cayley , y estos tienen propiedades relacionadas con la estructura del grupo. [1]
Esta segunda rama de la teoría de grafos algebraicos 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 grafo altamente simétrico, como el grafo de Petersen, tiene pocos valores distintos [1] (el grafo de Petersen tiene 3, que es el mínimo posible, dado su diámetro). Para los grafos de Cayley, el espectro puede relacionarse directamente con la estructura del grupo, en particular con sus caracteres irreducibles . [1] [3]
Finalmente, la tercera rama de la teoría de grafos algebraicos se ocupa de las propiedades algebraicas de los invariantes de grafos, y especialmente del polinomio cromático , el polinomio de Tutte y los invariantes de nudos . El polinomio cromático de un grafo, por ejemplo, cuenta el número de sus coloraciones de vértice adecuadas . Para el grafo de Petersen, este polinomio es . [1] En particular, esto significa que el grafo de Petersen no se puede colorear correctamente con uno o dos colores, pero se puede colorear de 120 formas diferentes con 3 colores. Gran parte del trabajo en esta área de la teoría de grafos algebraicos estuvo motivado por los intentos de demostrar el teorema de los cuatro colores . Sin embargo, todavía hay muchos problemas abiertos , como la caracterización de grafos que tienen el mismo polinomio cromático y la determinación de qué polinomios son cromáticos.
Medios relacionados con Teoría de grafos algebraicos en Wikimedia Commons
