sábado, 26 de marzo de 2011

Un problema de ciudades y carreteras

Concurso de El Pais, marzo de 2011

Grafo

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.

Solución

1 comentario:

Anónimo dijo...

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 :)