Circunferencia (teoría de grafos)

En teoría de grafos , la circunferencia de un grafo no dirigido es la longitud del ciclo más corto contenido en el grafo. ^{[ 1 ]} Si el grafo no contiene ningún ciclo (es decir, es un bosque ), su circunferencia se define como infinito . ^{[ 2 ]} Por ejemplo, un 4-ciclo (cuadrado) tiene circunferencia 4. Una cuadrícula también tiene circunferencia 4, y una malla triangular tiene circunferencia 3. Un grafo con circunferencia cuatro o más está libre de triángulos .

Un grafo cúbico (todos los vértices tienen grado tres) de circunferencia g que es lo más pequeño posible se conoce como una g - jaula (o como una (3, g ) -jaula). El grafo de Petersen es la única 5-jaula (es el grafo cúbico más pequeño de circunferencia 5), ​​el grafo de Heawood es la única 6-jaula, el grafo de McGee es la única 7-jaula y la ocho-jaula de Tutte es la única 8-jaula. ^{[ 3 ]} Puede haber múltiples jaulas para una circunferencia dada. Por ejemplo, hay tres 10-jaulas no isomorfas, cada una con 70 vértices: la 10-jaula de Balaban , el grafo de Harries y el grafo de Harries-Wong .

• 
  El gráfico de Petersen tiene una circunferencia de 5
• 
  El gráfico de Heawood tiene una circunferencia de 6
• 
  El gráfico de McGee tiene una circunferencia de 7
• 
  El gráfico de Tutte-Coxeter ( jaula de ocho de Tutte ) tiene una circunferencia de 8

Para cualesquiera enteros positivos g y χ , existe un grafo con circunferencia al menos g y número cromático al menos χ ; por ejemplo, el grafo de Grötzsch no tiene triángulos y tiene número cromático 4, y al repetir la construcción de Mycielskian utilizada para formar el grafo de Grötzsch se obtienen grafos sin triángulos de número cromático arbitrariamente grande. Paul Erdős fue el primero en demostrar el resultado general, utilizando el método probabilístico . ^{[ 4 ]} Más precisamente, demostró que un grafo aleatorio de n vértices, formado al elegir independientemente si se incluye cada arista con probabilidad n ^{(1– g )/ g} , tiene, con probabilidad que tiende a 1 cuando n tiende a infinito, como máximo ⁠ n / 2 ⁠ ciclos de longitud g o menos, pero no tiene un conjunto independiente de tamaño ⁠ n / 2 k ⁠ . Por lo tanto, al eliminar un vértice de cada ciclo corto se obtiene un grafo más pequeño con una circunferencia mayor que g , en el que cada clase de color de una coloración debe ser pequeña y que, por lo tanto, requiere al menos k colores en cualquier coloración.

Se pueden construir grafos explícitos, aunque grandes, con gran circunferencia y número cromático como ciertos grafos de Cayley de grupos lineales sobre cuerpos finitos . ^{[ 5 ]} Estos notables grafos de Ramanujan también tienen un gran coeficiente de expansión .

La circunferencia impar y la circunferencia par de un gráfico son, respectivamente, las longitudes del ciclo impar más corto y del ciclo par más corto.

ElLa circunferencia de un gráfico es la longitud delmás largo(simple), no del más corto.

Considerada como la longitud mínima de un ciclo no trivial, la circunferencia admite generalizaciones naturales como la 1-sístole o sístoles superiores en la geometría sistólica .

La circunferencia es el concepto dual de la conectividad de aristas , en el sentido de que la circunferencia de un grafo planar es la conectividad de aristas de su grafo dual , y viceversa. Estos conceptos se unifican en la teoría de matroides mediante la circunferencia de un matroide , que es el tamaño del conjunto dependiente más pequeño en el matroide. Para un matroide gráfico , la circunferencia del matroide es igual a la circunferencia del grafo subyacente, mientras que para un matroide cográfico es igual a la conectividad de aristas. ^{[ 6 ]}

La circunferencia de un grafo no dirigido se puede calcular realizando una búsqueda en anchura desde cada nodo, con complejidad${\displaystyle O(nm)}$dónde${\displaystyle n}$es el número de vértices del grafo y${\displaystyle m}$es el número de aristas. ^{[ 7 ]} Una optimización práctica consiste en limitar la profundidad de la BFS a una profundidad que dependa de la longitud del ciclo más pequeño descubierto hasta el momento. ^{[ 8 ]} Se conocen mejores algoritmos en el caso en que la circunferencia es par ^{[ 9 ]} y cuando el grafo es planar. ^{[ 10 ]} En términos de cotas inferiores, calcular la circunferencia de un grafo es al menos tan difícil como resolver el problema de encontrar triángulos en el grafo.