En teoría de grafos , una rama de las matemáticas, un gráfico de corona en 2 n vértices es un gráfico no dirigido con dos conjuntos de vértices { u 1 , u 2 ,…, u n } y { v 1 , v 2 ,…, v n } y con una ventaja de u i a v j siempre que i ≠ j .
El gráfico de la corona puede verse como un gráfico bipartito completo del que se han eliminado los bordes de una coincidencia perfecta , como la doble cubierta bipartita de un gráfico completo , como el producto tensorial K n × K 2 , como el complemento de la directa cartesiana. producto de K n y K 2 , o como un gráfico de Kneser bipartito H n ,1 que representa los subconjuntos de 1 elemento y ( n – 1) de un conjunto de n elementos, con un borde entre dos subconjuntos siempre que uno esté contenido en el otro.
La gráfica de corona de 6 vértices forma un ciclo , y la gráfica de corona de 8 vértices es isomorfa a la gráfica de un cubo . En el doble seis de Schläfli , una configuración de 12 líneas y 30 puntos en un espacio tridimensional, las doce líneas se cruzan entre sí en el patrón de un gráfico de corona de 12 vértices.
El número de aristas en un gráfico de corona es el número pronico n ( n – 1) . Su número acromático es n : se puede encontrar una coloración completa eligiendo cada par { u i , v i } como una de las clases de color. [1] Los gráficos de corona son simétricos y transitivos en distancia . Archidiácono et al. (2004) describen particiones de los bordes de un gráfico de corona en ciclos de igual longitud.
El gráfico de corona de 2 n -vértices se puede incrustar en un espacio euclidiano de cuatro dimensiones de tal manera que todas sus aristas tengan una unidad de longitud. Sin embargo, esta incrustación también puede colocar algunos vértices no adyacentes a una unidad de distancia. Una incrustación en la que los bordes están a una distancia unitaria y los no bordes no están a una distancia unitaria requiere al menos n – 2 dimensiones. Este ejemplo muestra que un gráfico puede requerir dimensiones muy diferentes para representarse como un gráfico de distancia unitaria y como un gráfico de distancia unitaria estricto. [2]
El número mínimo de subgrafos bipartitos completos necesarios para cubrir los bordes de un gráfico de corona (su dimensión bipartita , o el tamaño de una cubierta biclique mínima) es
la función inversa del coeficiente binomial central . [3]
El gráfico complementario de un gráfico de corona de 2 n- vértices es el producto cartesiano de gráficos completos K 2 ▢ K n , o equivalentemente el gráfico de torre de 2 × n .
En etiqueta , una regla tradicional para organizar a los invitados en una mesa es que hombres y mujeres deben alternar posiciones y que ningún matrimonio debe sentarse uno al lado del otro. [4] Los arreglos que satisfacen esta regla, para una parte formada por n parejas casadas, pueden describirse como los ciclos hamiltonianos de un gráfico de corona. Por ejemplo, la disposición de los vértices que se muestra en la figura puede interpretarse como planos de asientos de este tipo en los que cada marido y mujer se sientan lo más separados posible. El problema de contar el número de posibles disposiciones de asientos, o casi equivalentemente [5] el número de ciclos hamiltonianos en un gráfico de corona, se conoce en combinatoria como problema del ménage ; para gráficos de corona con 6, 8, 10, ... vértices, el número de ciclos hamiltonianos (orientados) es
Los gráficos de corona se pueden utilizar para mostrar que los algoritmos de coloración codiciosa se comportan mal en el peor de los casos: si los vértices de un gráfico de corona se presentan al algoritmo en el orden u 0 , v 0 , u 1 , v 1 , etc., entonces un La coloración codiciosa utiliza n colores, mientras que el número óptimo de colores es dos. Esta construcción se atribuye a Johnson (1974); Las gráficas de corona a veces se denominan gráficas de Johnson con notación J n . [6] Fürer (1995) utiliza gráficos de corona como parte de una construcción que muestra la dureza de la aproximación de los problemas de coloración.
Matoušek (1996) utiliza distancias en gráficos de corona como ejemplo de un espacio métrico que es difícil de integrar en un espacio vectorial normado .
Como muestran Miklavič y Potočnik (2003), los gráficos de corona son uno de los pocos tipos diferentes de gráficos que pueden ocurrir como gráficos circulantes de distancia regular .
Agarwal et al. (1994) describen polígonos que tienen gráficos de corona como gráficos de visibilidad ; Usan este ejemplo para mostrar que representar gráficos de visibilidad como uniones de gráficos bipartitos completos puede no siempre ser eficiente en términos de espacio.
Un gráfico de corona con 2 n vértices, con sus bordes orientados de un lado a otro de la bipartición, forma el ejemplo estándar de un conjunto parcialmente ordenado con dimensión de orden n .
{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace )