Download G - California State University Channel Islands
Document related concepts
no text concepts found
Transcript
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?