Guijarro de gráficos

Juego matemático jugado en un gráfico.

Graph pebbling es un juego matemático que se juega en un gráfico con cero o más guijarros en cada uno de sus vértices . El 'juego' se compone de una serie de movimientos de guijarros. Un movimiento de guijarros en un gráfico consiste en elegir un vértice con al menos dos guijarros, quitarle dos guijarros y agregar uno a un vértice adyacente (el segundo guijarro eliminado se descarta del juego). π( G ), el número de guijarros de un gráfico G , es el número natural más bajo n que satisface la siguiente condición:

Dado cualquier vértice objetivo o 'raíz' en el gráfico y cualquier configuración inicial de n guijarros en el gráfico, es posible, después de una serie posiblemente vacía de movimientos de guijarros, alcanzar una nueva configuración en la que el vértice raíz designado tenga uno o más guijarros.

Por ejemplo, en un gráfico con 2 vértices y 1 arista que los conecta, el número de guijarros es 2. No importa cómo se coloquen los dos guijarros en los vértices del gráfico, siempre es posible llegar al resultado deseado: que el vértice elegido tenga un Guijarro; Si la configuración inicial es la configuración con un guijarro por vértice, entonces el objetivo se logra trivialmente con cero movimientos de guijarros. Una de las cuestiones centrales del graficado es el valor de π( G ) para un gráfico dado G .

Otros temas en pebbling incluyen pebbling de cobertura, pebbling óptimo, pebbling de cobertura de dominación, límites y umbrales para números de pebbling, así como gráficos profundos.

Una aplicación de los juegos de pebbling es el análisis de seguridad de funciones de memoria dura en criptografía . ^[1]

π( G ) — el número de guijarros de un gráfico

El juego del guijarro fue sugerido por primera vez por Lagarias y Saks , como herramienta para resolver un problema particular en teoría de números . En 1989, FRK Chung introdujo el concepto en la literatura ^[2] y definió el número de pebbling, π( G ).

Se puede verificar fácilmente que el número de guijarros para un gráfico completo en n vértices es n : si tuviéramos ( n  − 1) guijarros para colocar en el gráfico, entonces podríamos colocar un guijarro en cada vértice excepto en el objetivo. Como ningún vértice tiene dos o más piedras, no es posible realizar ningún movimiento, por lo que es imposible colocar una piedra en el objetivo. Por 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 gráfico completo. ^[2]

π( G ) para familias de gráficos

El número de guijarros es conocido por las siguientes familias de gráficos:

• ${\displaystyle \pi (K_{n})\,=\,n}$, donde es un gráfico completo en n vértices. ^[2] ${\displaystyle K_{n}}$
• ${\displaystyle \pi (P_{n})\,=\,2^{n-1}}$, donde hay un gráfico de ruta en n vértices. ^[2] ${\displaystyle P_{n}}$
• ${\displaystyle \pi (W_{n})\,=\,n}$, donde hay un gráfico de rueda en n vértices. ${\displaystyle W_{n}}$

La conjetura de Graham

Problema no resuelto en matemáticas :

¿El número de guijarros de un producto cartesiano de gráficos es como máximo el producto del número de guijarros de los gráficos?

(más problemas sin resolver en matemáticas)

Chung (1989) le dio crédito a Ronald Graham por la conjetura de que el número de guijarros de un producto cartesiano de gráficos es como máximo igual al producto de los números de guijarros de los factores del producto. ^[3] Esto ha llegado a conocerse como la conjetura del guijarro de Graham . A fecha de 2019 ^[actualizar], sigue sin resolverse, aunque se conocen casos especiales. ^[4]

γ( G ) — el número de guijarros de portada de un gráfico

Crull et al. introdujo el concepto de guijarros de cobertura. γ( G ), el número de guijarros de cobertura de un gráfico 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 guijarros, el gráfico quede cubierto: hay al menos un guijarro en cada vértice . ^[5] Un resultado llamado teorema de apilamiento encuentra el número de guijarros de cubierta para cualquier gráfico. ^{[6] [7]}

