En teoría de grafos , una rama de las matemáticas, un grafo corona sobre 2 n vértices es un grafo no dirigido con dos conjuntos de vértices { u 1 , u 2 , …, u n } y { v 1 , v 2 , …, v n } y con una arista de u i a v j siempre que i ≠ j .
El gráfico de corona puede verse como un gráfico bipartito completo del cual se han eliminado los bordes de una correspondencia perfecta , como la doble cubierta bipartita de un gráfico completo , como el producto tensorial K n × K 2 , como el complemento del producto directo cartesiano 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) elementos de un conjunto de n elementos, con un borde entre dos subconjuntos siempre que uno esté contenido en el otro.
El grafo de corona de 6 vértices forma un ciclo , y el grafo de corona de 8 vértices es isomorfo al grafo de un cubo . En el doble seis de Schläfli , una configuración de 12 líneas y 30 puntos en el espacio tridimensional, las doce líneas se intersecan entre sí en el patrón de un grafo de corona de 12 vértices.
El número de aristas en un grafo 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 grafos de corona son simétricos y transitivos en cuanto a la distancia . Archdeacon et al. (2004) describen particiones de las aristas de un grafo de corona en ciclos de igual longitud.
El grafo de corona de 2 n vértices puede estar incrustado en un espacio euclidiano de cuatro dimensiones de tal manera que todos sus bordes tengan una longitud unitaria. Sin embargo, esta incrustación también puede colocar algunos vértices no adyacentes separados por una distancia unitaria. 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 grafo puede requerir dimensiones muy diferentes para ser representado como un grafo de distancia unitaria y como un grafo de distancia unitaria estricta. [2]
El número mínimo de subgrafos bipartitos completos necesarios para cubrir los bordes de un grafo 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 de cena es que los hombres y las mujeres deben alternar posiciones, y que ninguna pareja casada debe sentarse una al lado de la otra. [4] Las disposiciones que satisfacen esta regla, para una fiesta compuesta por n parejas casadas, se pueden describir como los ciclos hamiltonianos de un grafo de corona. Por ejemplo, las disposiciones de vértices que se muestran en la figura se pueden interpretar como diagramas de asientos de este tipo en los que cada esposo y esposa 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 grafo de corona, se conoce en combinatoria como el problema del ménage ; para grafos 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 voraz 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 una coloración voraz utiliza n colores, mientras que el número óptimo de colores es dos. Esta construcción se atribuye a Johnson (1974); los gráficos de corona a veces se denominan gráficos 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 dificultad de aproximación de los problemas de coloración.
Matoušek (1996) utiliza distancias en gráficos de corona como un 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 presentarse como gráficos circulantes regulares en función de la distancia .
Agarwal et al. (1994) describen polígonos que tienen gráficos de corona como sus gráficos de visibilidad ; utilizan este ejemplo para mostrar que representar gráficos de visibilidad como uniones de gráficos bipartitos completos puede no ser siempre eficiente en términos de espacio.
Un gráfico de corona con 2 n vértices, con sus aristas orientadas de un lado de la bipartición al otro, forma el ejemplo estándar de un conjunto parcialmente ordenado con dimensión de orden n .
{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )