Hispanopedia WikiEl juego de colocar piedras en grafos es un juego matemático que se juega en un grafo con cero o más piedras en cada uno de sus vértices . El "juego" se compone de una serie de movimientos de colocación de piedras. Un movimiento de colocación de piedras en un grafo consiste en elegir un vértice con al menos dos piedras, quitar dos piedras de él y añadir una a un vértice adyacente (la segunda piedra quitada se descarta del juego). π( G ), el número de colocación de piedras de un grafo G , es el número natural más pequeño n que satisface la siguiente condición:
Dado cualquier vértice objetivo o "raíz" en el grafo y cualquier configuración inicial de n guijarros en el grafo, es posible, después de una serie de movimientos de guijarros posiblemente vacíos, llegar a una nueva configuración en la que el vértice raíz designado tenga uno o más guijarros.
Por ejemplo, en un grafo con 2 vértices y 1 arista que los conecta, el número de pebbling es 2. No importa cómo se coloquen los dos pebblings en los vértices del grafo, siempre es posible llegar al resultado deseado de que el vértice elegido tenga un pebbling; si la configuración inicial es la configuración con un pebbling por vértice, entonces el objetivo se logra trivialmente con cero movimientos de pebbling. Una de las preguntas centrales del pebbling de grafos es el valor de π( G ) para un grafo G dado .
Otros temas relacionados con el pebbling incluyen el pebbling de cobertura, el pebbling óptimo, el pebbling de cobertura de dominación, los límites y umbrales para los números de pebbling, así como los grafos profundos.
Una aplicación de los juegos de guijarros se encuentra en el análisis de seguridad de funciones difíciles de memorizar en criptografía . [ 1 ]
π( G ) — el número de guijarros de un gráfico
El juego de colocar guijarros fue sugerido por primera vez por Lagarias y Saks , como una herramienta para resolver un problema particular en la teoría de números . En 1989, FRK Chung introdujo el concepto en la literatura [ 2 ] y definió el número de colocación de guijarros, π( G ).
El número de guijarros para un grafo completo de n vértices se verifica fácilmente que es n : Si tuviéramos n − 1 guijarros para colocar en el grafo, podríamos colocar un guijarro en cada vértice excepto en el objetivo. Como ningún vértice tiene dos o más guijarros, no es posible realizar movimientos, por lo que es imposible colocar un guijarro en el objetivo. Por lo tanto, el número de guijarros debe ser mayor que n − 1. Dados n guijarros, hay dos casos posibles. Si cada vértice tiene un guijarro, no se requieren movimientos. Si algún vértice está vacío, al menos otro vértice debe tener dos guijarros, y un movimiento de guijarro permite agregar un guijarro a cualquier vértice objetivo en el grafo completo. [ 2 ]
π( G ) para familias de grafos
El número de guijarros se conoce para las siguientes familias de gráficos:
- , dóndees un grafo completo con n vértices. [ 2 ]
- , dóndees un grafo de caminos con n vértices. [ 2 ]
- , dóndees un grafo de rueda con n vértices.
La conjetura de Graham sobre el emplazamiento de guijarros
Chung (1989) atribuyó a Ronald Graham la conjetura de que el número de pebbling de un producto cartesiano de grafos es como máximo igual al producto de los números de pebbling de los factores. [ 3 ] Esto se conoce como la conjetura de pebbling de Graham . Permanece sin resolver, aunque se conocen casos especiales. [ 4 ]
γ( G ) — el número de cobertura de un grafo
Crull et al. introdujeron el concepto de cobertura de guijarros. El número de cobertura de guijarros de un grafo G , γ( G ), es el número mínimo de guijarros necesarios para que, a partir de cualquier disposición inicial de los guijarros, después de una serie de movimientos de cobertura, el grafo quede cubierto: hay al menos un guijarro en cada vértice. [ 5 ] Un resultado llamado teorema de apilamiento encuentra el número de cobertura de guijarros para cualquier grafo. [ 6 ] [ 7 ]
El teorema de apilamiento
Según el teorema de apilamiento, la configuración inicial de guijarros que requiere que se cubra la mayor cantidad de guijarros se produce cuando todos los guijarros se colocan en un solo vértice. Basándonos en esta observación, definimos
para cada vértice v en G , donde d ( u , v ) denota la distancia de u a v . Entonces el número de pebbling de la cubierta es el s ( v ) más grande que resulta.
γ( G ) para familias de grafos
El número de pebbling de la cubierta se conoce para las siguientes familias de gráficos:
- , dóndees un grafo completo con n vértices.
- , dóndees un grafo de caminos con n vértices.
- , dóndees un grafo rueda con n vértices. [ 8 ]
Véase también
Referencias
- ↑ Alwen, Joël; Serbinenko, Vladimir (2014), High Parallel Complexity Graphs and Memory-Hard Functions , archivado del original el 16 de abril de 2024 , consultado el 15 de enero de 2024.
- 1 2 3 4 Chung, Fan RK (1989). "Pebbling en hipercubos". SIAM Journal on Discrete Mathematics . 2 (4): 467– 472. doi : 10.1137/0402041 . MR 1018531 .
- ↑ Véase Chung (1989) , pregunta 3, página 472.
- ↑ Pleanmani, Nopparat (2019). "La conjetura de Graham sobre el apilamiento de guijarros se cumple para el producto de un grafo y un grafo bipartito completo suficientemente grande". Matemáticas Discretas, Algoritmos y Aplicaciones . 11 (6): 1950068, 7. doi : 10.1142/s179383091950068x . MR 4044549. S2CID 204207428 .
- ↑ Crull, Betsy; Cundiff, Tammy; Feltman, Paul; Hurlbert, Glenn H.; Pudwell, Lara; Szaniszlo, Zsuzsanna; Tuza, Zsolt (2005), "The cover pebbling number of graphs" (PDF) , Discrete Mathematics , 296 (1): 15–23 , arXiv : math/0406206 , doi : 10.1016/j.disc.2005.03.009 , MR 2148478 , S2CID 5109099 , archivado (PDF) del original el 17-07-2012 , recuperado el 22-07-2019
- ↑ Vuong, Annalies; Wyckoff, M. Ian (18 de octubre de 2004). "Condiciones para el pebbling de cobertura ponderada de grafos". arXiv : math/0410410 .
- ↑ Sjöstrand, Jonas (2005). " El teorema del pebbling de la cubierta" . Revista electrónica de combinatoria . 12 N22: Nota 22. doi : 10.37236/1989 . MR 2180807. Archivado del original el 14 de febrero de 2012. Consultado el 22 de julio de 2019 .
- ↑ Watson, Nathaniel G.; Yerger, Carl R. (2006). "Números de pebbling de cobertura y límites para ciertas familias de grafos". Boletín del Instituto de Combinatoria y sus Aplicaciones . 48 : 53–62 . arXiv : math/0409321 . MR 2259702 .
Lecturas adicionales
- Chan, Melody ; Godbole, Anant P. (2008). "Límites mejorados para el apilamiento de guijarros". Matemáticas Discretas . 308 (11): 2301– 2306. arXiv : math/0510045 . doi : 10.1016/j.disc.2006.06.032 . MR 2404560. S2CID 5501949 .
- Hurlbert, Glenn H. (1999). "Una revisión del grafo de pebbling" (PDF) . Actas de la Trigésima Conferencia Internacional del Sudeste sobre Combinatoria, Teoría de Grafos y Computación (Boca Ratón, FL, 1999) . Congressus Numerantium. Vol. 139. págs. 41–64 . MR 1744229. Archivado (PDF) del original el 2 de septiembre de 2006. Recuperado el 31 de octubre de 2005 .
- Pachter, Lior ; Snevily, Hunter S.; Voxman, Bill (1995). "Sobre grafos de guijarros" (PDF) . Actas de la Vigésimo Sexta Conferencia Internacional del Sudeste sobre Combinatoria, Teoría de Grafos y Computación (Boca Ratón, FL, 1995) . Congressus Numerantium. Vol. 107. págs. 65–80 . MR 1369255. Archivado del original (PDF) el 25 de noviembre de 2015.
- invariantes de grafos
