En teoría de grafos , la circunferencia de un gráfico no dirigido es la longitud de un ciclo más corto contenido en el gráfico. [1] Si el gráfico no contiene ningún ciclo (es decir, es un bosque ), su circunferencia se define como infinita . [2] Por ejemplo, un (cuadrado) de 4 ciclos 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 gráfico con una circunferencia de cuatro o más no tiene triángulos .
Una gráfica cúbica (todos los vértices tienen grado tres) de circunferencia g que es lo más pequeña posible se conoce como g - jaula (o como (3, g ) -jaula). El gráfico de Petersen es el único de 5 jaulas (es el gráfico cúbico más pequeño de circunferencia 5), el gráfico de Heawood es el único de 6 jaulas, el gráfico de McGee es el único de 7 jaulas y el de Tutte ocho jaulas es el único de 8 jaulas. jaula. [3] Pueden existir varias jaulas para una circunferencia determinada. Por ejemplo, hay tres 10 jaulas no isomorfas, cada una con 70 vértices: la jaula de 10 Balaban , el gráfico de Harries y el gráfico de Harries-Wong .
Para cualquier número entero positivo g y χ , existe un gráfico con circunferencia al menos g y número cromático al menos χ ; por ejemplo, el gráfico de Grötzsch no tiene triángulos y tiene un número cromático 4, y al repetir la construcción mycielskiana utilizada para formar el gráfico de Grötzsch se obtienen gráficos sin triángulos con un 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 gráfico aleatorio en n vértices, formado al elegir independientemente si incluir cada borde con probabilidad n (1– g )/ g , tiene, con probabilidad que tiende a 1 cuando n tiende al infinito, en la mayoría de los n ⁄ 2 ciclos de longitud g o menos, pero no tiene un conjunto independiente de tamaño n ⁄ 2 k . Por lo tanto, eliminar un vértice de cada ciclo corto deja 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 gran circunferencia y número cromático 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 menor duración de un ciclo no trivial, la circunferencia admite generalizaciones naturales como la 1-sístole o sístoles superiores en geometría sistólica .
La circunferencia es el concepto dual de la conectividad de borde , en el sentido de que la circunferencia de un gráfico plano es la conectividad de borde de su gráfico dual , y viceversa. Estos conceptos están unificados en la teoría matroide por la circunferencia de una matroide , el tamaño del conjunto dependiente más pequeño de la matroide. Para una matroide gráfica , la circunferencia de la matroide es igual a la circunferencia del gráfico subyacente, mientras que para una matroide cográfica es igual a la conectividad de borde. [6]
La circunferencia de un gráfico no dirigido se puede calcular ejecutando una búsqueda en amplitud desde cada nodo, con complejidad donde es el número de vértices del gráfico y es el número de aristas. [7] Una optimización práctica es limitar la profundidad del BFS a una profundidad que dependa 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 gráfico es plano. [10] En términos de límites inferiores, calcular la circunferencia de un gráfico es al menos tan difícil como resolver el problema de encontrar triángulos en el gráfico.
{{cite web}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )