Gráfico de panqueques

En el campo matemático de la teoría de grafos , el grafo panqueque P _n o grafo n -panqueque es un grafo cuyos vértices son las permutaciones de n símbolos de 1 a n y sus aristas están dadas entre permutaciones transitivas por inversiones de prefijo.

La clasificación de panqueques es el término coloquial para el problema matemático de clasificar una pila desordenada de panqueques en orden de tamaño cuando se puede insertar una espátula en cualquier punto de la pila y usarla para voltear todos los panqueques que están encima. Un número de panqueques es el número mínimo de volteos necesarios para una cantidad dada de panqueques. Obtener el número de panqueques es equivalente al problema de obtener el diámetro del gráfico de panqueques. ^[1]

El grafo de panqueque de dimensión n , P _n , es un grafo regular con vértices. Su grado es n  − 1, por lo tanto, de acuerdo con el lema del apretón de manos , tiene aristas. P _n se puede construir recursivamente a partir de n copias de P _{n −1} , asignando un elemento diferente del conjunto {1, 2, …, n } como sufijo a cada copia. ${\displaystyle n!}$ ${\displaystyle {\dfrac {1}{2}}~n!\left(n-1\right)}$

Resultados

P _n ( n ≥ 4) está superconectado e hiperconectado . ^[2]

Su circunferencia es ^[3]

${\displaystyle g(P_{n})=6,{\text{ if }}n>2.}$

El género γ( P _n ) de P _n está limitado inferior y superiormente por: ^{[4] [5]}

${\displaystyle n!\left({\frac {n-4}{6}}\right)+1\leq \gamma (P_{n})\leq n!\left({\frac {3n-10}{12}}\right)+1.}$

Propiedades cromáticas

Existen algunas propiedades de coloración de gráficos conocidas de los gráficos tipo panqueque.

Un gráfico de panqueque P _n ( n ≥ 3) tiene un número cromático total y un índice cromático . ^[6] ${\displaystyle \chi _{t}(P_{n})=n}$ ${\displaystyle \chi _{e}(P_{n})=n-1}$

Existen algoritmos efectivos para la coloración adecuada (n−1) y la coloración total n de gráficos de panqueques. ^[6]

Para el número cromático se conocen los siguientes límites: ${\displaystyle \chi (P_{n})}$

Si , entonces ${\displaystyle 4\leq n\leq 8}$

${\displaystyle \chi (P_{n})\leq {\begin{cases}n-k,&{\text{if }}n\equiv k{\pmod {4}},k=1,3;\\n-2,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}}$

Si , entonces ${\displaystyle 9\leq n\leq 16}$

${\displaystyle \chi (P_{n})\leq {\begin{cases}n-(k+2),&{\text{if }}n\equiv k{\pmod {4}},k=1,3;\\n-4,&{\text{if }}n\equiv k{\pmod {4}},k=0,2;\end{cases}}}$

Si , entonces ${\displaystyle n\geq 17}$

${\displaystyle \chi (P_{n})\leq {\begin{cases}n-(k+4),&{\text{if }}n\equiv k{\pmod {4}},k=1,2,3;\\n-8,&{\text{if }}n\equiv k{\pmod {4}},k=0.\end{cases}}}$

En la siguiente tabla se analizan valores de números cromáticos específicos para algunos n pequeños .

Enumeración de ciclos

En un gráfico de panqueque P _n ( n ≥ 3) siempre hay al menos un ciclo de longitud ℓ , cuando (pero no hay ciclos de longitud 3, 4 o 5). ^[7] Esto implica que el gráfico es hamiltoniano y que dos vértices cualesquiera pueden unirse mediante un camino hamiltoniano. ${\displaystyle 6\leq \ell \leq n!}$

Acerca de los 6-ciclos del gráfico panqueque P _n ( n ≥ 4): cada vértice pertenece exactamente a un 6-ciclo. El gráfico contiene 6-ciclos independientes (disjuntos con respecto a los vértices). ^[8] ${\displaystyle {\frac {n!}{6}}}$

Acerca de los 7-ciclos del gráfico panqueque P _n ( n ≥ 4): cada vértice pertenece a 7-ciclos. El gráfico contiene diferentes 7-ciclos. ^[9] ${\displaystyle 7\cdot (n-3)}$ ${\displaystyle n!\cdot (n-3)}$

Acerca de los 8 ciclos del gráfico de panqueque P _n ( n ≥ 4): el gráfico contiene diferentes 8 ciclos; un conjunto máximo de 8 ciclos independientes contiene de ellos. ^[8] ${\displaystyle {\frac {n!(n^{3}+12n^{2}-103n+176)}{16}}}$ ${\displaystyle {\frac {n!}{8}}}$

Diámetro

El problema de clasificación de panqueques (obtención del número de panqueques) y la obtención del diámetro del gráfico de panqueques son equivalentes. Una de las principales dificultades para resolver este problema es la complicada estructura cíclica del gráfico de panqueques.

