Grafos
Páginas: 3 (563 palabras)
Publicado: 18 de enero de 2012
Teor´ de Grafos ıa Problemas Abiertos 1. ¿Admite K6 una representaci´n en la que s´lo haya 2 cruces de las aristas? o o Observamos que necesariamente el n´mero de cruces es mayor que 1, ya que,eliminando u un v´rtice que sea incidente con una de las aristas que se cruce, obtendr´ e ıamos una representaci´n plana de K5 , lo que es una contradicci´n. Por otro lado, el siguiente o o ejemplomuestra que tal representaci´n es posible, para K6 , con 3 cruces: o
z z
z
z
z
}
¿Se puede hacer con s´lo 2 cruces? o
La respuesta es afirmativa. De hecho se conocen los n´meros de cortede los grafos u completos Kn , para n = 1, · · · , 12 (para n ≥ 13 es un problema abierto): 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150. e a a 2. ¿Existe un grafo plano con 14 v´rtices, di´metro 3 ycon grado m´ximo igual a 3? Este problema, propuesto por P. Erd˝s, tiene relevancia en la construcci´n de redes de o o ordenadores trabajando en paralelo. La configuraci´n m´xima que se conoce actualoa mente contiene 12 v´rtices: e
v v v v v v v v v v v v
1
3. Conjetura de S. M. Ulam Supongamos que G y H son dos grafos que tienen el mismo n´mero de v´rtices, u e V (G) = {u1 , . . . , un }y V (H) = {v1 , . . . , vn }, n ≥ 3,
y de manera que para cada j = 1, . . . , n, se verifica que G − uj ≈ H − vj . Estudiar si, necesariamente, G ≈ H. El resultado es cierto, por ejemplo, si G y Hson arboles. ´ 4. El Problema del Viajante Un comerciante ha de visitar una sola vez todas las ciudades donde residen sus clientes, y quiere hacerlo de manera que el recorrido sea el m´s cortoposible ¿C´mo se a o puede determinar esta ruta de manera efectiva? Si, por ejemplo, enumeramos todas las posibilidades de ordenar las distintas ciudades (supongamos que hay n), y elegimos la que da elvalor menor, habremos de considerar n! casos. Para hacernos una idea de la magnitud de este n´mero, si pudi´ramos trabajar con el ordenador m´s r´pido que u e a a existe (alrededor de 40 billones de...
z z
z
z
z
}
¿Se puede hacer con s´lo 2 cruces? o
La respuesta es afirmativa. De hecho se conocen los n´meros de cortede los grafos u completos Kn , para n = 1, · · · , 12 (para n ≥ 13 es un problema abierto): 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150. e a a 2. ¿Existe un grafo plano con 14 v´rtices, di´metro 3 ycon grado m´ximo igual a 3? Este problema, propuesto por P. Erd˝s, tiene relevancia en la construcci´n de redes de o o ordenadores trabajando en paralelo. La configuraci´n m´xima que se conoce actualoa mente contiene 12 v´rtices: e
v v v v v v v v v v v v
1
3. Conjetura de S. M. Ulam Supongamos que G y H son dos grafos que tienen el mismo n´mero de v´rtices, u e V (G) = {u1 , . . . , un }y V (H) = {v1 , . . . , vn }, n ≥ 3,
y de manera que para cada j = 1, . . . , n, se verifica que G − uj ≈ H − vj . Estudiar si, necesariamente, G ≈ H. El resultado es cierto, por ejemplo, si G y Hson arboles. ´ 4. El Problema del Viajante Un comerciante ha de visitar una sola vez todas las ciudades donde residen sus clientes, y quiere hacerlo de manera que el recorrido sea el m´s cortoposible ¿C´mo se a o puede determinar esta ruta de manera efectiva? Si, por ejemplo, enumeramos todas las posibilidades de ordenar las distintas ciudades (supongamos que hay n), y elegimos la que da elvalor menor, habremos de considerar n! casos. Para hacernos una idea de la magnitud de este n´mero, si pudi´ramos trabajar con el ordenador m´s r´pido que u e a a existe (alrededor de 40 billones de...
Leer documento completo
Regístrate para leer el documento completo.