¿Qué es un laberinto?
La pregunta del título no alude a la definición de la palabra “laberinto”, sino a la descripción matemática que adoptaremos. Todos sabemos qué es un laberinto, los hay esencialmente de dos tipos, aquellos que se resuelven con lápiz y papel, y aquellos que son construcciones que se resuelven desde adentro y en los que el diseño del laberinto es descubierto a medida que éste es recorrido. Nos interesan aquí los laberintos del segundo tipo, que describiremos matemáticamente mediante grafos.
Un grafo es un dibujo formado por puntos (o nodos) unidos mediante líneas (o ejes). Aunque puede darse una definición más formal de este concepto (como un conjunto finito de pares ordenados), la definición gráfica que hemos dado será más que suficiente para todos nuestros fines. Los siguientes son ejemplos de grafos, donde los nodos están destacados en azul:
Nótese que el hecho de que dos líneas se corten en un punto no transforma a éste necesariamente en un nodo (Figura 1) y que pude suceder que un eje conecte a un nodo consigo mismo (Figura 2).Un camino en un grafo es un recorrido que comienza y termina en un nodo (eventualmente el mismo) y que va pasando de un nodo a otro a través de los ejes que los conectan (sólo puede cambiar de dirección en un nodo). Un camino puede pasar varias veces por un mismo eje o tocar varias veces un mismo nodo. Como antes, es posible dar una definición más formal de este concepto, pero a todos nuestros fines esta definición informal será más que suficiente. Un grafo es conexo si dado cualquier par de nodos siempre existe un camino que los conecte. Los dos grafos dibujados más arriba son conexos, pero el siguiente no lo es:
Todo laberinto se representará mediante un grafo conexo en el que se hayan destacado dos nodos, llamados entrada y salida. En los dibujos la entrada se marcará con rojo y la salida, con verde. Aquí abajo vemos un laberinto y uno de los grafos que lo representa (donde los nodos indican las bifurcaciones del laberinto):
En la tercera parte veremos otras definiciones referidas a los laberintos y a los grafos que los representan.(A la parte 1 - A la parte 3)
No hay comentarios.:
Publicar un comentario