Circunferencia (teoría de grafos)
En teoría de grafos, la circunferencia de un gráfico no dirigido es la longitud del ciclo más corto contenido en el gráfico. Si el gráfico no contiene ningún ciclo (es decir, es un bosque), su circunferencia se define como infinita. Por ejemplo, un ciclo de 4 (cuadrado) tiene un perímetro 4. Una cuadrícula también tiene un perímetro 4 y una malla triangular tiene un perímetro 3. Un gráfico con un perímetro cuatro o más no tiene triángulos.
Jaulas
Un gráfico 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 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 Tutte de ocho jaulas es el único de 8 jaula. Pueden existir múltiples jaulas para una circunferencia determinada. Por ejemplo, hay tres jaulas de 10 no isomorfas, cada una con 70 vértices: la jaula de 10 de Balaban, el gráfico de Harries y el gráfico de Harries-Wong.
El gráfico Petersen tiene una circunferencia de 5
El gráfico Heawood tiene una circunferencia de 6
El gráfico McGee tiene una circunferencia de 7
El gráfico Tutte-CoxeterTutte ocho jaula) tiene una circunferencia de 8
Coloreado de circunferencia y gráfico
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 el número cromático 4, y la repetición de la construcción de Mycielskian utilizada para formar el gráfico de Grötzsch produce 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. Más precisamente, mostró que un grafo aleatorio en n vértices, formado eligiendo independientemente si incluir cada borde con probabilidad n(1–g)/g, tiene, con probabilidad tiende a 1 cuando n tiende a infinito, como mucho n⁄2 ciclos de longitud g o menos, pero no tiene un conjunto independiente de funciones de tamaño n⁄2k . 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 un colorante debe ser pequeño y por lo tanto requiere al menos k colores en cualquier coloración.
Gráficos explícitos, aunque grandes, con gran circunferencia y número cromático se pueden construir como ciertos gráficos de Cayley de grupos lineales sobre campos finitos. Estos notables gráficos de Ramanujan también tienen un gran coeficiente de expansión.
Conceptos relacionados
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.
La circunferencia de un gráfico es la longitud del ciclo más largo (simple), en lugar del más corto.
Considerado como la duración mínima de un ciclo no trivial, el perímetro 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 de las matroides 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 del borde.
Contenido relacionado
Piet Hein (científico)
Grupo unitario especial
Números cuneiformes babilónicos