La teoría de grafos algebraicos 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 . Hay tres ramas principales de la teoría de grafos algebraica, que involucran el uso de álgebra lineal , el uso de teoría de grupos y el estudio de invariantes de grafos .
Ramas de la teoría de grafos algebraicos
Usando álgebra lineal
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 gráfico (esta parte de la teoría de grafos algebraicos 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 espectros gráficos para analizar la sincronizabilidad de las redes .
Usando la teoría de grupos
Familias de gráficos definidas por sus automorfismos | ||||
---|---|---|---|---|
distancia-transitiva | → | distancia regular | ← | muy regular |
↓ | ||||
simétrico (arco-transitivo) | ← | t -transitivo, t ≥ 2 | simétrico sesgado | |
↓ | ||||
(si está conectado) vértice y borde transitivo | → | edge-transititive y regular | → | borde transitivo |
↓ | ↓ | ↓ | ||
vértice-transitivo | → | regular | → | (si es bipartito) birregular |
↑ | ||||
Gráfico de Cayley | ← | simétrico cero | asimétrico |
La segunda rama de la teoría de grafos algebraicos implica el estudio de grafos en conexión con la teoría de grupos , particularmente los grupos de automorfismo y la teoría de grupos geométricos . El foco se coloca en varias familias de gráficos basado en la simetría (tales como gráficos simétricos , gráficos de vértice-transitivo , gráficos de borde-transitivo , gráficos de distancia-transitivo , gráficos de distancia regular , 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 poder elaborar listas de gráficos. Según el teorema de Frucht , todos los grupos se pueden representar como el grupo de automorfismo de un gráfico conectado (de hecho, de un gráfico 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]
Estudiar invariantes de gráficos
Finalmente, la tercera rama de la teoría de grafos algebraicos se refiere a las propiedades algebraicas de los invariantes de los gráficos, y especialmente al polinomio cromático , el polinomio de Tutte y los invariantes de nudos . El polinomio cromático de un gráfico, por ejemplo, cuenta el número de coloraciones de vértice correspondientes . 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, sino que se puede colorear de 120 formas diferentes con 3 colores. Gran parte del trabajo en esta área de la teoría de grafos algebraicos fue motivado por intentos de probar el teorema de los cuatro colores . Sin embargo, todavía hay muchos problemas abiertos , como caracterizar gráficos que tienen el mismo polinomio cromático y determinar qué polinomios son cromáticos.
Ver también
- Teoría de grafos espectrales
- Combinatoria algebraica
- Conectividad algebraica
- Descomposición de Dulmage-Mendelsohn
- Propiedad gráfica
- Matriz de adyacencia
Referencias
- ^ a b c d e Biggs, Norman (1993), Teoría de gráficos algebraicos (2.a ed.), Cambridge: Cambridge University Press, ISBN 0-521-45897-8
- ^ R. Frucht . Gráficos de Grado 3 con grupo abstracto dado, Can. J. Math. 3 1949.
- ^ * Babai, L (1996), "Grupos de automorfismo, isomorfismo, reconstrucción" , en Graham, R; Grötschel, M ; Lovász, L (eds.), Handbook of Combinatorics , Elsevier, archivado desde el original el 11 de junio de 2010 , consultado el 27 de marzo de 2009
- Godsil, Chris ; Royle, Gordon (2001), Teoría de grafos algebraicos , Textos de posgrado en matemáticas, 207 , Nueva York: Springer-Verlag CS1 maint: parámetro desalentado ( enlace ).
enlaces externos
- Medios relacionados con la teoría de grafos algebraicos en Wikimedia Commons