Teoría de grafos algebraicos

La teoría algebraica de grafos  es una dirección en la teoría de grafos que aplica métodos algebraicos a problemas de teoría de grafos (además de direcciones geométricas , combinatorias y algorítmicas ). A su vez, la teoría algebraica de grafos se divide en tres ramas: algebraica lineal , teórica de grupos y estudio de invariantes de grafos .

Álgebra lineal

Una característica representativa de la rama algebraica lineal es la teoría de grafos espectrales , en la que se estudian los espectros de la matriz de adyacencia o la matriz de Kirchhoff de un grafo. Para el gráfico de Petersen , por ejemplo, el espectro de la matriz adyacente es (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Algunos teoremas relacionan las propiedades del espectro con otras gráficas invariantes . Como ejemplo simple, un gráfico conexo con un diámetro tendrá al menos valores distintos en su espectro [1] . Las propiedades del espectro gráfico se utilizan para analizar la sincronicidad de la red .

Teoría de grupos

En la rama de la teoría de grupos se utilizan métodos del álgebra general y la combinatoria algebraica , la teoría geométrica de grupos es muy utilizada ; una de las principales construcciones estudiadas son los automorfismos de grafos (que forman el grupo ). Se presta atención a varias familias de grafos basados ​​en la simetría (como grafos simétricos, grafos transitivos de vértice, grafos transitivos de borde, grafos transitivos de distancia , grafos regulares de distancia y grafos fuertemente regulares ), y las conexiones entre estas familias. Algunas de estas categorías tienen una pequeña cantidad de gráficos, por lo que se pueden enumerar todas . Por el teorema de Frucht , todos los grupos se pueden representar como grupos de automorfismos de grafos conectados (además, grafos cúbicos ) [2] . Otra conexión con la teoría de grupos es que, dado cualquier grupo, se pueden formar gráficos conocidos como gráficos de Cayley , y tienen propiedades relacionadas con la estructura del gráfico [1] .

La rama de grupo está estrechamente relacionada con la algebraica lineal, ya que las propiedades de simetría de un gráfico se reflejan en su espectro. En particular, el espectro de un gráfico con alta simetría, como el gráfico de Petersen, tiene pocos valores propios distintos [1] (el gráfico de Petersen tiene 3 valores, que es el número más pequeño posible para un gráfico con un diámetro como el Petersen grafico). Para los gráficos de Cayley, el espectro se puede relacionar directamente con la estructura del grupo, en particular, con sus representaciones irreducibles [1] [3] .

Graficar invariantes

Las propiedades algebraicas de las invariantes de gráficos , como polinomios cromáticos, polinomios de Tatta , invariantes de nudos , permiten estudiar la estructura de las gráficas por medios algebraicos. Por ejemplo, el polinomio cromático de un grafo, cuenta el número de colores correctos de sus vértices ; para el gráfico 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 con tres colores se puede colorear de 120 formas diferentes. Gran parte del trabajo en esta área está asociado con los intentos de probar el teorema de los cuatro colores . Hay muchas preguntas abiertas relacionadas con las invariantes, como determinar qué gráficos tienen el mismo polinomio cromático y qué polinomios son cromáticos.

Véase también

Notas

  1. ↑ 1 2 3 4 5 Biggs, 1993 .
  2. ↑ Frucht, 1949 .
  3. ↑ Babaí, 1996 .

Literatura