En la teoría de grafos , una rama de las matemáticas, un grafo de corona en 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 .
Gráfico de corona | |
---|---|
Vértices | 2 n |
Bordes | n ( n - 1) |
Radio | |
Diámetro | |
Circunferencia | |
Número cromático | |
Propiedades | Transitivo a distancia |
Notación | |
Tabla de gráficos y parámetros |
El gráfico de corona se puede ver 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 del directo cartesiano. 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) elemento de un conjunto de n elementos, con una ventaja entre dos subconjuntos siempre que uno esté contenido en el otro.
Ejemplos de
El gráfico de corona de 6 vértices forma un ciclo y el gráfico de corona de 8 vértices es isomorfo al gráfico 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 en el patrón de un gráfico de corona de 12 vértices.
Propiedades
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 un color completo eligiendo cada par { u i , v i } como una de las clases de colores. [1] Los gráficos de coronas son simétricos y transitivos a la distancia . Archdeacon 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 el espacio euclidiano de cuatro dimensiones de tal manera que todos sus bordes tengan una unidad de longitud. Sin embargo, esta incrustación también puede colocar algunos vértices no adyacentes separados por 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 ser representado como un gráfico de unidad de distancia y como un gráfico de unidad de distancia 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 biclicua mínima) es
la función inversa del coeficiente binomial central . [3]
El gráfico de complemento de un gráfico de corona de 2 n -vértices es el producto cartesiano de los gráficos completos K 2 K n , o equivalentemente el gráfico de torre 2 × n .
Aplicaciones
En la etiqueta , una regla tradicional para organizar invitados en una mesa para cenar es que hombres y mujeres deben alternar posiciones, y que ninguna pareja casada debe sentarse uno al lado del otro. [4] Los arreglos que satisfacen esta regla, para una fiesta que consta de 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 se puede interpretar como gráficos de asientos de este tipo en los que cada esposo y esposa están sentados lo más separados posible. El problema de contar el número de posibles arreglos de asientos, o casi equivalentemente [5] el número de ciclos hamiltonianos en un gráfico de corona, se conoce en combinatoria como el 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 codiciosos 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 coronas como parte de una construcción que muestra la dureza de aproximación de los problemas de coloración.
Matoušek (1996) usa distancias en gráficos de coronas como un ejemplo de un espacio métrico que es difícil de incrustar en un espacio vectorial normalizado .
Como muestran Miklavič y Potočnik (2003) , los gráficos de coronas son uno de un pequeño número de diferentes tipos de gráficos que pueden aparecer como gráficos circulantes de distancia regular .
Agarwal y col. (1994) describen polígonos que tienen gráficos de coronas como gráficos de visibilidad ; utilizan este ejemplo para mostrar que la representación de gráficos de visibilidad como uniones de gráficos bipartitos completos no siempre es eficiente en términos de espacio.
Un gráfico de corona con 2 n vértices, con sus bordes orientados 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 .
Notas
- ^ Chaudhary y Vishwanathan (2001) .
- ^ Erdős y Simonovits (1980) .
- ↑ de Caen, Gregory y Pullman (1981) .
- ^ Fox, Sue (2011), Etiqueta para tontos (2ª ed.), John Wiley & Sons, p. 244, ISBN 9781118051375
- ^ En el problema del ménage, la posición inicial del ciclo se considera significativa, por lo que el número de ciclos hamiltonianos y la solución al problema del ménage difieren en un factor de 2 n .
- ^ Kubale (2004) .
Referencias
- Agarwal, Pankaj K .; Alon, Noga ; Aronov, Boris ; Suri, Subhash (1994), "¿Pueden representarse los gráficos de visibilidad de forma compacta?", Geometría discreta y computacional , 12 (1): 347–365, doi : 10.1007 / BF02574385 , MR 1298916.
- Archidiácono, D .; Debowsky, M .; Dinitz, J .; Gavlas, H. (2004), "Sistemas de ciclo en el gráfico bipartito completo menos un factor único", Matemáticas discretas , 284 (1–3): 37–43, doi : 10.1016 / j.disc.2003.11.021 , MR 2071894.
- Chaudhary, Amitabh; Vishwanathan, Sundar (2001), "Algoritmos de aproximación para el número acromático", Journal of Algorithms , 41 (2): 404–416, CiteSeerX 10.1.1.1.5562 , doi : 10.1006 / jagm.2001.1192 , MR 1869259.
- de Caen, Dominique ; Gregory, David A .; Pullman, Norman J. (1981), "El rango booleano de las matrices cero-uno", en Cadogan, Charles C. (ed.), Proc. Tercera Conferencia del Caribe sobre Combinatoria y Computación , Departamento de Matemáticas, Universidad de las Indias Occidentales, págs. 169-173, MR 0657202.
- Erdős, Paul ; Simonovits, Miklós (1980), "Sobre el número cromático de gráficos geométricos" (PDF) , Ars Combinatoria , 9 : 229–246, MR 0582295.
- Fürer, Martin (1995), "Resultados de dureza mejorados para la aproximación del número cromático", Proc. 36th IEEE Symp. Fundamentos de la informática (FOCS '95) , págs. 414–421, doi : 10.1109 / SFCS.1995.492572 , ISBN 978-0-8186-7183-8.
- Johnson, DS (1974), "Comportamiento en el peor de los casos de algoritmos de coloración de gráficos", Proc. 5ta Conf. Sureste sobre combinatoria, teoría de grafos y computación, Utilitas Mathematicae , Winnipeg, págs. 513–527, MR 0389644
- Kubale, M. (2004), Coloración de gráficos , American Mathematical Society, ISBN 978-0-8218-3458-9, MR 2074481
- Matoušek, Jiří (1996), "Sobre la distorsión requerida para incrustar espacios métricos finitos en espacios normados", Israel Journal of Mathematics , 93 (1): 333–344, doi : 10.1007 / BF02761110 , MR 1380650.
- Miklavič, Štefko; Potočnik, Primož (2003), "Circulantes regulares a distancia", European Journal of Combinatorics , 24 (7): 777–784, doi : 10.1016 / S0195-6698 (03) 00117-3 , MR 2009391.
enlaces externos
- Weisstein, Eric W. "Gráfico de la corona" . MathWorld .