Corona (teoría de grafos)

En teoría de grafos, una corona de 2n vértices es un grafo no dirigido con dos conjuntos de vértices u i y v i y aristas entre u i y v j si i ≠ j . Uno puede pensar en la corona como un gráfico bipartito completo del que se ha eliminado una combinación perfecta , como un gráfico bipartito doble que cubre el gráfico completo , o como un gráfico bipartito de Kneser H n ,1 que representa subconjuntos de 1 elemento y ( n − 1) elementos de un conjunto de n elementos con bordes entre dos subconjuntos si un subconjunto está contenido en el otro.

Ejemplos

Una corona con seis vértices forma un ciclo , y una corona con ocho vértices es isomorfa a un gráfico de cubo . En la configuración doble seis Schläfli de 12 líneas y 30 puntos en el espacio tridimensional, doce líneas se cruzan entre sí en un patrón de corona con 12 vértices.

Propiedades

El número de aristas en la corona es un número rectangular n ( n − 1). Su número acromático es n  — uno puede encontrar una coloración completa eligiendo un par { u i , v i } como clases de color [1] . Las coronas son gráficos simétricos y de distancia transitiva . Archdeacon et al [2] describen la división de los bordes de la corona en ciclos de igual longitud.

Una corona con 2n vértices se puede incrustar en un espacio euclidiano de cuatro dimensiones de tal manera que todas sus aristas tengan longitud uno. Sin embargo, dicha incrustación puede colocar vértices no adyacentes a una distancia de uno. La incrustación donde los bordes tienen una longitud de uno y la distancia entre los vértices no adyacentes no es igual a uno requiere al menos la dimensión n − 2. Esto muestra que para representar un gráfico como un gráfico de distancias unitarias y un gráfico de distancias estrictamente unitarias , se requieren dimensiones completamente diferentes [3 ] . El número mínimo de subgrafos bipartitos completos necesarios para cubrir los bordes de la corona (su dimensión bipartita o el tamaño de la cobertura mínima de la camarilla) es

es decir, la función inversa del coeficiente binomial central [4] .

El complemento de una corona de 2n vértices es el producto directo de los gráficos completos K 2 K n , lo que equivale a un gráfico de torres de 2 ×  n .

Aplicación

En la etiqueta  , las reglas tradicionales para sentar a los invitados en la mesa de la cena, los hombres y las mujeres deben alternarse y ninguna pareja casada debe sentarse una al lado de la otra. Un asiento que satisfaga estas reglas para un grupo de n parejas puede describirse como un ciclo corona hamiltoniano . El problema de contar el número de posibles disposiciones de asientos o, que es casi lo mismo [5] que el número de ciclos hamiltonianos en la corona, se conoce en combinatoria como problema del invitado . Para coronas con 6, 8, 10,... vértices, el número de ciclos hamiltonianos (orientados) es

2, 12, 312, 9600, 416880, 23879520, 1749363840,... Secuencia OEIS A094047 .

Las coronas se pueden usar para mostrar que un algoritmo de coloración codicioso se comporta mal en algunos casos: si los vértices de una corona se presentan al algoritmo en el orden u 0 , v 0 , u 1 , v 1 , etc., entonces se usa la coloración codiciosa n colores, aunque el número óptimo de colores es dos. Esta construcción se atribuye a Johnson [6] , y las propias coronas a veces se denominan gráficos de Johnson con la notación J n [7] . Fuhrer [8] usó coronas como parte de una construcción que muestra la complejidad de aproximar el problema del color.

Matushek [9] usó la distancia en coronas como un ejemplo de un espacio métrico que es difícil de incrustar en un espacio vectorial normado .

Como muestran Miklavic y Poroshnik [10] , las coronas se incluyen en un pequeño número de diferentes tipos de gráficos que son gráficos circulantes de distancia regular .

Agarwal y otros [11] describen polígonos que tienen coronas como gráficos de visibilidad . Los usan como ejemplo para mostrar que representar gráficos como una unión de gráficos bipartitos completos no siempre es eficiente en términos de memoria.

Una corona con 2n vértices con aristas orientadas de un lado al otro de un gráfico bipartito forma un ejemplo estándar de un conjunto parcialmente ordenado con dimensión de ordenación n .

Notas

  1. ↑ Amitabh Chaudhary, Sundar Vishwanathan. SODA '97: Actas del 8º Simposio ACM-SIAM sobre algoritmos discretos. - 1997. - S. 558-563 .
  2. ↑ D. Archidiácono, M. Debowsky, J. Dinitz, H. Gavlas. Sistemas de ciclos en el gráfico bipartito completo menos un factor // Matemáticas discretas . - 2004. - T. 284 , núm. 1-3 . - S. 37-43 . -doi : 10.1016/ j.disco.2003.11.021 .
  3. ↑ Paul Erdős, Miklos Simonovits. Sobre el número cromático de grafos geométricos // Ars Combinatoria. - 1980. - T. 9 . - S. 229-246 .
  4. ↑ Dominique de Caen, David A. Gregory, Norman J. Pullman. proc. 3ra Conferencia Caribeña de Combinatoria y Computación / ed. Charles C. Cadogan. - Departamento de Matemáticas, Universidad de las Indias Occidentales, 1981. - S. 169-173 .
  5. ↑ En el problema del huésped, la posición inicial del ciclo es significativa, por lo que el número de ciclos hamiltonianos y la solución al problema del huésped difieren por un factor de 2n .
  6. ↑ DS Johnson. proc. 5ª Conferencia del Sureste. sobre combinatoria, teoría de grafos y computación, Utilitas Mathematicae. - Winnipeg, 1974. - S. 513-527 .
  7. ↑ M. Kubale. Coloraciones de gráficos. - Sociedad Matemática Americana, 2004. - ISBN 0-8218-3458-4 .
  8. ↑ Fürer. proc. 36º Simposio IEEE. Fundamentos de Ciencias de la Computación (FOCS '95) . - 1995. - S. 414 -421 . - ISBN 0-8186-7183-1 . -doi : 10.1109/ SFCS.1995.492572 .
  9. ↑ Jiri Matousek. Sobre la distorsión requerida para incrustar espacios métricos finitos en espacios normados // Israel Journal of Mathematics. - 1996. - T. 93 , núm. 1 . - S. 333-344 . -doi : 10.1007/ BF02761110 .
  10. ↑ Štefko Miklavic, Primož Poročnik. Circulantes regulares a distancia // European Journal of Combinatorics. - 2003. - T. 24 , núm. 7 . - S. 777-784 . - doi : 10.1016/S0195-6698(03)00117-3 .
  11. ↑ Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri. ¿Se pueden representar los gráficos de visibilidad de forma compacta? // Geometría Discreta y Computacional. - 1994. - T. 12 , núm. 1 . - S. 347-365 . -doi : 10.1007/ BF02574385 .

Enlaces