Gráfico de guijarros

Juego matemático jugado en un gráfico.

El juego de pebbling de grafos es un juego matemático que se juega en un grafo con cero o más guijarros en cada uno de sus vértices . El 'juego' se compone de una serie de movimientos de pebbling. Un movimiento de pebbling en un grafo 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 quitado se descarta del juego). π( G ), el número de pebbling de un grafo 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 de movimientos de guijarros posiblemente vacíos, alcanzar 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 pebbles en los vértices del grafo, siempre es posible llegar al resultado deseado de que el vértice elegido tenga un pebble; si la configuración inicial es la configuración con un pebble 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, 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 exigente en criptografía . ^[1]

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

El juego de pebbling 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 pebbling, π( G ).

El número de guijarros para un grafo completo en n vértices se verifica fácilmente como n : Si tuviéramos n  − 1 guijarros para poner en el grafo, entonces podríamos poner un guijarro en cada vértice excepto 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 sobre él, y un movimiento de guijarros permite agregar un guijarro a cualquier vértice objetivo en el grafo completo. ^[2]

π(GRAMO) para familias de gráficos

El número de guijarros se conoce para 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 es un gráfico de trayectoria en n vértices. ^[2] ${\displaystyle P_{n}}$
• ${\displaystyle \pi (W_{n})=n}$, donde es un gráfico de rueda en n vértices. ${\displaystyle W_{n}}$

La conjetura de los guijarros de Graham

Problema sin resolver en matemáticas :

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

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

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 . Sigue sin resolverse, aunque se conocen casos especiales. ^[4]

y(GRAMO) — el número de guijarros de la cubierta de un gráfico

Crull et al. introdujeron el concepto de "pebbling de cobertura". El número de pebbling de cobertura de un grafo G , γ( G ), es el número mínimo de pebbles necesarios para que, a partir de cualquier disposición inicial de los pebbles, después de una serie de movimientos de pebbling, el grafo esté cubierto: hay al menos un pebbling en cada vértice. ^[5] Un resultado llamado teorema de apilamiento encuentra el número de pebbling de cobertura 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 cubran la mayor cantidad de guijarros se resuelve 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 s ( v ) más grande que resulta.

y(GRAMO) para familias de gráficos

El número de guijarros de la cubierta 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 es un gráfico de ruta en n vértices. ${\displaystyle P_{n}}$
• ${\displaystyle \gamma (W_{n})=4n-9}$, donde es un gráfico de rueda en n vértices. ^[8] ${\displaystyle W_{n}}$

Véase también

• Juego de guijarros
• Prueba de espacio

Referencias

1. Alwen, Joël; Serbinenko, Vladimir (2014), Gráficos de alta complejidad paralela y funciones de memoria difícil , consultado el 15 de enero de 2024
2. Chung, Fan RK (1989). "Pebbling en hipercubos". Revista SIAM de Matemáticas Discretas . 2 (4): 467–472. doi :10.1137/0402041. MR  1018531.
3. Véase Chung (1989), pregunta 3, página 472.
4. Pleanmani, Nopparat (2019). "La conjetura de Graham sobre el empedrado es válida 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.
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, Annalies; Wyckoff, M. Ian (18 de octubre de 2004). "Condiciones para el pebbling ponderado de gráficos". arXiv : math/0410410 .
7. Sjöstrand, Jonas (2005). "El teorema de la formación de guijarros en la cubierta". Revista electrónica de combinatoria . 12 : Nota 22. doi : 10.37236/1989 . MR  2180807.
8. Watson, Nathaniel G.; Yerger, Carl R. (2006). "Números de cubierta 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.

Lectura adicional

• Chan, Melody ; Godbole, Anant P. (2008). "Límites de pebbling mejorados". 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). "Un estudio de la construcción de grafos" (PDF) . Actas de la 30.ª Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1999) . Congressus Numerantium. Vol. 139. págs. 41–64. MR  1744229.
• Pachter, Lior ; Snevily, Hunter S.; Voxman, Bill (1995). "Sobre los grafos en forma de guijarros" (PDF) . Actas de la 26.ª Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1995) . Congressus Numerantium. Vol. 107. págs. 65–80. MR  1369255. Archivado desde el original (PDF) el 25 de noviembre de 2015.