Seminario de grafos y algoritmos asociados, basado en el libro "For all practical purposes" de COMAP y organizado por la Olimpíada Matemática Argentina
Por un lado no entiendo mucho si uno puede (por ejemplo) salir por la puerta 3 y entrar a la misma sala por la puerta 12, supongo que sí. En ese caso también se podría preguntar de salir y volver a entrar a la misma sala, y la variante de salir de una sala para ingresar a otra. Como mencionaste, también podría preguntarse por recorrer todas las paredes o de retornar a la puerta de entrada (¿que es...?).
Así como está planteado el problema entiendo que se quiere encontrar un recorrido (o podría ser un circuito) que pasé por todas las puertas exactamente una vez. En la vida real eso no tendría mucho sentido, ya que uno en el recorrido pasaría por las salas más de una vez. Creo que tendría más sentido preguntar si se puede armar un circuito que pase por todas las salas exactamente una vez (y acá dejaría de lado dentro de la sala cómo se recorre la misma). Si armamos el grafo poniendo un vértice por cada sala y una arista por cada puerta el primer problema sería un problema de Euler y el segundo de Hamilton, puede ser?
Me pareció que había publicado un comentario, pero no lo veo: perdón si aparece repetido. Lo que decía es que si los chicos están aburridos, para entretenerlos uno puede proponerles que recorran todas las galerías pasando por cada puerta exactamente una vez (;-).
Pues, podría ser interesante que los niños hagan eso, mientras los padres recorren la muestra con tranquilidad!!! Padres hamiltonianos, con hijos eulerianos!
Por un lado no entiendo mucho si uno puede (por ejemplo) salir por la puerta 3 y entrar a la misma sala por la puerta 12, supongo que sí. En ese caso también se podría preguntar de salir y volver a entrar a la misma sala, y la variante de salir de una sala para ingresar a otra.
ResponderEliminarComo mencionaste, también podría preguntarse por recorrer todas las paredes o de retornar a la puerta de entrada (¿que es...?).
Así como está planteado el problema entiendo que se quiere encontrar un recorrido (o podría ser un circuito) que pasé por todas las puertas exactamente una vez. En la vida real eso no tendría mucho sentido, ya que uno en el recorrido pasaría por las salas más de una vez. Creo que tendría más sentido preguntar si se puede armar un circuito que pase por todas las salas exactamente una vez (y acá dejaría de lado dentro de la sala cómo se recorre la misma).
EliminarSi armamos el grafo poniendo un vértice por cada sala y una arista por cada puerta el primer problema sería un problema de Euler y el segundo de Hamilton, puede ser?
Me pareció que había publicado un comentario, pero no lo veo: perdón si aparece repetido. Lo que decía es que si los chicos están aburridos, para entretenerlos uno puede proponerles que recorran todas las galerías pasando por cada puerta exactamente una vez (;-).
EliminarPues, podría ser interesante que los niños hagan eso, mientras los padres recorren la muestra con tranquilidad!!! Padres hamiltonianos, con hijos eulerianos!
Eliminar