El teorema de apilamiento

Según el teorema de apilamiento, la configuración inicial de guijarros que requiere que se resuelva la mayor cantidad de guijarros ocurre cuando todos los guijarros se colocan en un solo vértice. Con base en esta observación, defina

${\displaystyle s(v)=\sum _{u\in V(G)}2^{d(u,v)}}$

para cada vértice v en G , donde d ( u , v ) denota la distancia de u a v . Entonces el número de guijarros de la cubierta es el mayor s ( v ) que resulte.

γ( G ) para familias de gráficos

El número de guijarros de portada se conoce para las siguientes familias de gráficos:

• ${\displaystyle \gamma (K_{n})\,=\,2n-1}$, donde es un gráfico completo en n vértices. ${\displaystyle K_{n}}$
• ${\displaystyle \gamma (P_{n})\,=\,2^{n}-1}$, donde hay un camino en n vértices. ${\displaystyle P_{n}}$
• ${\displaystyle \gamma (W_{n})\,=\,4n-9}$, donde hay un gráfico de rueda en n vértices. ^[8] ${\displaystyle W_{n}}$

Ver también

• juego de guijarros
• prueba de espacio

Referencias

1. Alwen, Joel; Serbinenko, Vladimir (2014), Gráficos de alta complejidad paralela y funciones de memoria dura , consultado el 15 de enero de 2024
2. Chung, Fan RK (1989). "Guijarros en hipercubos". Revista SIAM de Matemática Discreta . 2 (4): 467–472. doi :10.1137/0402041. SEÑOR  1018531.
3. Véase Chung (1989), pregunta 3, página 472.
4. Pleanmani, Nopparat (2019). "La conjetura de Graham es válida para el producto de un gráfico y un gráfico bipartito completo suficientemente grande". Matemáticas discretas, algoritmos y aplicaciones . 11 (6): 1950068, 7. doi :10.1142/s179383091950068x. SEÑOR  4044549. S2CID  204207428.
5. Crull, Betsy; Cundiff, Tammy; Feltman, Pablo; Hurlbert, Glenn H.; Pudwell, Lara; Szaniszlo, Zsuzsanna; Tuza, Zsolt (2005), "El número de gráficos de la portada" (PDF) , Matemáticas discretas , 296 (1): 15–23, arXiv : math/0406206 , doi :10.1016/j.disc.2005.03.009, MR  2148478, S2CID  5109099
6. Vuong, Anales; Wyckoff, M. Ian (18 de octubre de 2004). "Condiciones para el guijarro de gráficos con cubierta ponderada". arXiv : matemáticas/0410410 .
7. Sjöstrand, Jonas (2005). "El teorema del guijarro de la cubierta". Revista Electrónica de Combinatoria . 12 : Nota 22. doi : 10.37236/1989 . SEÑOR  2180807.
8. Watson, Nathaniel G.; Yerger, Carl R. (2006). "Cubra números y límites de ciertas familias de gráficos". Boletín del Instituto de Combinatoria y sus Aplicaciones . 48 : 53–62. arXiv : matemáticas/0409321 . SEÑOR  2259702.

Otras lecturas

• Chan, Melodía ; Godbole, Anant P. (2008). "Límites de guijarros mejorados". Matemáticas discretas . 308 (11): 2301–2306. arXiv : matemáticas/0510045 . doi :10.1016/j.disc.2006.06.032. SEÑOR  2404560. S2CID  5501949.
• Hurlbert, Glenn H. (1999). "Un estudio sobre el guijarro de gráficos" (PDF) . Actas de la trigésima Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1999) . Congreso Numerantium. vol. 139, págs. 41–64. SEÑOR  1744229.
• Pachter, Lior ; Snevily, Hunter S.; Voxman, Bill (1995). "Sobre gráficos de guijarros" (PDF) . Actas de la Vigésima Sexta Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1995) . Congreso Numerantium. vol. 107, págs. 65–80. SEÑOR  1369255. Archivado desde el original (PDF) el 25 de noviembre de 2015.