Download G - California State University Channel Islands

Cindy Wyels
Departmento de Matemáticas y Física
California State University, Channel Islands
Distribución de empedrados: la distribución de
piedritas en los vértices de una gráfica
Paso de empedrados:
de un vértice con al
menos dos piedritas, quita
dos piedritas de este
vértice y pone una
piedrita en un
vértice adyacente.
2
1
1
Otro ejemplo:
4
2
2
1
¿Podemos mover una piedrita?
1
1
1
¿A cuales vértices podemos mover
una piedrita?
3
Quisiera mover una piedrita a cualquier vértice.
• ¿Cuantas piedritas necesito dar a la
distributadora si es una amiga inteligente?
• ¿Cuantas piedritas
necesito dar al
distributador si es un
enemigo ingénioso?
Digamos que una distribución es soluble cuando
podemos mover una piedrita a cualquier vértice.
• ¿Cuantas piedritas necesito dar al distributador
si es un enemigo ingénioso?
• ¿Cuantas piedritas se necesita para garantizar
que todas las distribuciones sean solubles?
• ¿Cuantas piedritas necesito dar a la
distributadora si es una amiga inteligente?
• ¿Cuantos piedritas se necesita para tener al
menos una distribución soluble?
Pregunta: ¿podemos “empedrador”
cualquier vértice?
(¿Es la distribución soluble?)
Sí.
2
3
1
3+1
3
2
?
1
• ¿Necesitamos todas estas piedritas?
• ¿Son todas las distribuciones con 9 piedritas
solubles?
1
21
1
2
3
11
1
1
3
1
1
1
Sea G una gráfica.
El número de empedrados de G, f(G), es
el número más pequeno para que toda
distribución de f(G) piedritas en los
vértices de G sea soluble. (enemigo)
El número óptimo de empedrados de G,
fopt(G), es el número mínimo de piedritas
para que exista una distribución soluble de
fopt(G) piedritas en G. (amiga)
Porque hay una distribución insoluble con 9
piedritas en la gráfica de Petersen, ya sabemos
que su número empedrado es más de 9.
1
1
1
1
1
1
1
1
1
Porque hay una distribución soluble con 8 piedritas en
la gráfica Peterson, ya sabemos que su número óptimal
de empedrados es 8 ó menos.
2
2
3
1
El Número Empedrado de un Camino
Pn es el camino (“path”) de n+1 vértices.
8
1
24
42
21
1
¿Que es el número t, el más pequeno para
que toda distribución de t piedritas en los
vértices de Pn sea soluble?
f(P4) = 16
f(Pn) =
n
2
Límites para Números de Empedrados
Sea G alguna gráfica en n vértices.
Sabemos: n ≤ f(G).
El diámetro de una gráfica, d, es el largo
del camino más grande en la gráfica.
32
Tenemos 2d ≤ f(G).
Límites para Números de Empedrados
Sea G alguna gráfica con n vértices, y
supongamos que G tiene diámetro d.
Si pongo al menos 2d piedritas en algun
vértice, o si pongo al menos 1 piedrita en
cado vértice, entonces la distribución tiene
que ser soluble.
max{n,2d} ≤ f(G) ≤ (2d-1)(n-1)+1.
Empedrados y Gráficas Completas
max{n,2d} ≤ f(G) ≤ (2d-1)(n-1)+1
d =1 nos da
n ≤ f(Kn) ≤ n
esto es f(Kn) = n
K5
max{n,2d} ≤ f(G) ≤ (2d-1)(n-1)+1
d=2
n = 10
10 ≤ f(Pete) ≤ 28.
Ciclos
C5
f(C2k+1) = 2[2k+1/3]+1
C6
f(C2k) = 2k
Aproximadamente, f(Cn) ~ 2n/2.
Gráficas Telerañas Modificadas

• Una gráfica teleraña modificada,
n,t , es
una gráfica teleraña con un vértice adicional al
centro.
 3,3
 8,5
Gráficas Telerañas en comparición
con Gráficas Telerañas Modificadas
Nota que cuando n > 5, cambian los
diámetros de las gráficas.
 6,4
diam 
6,4
 5
W6, 4
diam W6, 4   6
 8,5
diam 
8,5
W8,5
 7