Se ha demostrado que el número de panqueques, que es el número mínimo de vueltas necesarias para ordenar cualquier pila de n panqueques, se encuentra entre ⁠15/14⁠ n y ⁠18/11n (aproximadamente 1,07 n y 1,64 n ), pero el valor exacto sigue siendo un problema abierto. ^[10]

En 1979, Bill Gates y Christos Papadimitriou ^[11] dieron un límite superior de ⁠5/3⁠ n . Esto se mejoró, treinta años después, para ⁠18/11n por un equipo de investigadores de la Universidad de Texas en Dallas , dirigido por el profesor fundador Hal Sudborough ^[12] (Chitturi et al., 2009 ^[13] ).

En 2011, Laurent Bulteau, Guillaume Fertin e Irena Rusu ^[14] demostraron que el problema de encontrar la secuencia más corta de giros para una pila dada de panqueques es NP-difícil, respondiendo así una pregunta que había estado abierta durante más de tres décadas.

Gráfico de panqueques quemados

En una variación llamada el problema del panqueque quemado , se quema la parte inferior de cada panqueque de la pila y la clasificación debe completarse con el lado quemado de cada panqueque hacia abajo. Es una permutación con signo y si un panqueque i está "quemado hacia arriba", se coloca un elemento negativo i` en lugar de i en la permutación. El gráfico del panqueque quemado es la representación gráfica de este problema.

Un gráfico de panqueque quemado es regular , su orden es , su grado es . ${\displaystyle P'_{n}}$ ${\displaystyle 2^{n}\cdot n!}$ ${\displaystyle n}$

Para su variante, David S. Cohen (mejor conocido por su seudónimo " David X. Cohen ") y Manuel Blum demostraron en 1995 que (cuando el límite superior solo es cierto si ). ^[15] ${\displaystyle 3n/2\leq P'_{n}\leq 2n-2}$ ${\displaystyle n>9}$

La circunferencia de un gráfico de panqueque quemado es: ^[3]

${\displaystyle g(P_{n})=8{\text{, if }}n>2.}$

Otras clases de gráficos de panqueques

Tanto en el problema original de clasificación de panqueques como en el problema de los panqueques quemados, la inversión de prefijo era la operación que conectaba dos permutaciones. Si permitimos inversiones sin prefijo (como si estuviéramos dando vueltas con dos espátulas en lugar de una), entonces se pueden definir cuatro clases de gráficos de panqueques. Cada gráfico de panqueque se integra en todos los gráficos de panqueques de orden superior de la misma familia. ^[3]

Aplicaciones

Dado que los gráficos de panqueque tienen muchas propiedades interesantes, como estructuras simétricas y recursivas (son gráficos de Cayley , por lo tanto, son transitivos de vértice ), grado y diámetro sublogarítmicos, y son relativamente dispersos (en comparación con, por ejemplo, los hipercubos ), se les presta mucha atención como modelo de redes de interconexión para computadoras paralelas. ^{[4] [16] [17] [18]} Cuando consideramos los gráficos de panqueque como el modelo de las redes de interconexión, el diámetro del gráfico es una medida que representa el retraso de la comunicación. ^{[19] [20]}

La técnica de dar vuelta los panqueques también tiene aplicaciones biológicas en el campo de los análisis genéticos. En un tipo de mutaciones a gran escala, se invierte un segmento grande del genoma, lo que es análogo al problema del panqueque quemado.

Referencias

1. Asai, Shogo; Kounoike, Yuusuke; Shinano, Yuji; Kaneko, Keiichi (2006). "Cálculo del diámetro de un grafo de 17 panqueques utilizando un clúster de PC". En Nagel, Wolfgang E.; Walter, Wolfgang V.; Lehner, Wolfgang (eds.). Euro-Par 2006, Procesamiento paralelo, 12.ª Conferencia internacional Euro-Par, Dresde, Alemania, 28 de agosto – 1 de septiembre de 2006, Actas . Apuntes de clase en informática. Vol. 4128. Springer. págs. 1114–1124. doi :10.1007/11823285_117. ISBN . 978-3-540-37783-2.
2. Deng, Yun-Ping; Xiao-Dong, Zhang (31 de marzo de 2012). "Grupos de automorfismo de los grafos de panqueque". Cartas de procesamiento de información . 112 (7): 264–266. arXiv : 1201.0452 . doi :10.1016/j.ipl.2011.12.010. S2CID  38229793.
3. Compeau, Phillip EC (6 de septiembre de 2011). "Circunferencia de gráficos de panqueque". Matemáticas Aplicadas Discretas . 159 (15): 1641–1645. doi : 10.1016/j.dam.2011.06.013 .
4. Nguyen, Quan; Bettayeb, Said (5 de noviembre de 2009). "Sobre el género de la red Pancake" (PDF) . The International Arab Journal of Information Technology . 8 (3): 289–292.
5. Blanco, Saúl; Buehrle, Charles (20 de junio de 2023). "Límites en el género para incrustaciones de 2 celdas de grafos de inversión de prefijo". arXiv : 2306.11295 [math.CO].
6. Konstantinova, Elena (1 de agosto de 2017). "Propiedades cromáticas de los gráficos de panqueque". Discussiones Mathematicae Graph Theory . 37 (3): 777–787. doi : 10.7151/dmgt.1978 .
7. Sheu, Jyh-Jian; Tan, Jimmy JM (2006). "Incorporación de ciclos en redes de interconexión de panqueques" (PDF) . 23.° Taller sobre Matemática Combinatoria y Teoría de la Computación .
8. Konstantinova, EV; Medvedev, AN (26 de abril de 2013). "Ciclos pequeños en el gráfico de panqueque". Ars Mathematica Contemporanea . 7 : 237–246. doi : 10.26493/1855-3974.214.0e8 .
9. Konstantinova, EV; Medvedev, AN (1 de abril de 2010). "Ciclos de longitud siete en el gráfico de panqueque". Discretn. Anal. Issled. Oper . 17 (5): 46–55. doi : 10.1016/j.tcs.2008.04.045 .
10. Fertin, G. y Labarre, A. y Rusu, I. y Tannier, E. y Vialette, S. (2009). Combinatoria de reordenamientos del genoma . La prensa del MIT. ISBN 9780262062824.{{cite book}}: CS1 maint: multiple names: authors list (link)
11. Gates, W. ; Papadimitriou, C. (1979). "Límites para la ordenación por inversión de prefijo". Matemáticas discretas . 27 : 47–57. doi : 10.1016/0012-365X(79)90068-2 .
12. "Team Beats Young Bill Gates With Improved Answer to So-Called Pancake Problem in Mathematics" (Un equipo supera al joven Bill Gates con una respuesta mejorada al llamado problema de los panqueques en matemáticas). Centro de noticias de la Universidad de Texas en Dallas. 17 de septiembre de 2008. Archivado desde el original el 14 de febrero de 2012. Consultado el 10 de noviembre de 2008. Un equipo de estudiantes de informática de la UT Dallas y su asesor académico han mejorado una solución de larga data para un enigma matemático conocido como el problema de los panqueques. La mejor solución anterior, que se mantuvo durante casi 30 años, fue ideada por Bill Gates y uno de sus instructores de Harvard, Christos Papadimitriou, varios años antes de que se estableciera Microsoft.
13. Chitturi, B.; Fahle, W.; Meng, Z.; Morales, L.; Shields, CO; Sudborough, IH; Voit, W. (31 de agosto de 2009). "Un límite superior de (18/11)n para la ordenación por inversiones de prefijo". Ciencias de la Computación Teórica . Gráficos, Juegos y Computación: Dedicado al Profesor Burkhard Monien con motivo de su 65º Cumpleaños. 410 (36): 3372–3390. doi : 10.1016/j.tcs.2008.04.045 .
14. Bulteau, Laurent; Fertin, Guillaume; Rusu, Irena (2015). "Dar la vuelta a los panqueques es difícil". Revista de Ciencias de la Computación y de Sistemas . 81 (8): 1556–1574. arXiv : 1111.0434 . doi :10.1016/j.jcss.2015.02.003.
15. David S. Cohen, Manuel Blum: Sobre el problema de clasificar panqueques quemados. En: Discrete Applied Mathematics. 61, Nr. 2, 1995, págs. 105–120. DOI:10.1016/0166-218X(94)00009-3.
16. Akl, SG; Qiu, K.; Stojmenović, I. (1993). "Algoritmos fundamentales para las redes de interconexión en estrella y panqueque con aplicaciones a la geometría computacional". Redes . 23 (4): 215–225. CiteSeerX 10.1.1.363.4949 . doi :10.1002/net.3230230403. 
17. Bass, DW; Sudborough, IH (marzo de 2003). "Problemas de panqueques con inversiones de prefijo restringidas y algunas redes Cayley correspondientes". Journal of Parallel and Distributed Computing . 63 (3): 327–336. CiteSeerX 10.1.1.27.7009 . doi :10.1016/S0743-7315(03)00033-9. 
18. Berthomé, P.; Ferreira, A.; Perennes, S. (diciembre de 1996). "Difusión óptima de información en redes en estrella y en panqueque". IEEE Transactions on Parallel and Distributed Systems . 7 (12): 1292–1300. CiteSeerX 10.1.1.44.6681 . doi :10.1109/71.553290. 
19. Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introducción a la computación paralela: diseño y análisis de algoritmos. Benjamin/Cummings (1994)
20. Quinn, MJ: Computación paralela: teoría y práctica, segunda edición. McGraw Hill (1994)