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 una circunferencia de 4. Una cuadrícula también tiene una circunferencia de 4, y una malla triangular tiene una circunferencia de 3. Un grafo con una circunferencia de cuatro o más no tiene 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 g - jaula (o como (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] Pueden existir 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 .
Para cualquier entero positivo 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 repetir la construcción mycielskiana utilizada para formar el grafo de Grötzsch produce 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, mostró que un grafo aleatorio en n vértices, formado eligiendo independientemente si incluir 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 gráfico 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 gráficos explícitos, aunque grandes, con circunferencia y número cromático altos como ciertos gráficos de Cayley de grupos lineales sobre campos finitos . [5] Estos notables gráficos de Ramanujan también tienen un gran coeficiente de expansión .
La circunferencia impar y la circunferencia par de un gráfico son las longitudes de un ciclo impar más corto y un ciclo par más corto respectivamente.
ElLa circunferencia de un gráfico es la longitud delmás largo(simple), en lugar del más corto.
Considerada como la longitud mínima de un ciclo no trivial, la circunferencia admite generalizaciones naturales como la sístole 1 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 plano es la conectividad de aristas de su grafo dual , y viceversa. Estos conceptos están unificados en la teoría de matroides por la circunferencia de un matroide , 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 ejecutando una búsqueda en amplitud desde cada nodo, con una complejidad donde es el número de vértices del grafo y es el número de aristas. [7] Una optimización práctica es limitar la profundidad de la BFS a una profundidad que depende de la longitud del ciclo más pequeño descubierto hasta ahora. [8] Se conocen mejores algoritmos en el caso en que la circunferencia es par [9] y cuando el grafo es plano. [10] En términos de límites inferiores, calcular la circunferencia de un grafo es al menos tan difícil como resolver el problema de búsqueda de triángulos en el grafo.
{{cite web}}: CS1 maint: varios nombres: lista de autores ( enlace )