diam W8,5   8
Pebbling numbers for
Modified Web Graphs
n,t
3
4
5
6
2
3
4
5
6
7
7
12
25
46
95
191
9
16
32
64
128 256
11
18
35
67
131 259
13
20
35
68
133
7
8
9
15
22
36
69
134
19
32
64
22
38
NOTA: estos
son límites
inferiores.
Juan Zuñiga
(estudiante)
Empedrado de Gráficas Escalera
f ( En )  2
n
v32
f ( En )  2 :
n
16
8
4
2
1
r
Prueba para f ( En )  2
n
La meta es w1. Hay 2n piedritas.
v1
Caso 1: Supongamos que v1 tiene un
piedrita.
v2
w2
vn
wn
1
w1
Entonces hay a menos 2n - 1 piedritas
adicionales en el lado derecho o en el
lado izquierdo.
Pero f(En-1) = 2n-1: hay bastante para
mover una piedrita a v1 (el segundo
piedrita en v1) o a w1 (la meta).
Caso 2: Supongamos que v1
tiene 0 piedritas. Vamos a usar el
método de inducción.
n = 1: E1 = P2, y ya sabemos
que f(P2) = 21.
En general: supongamos que
f(En) = 2n.
Pongamos 2n+1 piedritas en En+1.
Nota que 2n+1 = 2n + 2n;
entonces tenemos bastante
piedritas para mover una piedrita
a w2, dos veces.
v1
0
w1
v2
w2
vn
wn
Caso 3: la meta es wk.
Parta la grafica en una copia de Ek, y
otra copia de En-k_1.
Si no puedo mover una piedrita de la
copia de Ek á wk , entonces esta Ek
no tiene más que 2k-1 piedritas.
Si no puedo mover una piedrita de la
copia de En-k+1 á wk , entonces esta
En-k+1 no tiene más que 2n-k+1-1
piedritas.
Pero, 2k-1 + 2n-k+1-1 < 2n , entonces
algún copia de una escalera más
pequeña tiene bastante piedritas
para llegar una piedrita a wk.
v1
w1
vk
wk
vn
wn
Resultados de Escaleras para
Victor X. Rodriguez (estudiante)
Números de Empedrados con Respecto a
Propiedades de Gráficas
vértice que corta: si se quita este
vértice de la gráfica, sera inconexa.
c
a
b
Si G tiene un vértice que corta
entonces f(G) > n.
(Cada
vértice
invisible
recibe 1
piedrita)
(Cada
vértice
invisible
recibe 1
piedrita)
b
a
c
3 piedritas en c
Números de Empedrados con
Respecto a Propiedades de Gráficas
Teorema: Si una gráfica G en n vértices
tiene diámetro 2, entonces f(G) ≤ n+1.
Corolario: Si G es 3-conectada y tiene
diámetro 2, entonces f(G) = n.
Nota: el corolario implica que casi toda
grafica satisface f(G) = n.
Números de Empedrados con
Respecto a Propiedades de Gráficas
Cor: Si G es 3-conectada y tiene diámetro
2, entonces f(G) = n.
3-conectada es necesaria:
el diámetro de G es 2, y G
tiene ningun vértice que
corta, pero f(G) = 7.
3
3
G
Números de Empedrados con Respecto a
Propiedades de Gráficas
Cor: Si G es
3-conectada
y tiene
diámetro 2,
entonces
f(G) = n.
f(Pete)=10.
Números Óptimos de Empedrados
¿Cual es el
número
óptimo de
empedrados
de la gráfica
Petersen?
Indirecta: d = 2
(4)
Números Óptimos de Caminos
Escriba Pn como P3t+r donde r es 0, 1, ó 2.
Teorema: El número óptimo de P3t+r es 2t + r.
2
fopt (P3t+r ) = 2t + r
2
1
Números Óptimales de Ciclos
Escriba Cn como C3t+r donde r es 0, 1, ó 2.
Teorema: El número óptimal de C3t+r es 2t + r.
2
fopt (C3t+r ) = 2t + r
1
1
2
2
Números Óptimales de Escaleras
Tenemos un método para investigar los números
óptimos para todas las gráficas que se pueden
definir con inducción.
Una Idea Símilar: Pinzado
Las reglas para
mover pinzas:
una pinza salta
otra hasta un
vértice adyacente.
La pinza saltada
es eliminada.
¿Podemos mover una pinza a cada vértice?
¿Podemos mover una pinza a cada vértice?
¿Qué significa
esta situación
cuando se habla
del número
pinzado de esta
gráfica?
Los resultados de Jason Counihan (estudiante)
• g(Pn) = n-1
• gopt(P2k+r) = k+r
Más resultados de Jason Counihan
• g(Pn) = n-1
• gopt(P2k+r) = k+r
• g(Cn) = n-2
• gopt(C2k+r) = k+r
• g(Kn) = gopt(Kn) = 2
• Si G es bipartita, g(G) es más que el número de
vértices en el subconjunto más grande.
• Si d es el diámetro de G, entonces g(G)  d-1.
Otros estudiantes (que conozco) que han
descubierto algo de empedrados en gráficas
Victor Moreno, (profesor), Juan
Zuñiga, (profesor), Marlene
Merchain, Modesty Briggs
Sean Pederson, Ronald
Martinez, Philip Gonzalez,
Victor Rodriguez
Además: Karl Fedje, Blaise Djegoue, y Jason Counihan
Algunas Preguntas Abiertas
• Relaciones de la conexión de vértices y el
número de empedrados
(al estilo: vértice que corta => f(G) > n)
• Falta mucho de saber en cuanto a determinar
números óptimos de empedrados de varios
tipos de familias de gráficas.
• Es posible encontrar una conexión más fuerte
entre el diámetro, el número de vértices, y el
número de empedrados?
Más Preguntas Abiertas
• La conjetura de Graham (muy famosa)
• El número de empedrados del producto de n
copias de C5 (Herscovici y Higgins ya
resolvieron el caso de n = 2)
• Números de pinzados para muchos tipos o
familias de gráficas
Y más… ¡Si no les falta imaginacion, no
les faltarán de preguntas!
Mi pregunta final (para hoy):
¿Cuales resultados
van a descubrir
Ustedes?