Un problema de ciudades y carreteras
Concurso de El Pais, marzo de 2011
Grafo
El dibujo que hay junto a estas líneas es un grafo, y representa una serie de puntos (pueden ser ciudades, interruptores, puntos de interés, estaciones de metro, ...), llamados nodos unidos por unos trazos (pueden ser carreteras, calles, vías, cables, ...) llamados aristas. Un camino en el grafo es un recorrido por el grafo que usa las aristas para saltar de nodo en nodo.
Encuentra un camino en el grafo de forma que se recorran todos los números una única vez y se vuelva al número inicial, o bien, demuestra que es imposible. Puedes empezar por el número que quieras, pero (salvo el inicial) no puedes pasar dos veces por el mismo nodo.
No es necesario recorrer todos los caminos, si no todos los nodos (números). Este tipo de caminos se llaman Hamiltonianos, y los que recorren todos los caminos, Eulerianos.
1 comentario:
Qué buen problema, me ha llevado un tiempo pero lo he conseguido resolver. Es de los que me han gustado :D
Tiene que ver que ahora mismo esté estudiando grafos en clase, pienso mucho en estas cosas :)
Publicar un comentario