Five room puzzle
Esta actividad pertenece al libro de GeoGebra Redes y Grafos.
Este es uno de los más antiguos rompecabezas relacionados con los grafos, descrito en 1957 por Martin Gardner.
En la siguiente construcción tienes dos posibilidades. Si eliges el tipo de puzle imposible, no podrás realizar un paseo que pase una sola vez por cada una de las 16 puertas. ¿Sabrías demostrarlo?
Si eliges el tipo de puzle posible, con 15 puertas, podrás realizar ese paseo: ¡encuéntralo!
Observa que la forma de la figura del puzle es irrelevante. Tal y como pensó Euler en el problema de los puentes, lo importante es su grafo dual. Y en este, el número de vértices y el número de aristas que concurren en cada uno de ellos.
Cuando dos grafos son equivalentes porque tienen el mismo número de vértices y cada arista de uno corresponde a una arista del otro, se dice que son isomorfos.
Por razones de estética y claridad, es habitual transformar, si es posible, un grafo en otro isomorfo sin aristas que se corten. Cuando puede conseguirse, se dice que el grafo es plano.
En esta construcción puedes ver una transformación continua entre grafos isomorfos correspondientes a este puzle (en su versión imposible). El último grafo, sin cortes de aristas, muestra que el grafo es plano.
Autor de la actividad y construcción GeoGebra: Rafael Losada.