Pasillos, cruces y un explorador miope

Se trata de descubrir un método infalible para encontrar un Minotauro inmóvil dentro de un laberinto y salir de ahí, sin recurrir a nada más que a la exploración y a los rastros del camino ya hecho. Describamos el terreno donde se aventura un explorador.

Cada pasillo tiene dos extremos, cada uno de los extremos del pasillo es incidente a un cruce (el mismo cruce para ambos si se trata de un pasillo que se cierra sobre sí mismo) : de este modo se establece una red, que en matemáticas llamamos grafo. Los grafos considerados acá abajo son finitos ; si están trazados en el plano sin cruce, considere eso como fortuito. Que el laberinto sea plano no juega ningún rol en nuestros algoritmos. El lector podrá añadir a su ciudad natal pasillos, puentes o túneles a voluntad.

Cuando un explorador llega al extremo de un pasillo, aparece en el otro extremo, el cual es incidente a un cruce que llamaremos $X$ ; de ahí, para seguir avanzando, él llega a uno de los extremos de pasillo incidentes a $X$, etc. Llamamos a esto abrirse camino.

En $X$, el explorador puede dejar un rastro de su paso, dejando una marca de tipo ’’alfa’’ en el extremo del pasillo por el cual él llegó a $X$, y una marca de tipo ’’beta’’ en el extremo del pasillo desde donde deja $X$.

Si el explorador, habiendo salido de un primer cruce-entrada, usa solo las marcas alfa y beta inscritas en un cruce para decidir ahí su ruta, se dice que se trata de un explorador miope, es decir, que no ve en un cruce nada más que las marcas de pasillos incidentes a ese cruce. No tiene la vista global del laberinto, no tiene el mapa. ¡Uno incluso podría decir que está dibujando el mapa ! Así queda definida una situación laberíntica, y la red donde el explorador miope camina merece (para él mismo) el nombre de laberinto.

Si el explorador abandona un cruce por el extremo de un pasillo por donde acaba de llegar se dice que él rebobina un hilo imaginario sobre un ovillo imaginario. El rebobinado simula el regreso sobre sus pasos. Puede tratarse de una retirada estratégica para después avanzar mejor, una famosa retirada alabada por Heráclito (uno no meditará nunca lo suficiente acerca de este fragmento : ’’nada es más valioso para la eclosión que la retirada’’).

Dédalo de Chartres en 3D evocando la historia de Thésée y Ariane

Según la aventura mítica cretense, el arquitecto Dédalo construyó el laberinto alambicado por orden del rey de Minos para encerrar ahí al Minotauro, mitad hombre y mitad toro, hijo de la reina Pasifae, enamorada de un toro. Dédalo no se quedó con los planos del laberinto ni con el recuerdo de sus múltiples circunvoluciones.

Con el fin de ayudar al explorador, cuando el príncipe Teseo vino de Atenas para combatir al Minotauro, Dédalo le proporcionó secretamente, por mano de la princesa Ariadna, un ovillo de lana. La estratagema debía permitirle encontrar al Minotauro y eventualmente regresar a la entrada del laberinto donde Ariadna, que se había quedado ahí con se hermana Fedra, sostenía el extremo del hilo del ovillo. Paralelamente, Teseo desenrollaba el ovillo cuando avanzaba y lo enrollaba cuando volvía sobre sus pasos. Por lo tanto, Teseo no busca tanto asegurar su salida gracias al hilo que lo une a Ariana, sino avanzar cuidadosamente por el laberinto y descubrir al Minotauro.

Las pinturas del Renacimiento italiano crearon el concepto abstracto de representación, que pasó a ser muy apreciado por los matemáticos. Ahí arriba, ¡en un mismo paisaje vemos a los mismos personajes en diferentes momentos ! Sobre todo, vemos esa construcción alambicada constituida por un pasillo filiforme único que no es un laberinto propiamente tal, sino que se erige como un hilo de Ariadna desenrrollado en una laberinto hipotético y virtual, con cuya representación hay que contentarse. A esta curva con meandros muy cercanos y dibujada en el plano la llamaremos dédalo matemático. No nos sorprendamos demasiado de que el lenguaje corriente confunda a menudo el objeto-laberinto y su representación mediante el hilo de Ariadna.

Un primer ardid del mito para vencer el laberinto consiste en no tomar jamás un pasillo dos veces en el mismo sentido. Esta instrucción será mantenida en todos los algoritmos del laberinto presentados acá abajo. Falta saber cuándo Teseo debe enrollar su hilo, y hasta dónde. Parece que Dédalo habría recomendado también lo siguiente : siempre ir hacia adelante y rebobinar solo cuando no haya otra alternativa para avanzar (bloqueo), pero enrollar solo un poco, es decir, hasta el próximo cruce donde el rebobinar sea posible.

La estratagema de los dos ardides del ovillo, evocado por Ferécides [1], asegura a Teseo recorrer completamente el laberinto, es decir, cada pasillo una vez en cada sentido, lo que llamaremos una solución de laberinto. ¡Resultado no demostrado en la Antigüedad, por supuesto ! Notemos que una tal solución permite descubrir al Minotauro donde sea que esté escondido, descubrir todas las eventuales salidas del laberinto y encontrarse in fine (en la parte final) cuando todo pasillo haya sido usado dos veces, en la entrada desde la cual uno partió (la demostración del inevitable regreso al cruce de entrada es dejada al lector como un ejercicio de ’’paridad’’, poniendo en juego el hecho de que todo pasillo tiene dos extremos). Más que analizar el algoritmo de Dédalo, cuya precisión es bastante intuitiva, vamos a definir el de Trémaux, más famoso porque es más generoso en subproductos de cálculos.

Árboles y arborescencias

Grafo de un laberinto

La teoría de grafos hace referencia a grafo más que a red, arista más que pasillo, y vértice más que cruce (alusión a la teoría de los poliedros y de las configuraciones químicas), con el fin de dar un paso más hacia la abstracción : ni longitud ni anchura de arista, ni derecha ni izquierda en las aristas y los vértices.

Una definición de ’’topología combinatoria’’ elemental es la siguiente : un árbol es un grafo conexo (lo que quiere decir que uno puede recorrerlo desde todo vértice al otro) sin ciclos (al recorrerlo ’’simplemente’’, es decir sin tomar dos veces una misma arista, uno encuentra solo vértices nunca antes encontrados) [2].

De la definición se deriva que a un vértice arbitrariamente elegido dentro del árbol —llamémosle la raíz— va a corresponder una orientación de las aristas obtenida por los recorridos simples a partir de la raíz. La definición de la raíz de un árbol define entonces lo que uno llama una arborescencia. Sigamos un recorrido completo de una arborescencia : partiendo desde la raíz, uno desenrolla en los pasillos en el sentido de la orientación, y enrolla en sentido contrario ; y se destaca que enrollar solo un poco es aquí una necesidad, ya que abandonar la oportunidad de explorar un pasillo cuando uno enrolla es abandonarla para siempre (ausencia de ciclo).

Aprovechemos este comentario para definir un ciclo en términos de recorridos. Un ciclo de un grafo es un subconjunto no vacío de sus aristas tal que, al avanzar a partir de un vértice arbitrariamente elegido sobre el ciclo, sin regresar, todas las aristas se encuentran recorridas una vez exactamente desde que uno vuelve a ese vértice. ¿Cuál sería entonces la instrucción miope para encontrar una solución al laberinto si hubiesen uno o varios ciclos ?

Recorrido completo de un arból orientado a partir de su raíz

De la observación de la exploración del laberinto-arborescencia surgió el algoritmo de Trémaux (conversación narrada por Édouard Lucas en Teoría de los números en 1891 [3]).

La idea del ingeniero Trémaux

La idea del ingeniero Trémaux es fiel a los principios del explorador prudente en un grafo conexo :

(i) no tomar dos veces un pasillo en el mismo sentido, y

(ii) desenrollar es siempre desenrollar un poco, es decir, hasta la primera encrucijada donde desenrollar resulta posible.

¿Pero qué hay acerca de elegir el momento de enrollar ? Charles-Pierre Trémaux, ingeniero de la Escuela Politécnica especializado en telecomunicaciones [4], tuvo la idea de transformar toda red en un camino laberíntico, en un laberinto arborescente. Propuso enrollar un poco cada vez que el explorador con su ovillo se topara con el hilo. Eso sucederá, digamos en un cruce $X$ justo después de haber desenrollado a lo largo de un pasillo $C$. Señalemos que no perdemos nada enrollando ahí, pues el explorador volverá a pasar de todas maneras en $X$ al enrollar el hilo con el cual se topó.

Al hacer esto, Trémaux propuso desconectar virtualmente el extremo del pasillo $C$ del cruce $X$, lo que no puede perjudicar la conectividad del laberinto. Como los ciclos del laberinto serán destruidos durante las operaciones virtuales y sin olvido (gracias a las breves ’’vueltas atrás’’), in fine el laberinto pasa a ser un laberinto arborescente, en virtud de las definiciones vistas más arriba. Finalmente, la solución encontrada del recorrido completo de la arborescencia es solución del laberinto de partida, QED.

Enrollado y desenrollado del hilo de Ariana según Trémaux

En el ’’diaporama’’ de enfrente aparecen los estados sucesivos del algoritmo de Trémaux aplicado al grafo de tres ciclos trazado más arriba.

El algoritmo universal de los laberintos

Los lectores que cultivan el arte de la escritura concisa de los algoritmos preferirán la regla universal para construir una solución de un laberinto sin recurrir a un ovillo :

(i) no tomar dos veces un pasillo en el mismo sentido ;

(ii) en un cruce, no regresar por el pasillo por el cual se llegó la primera vez amenos que no haya ninguna otra posibilidad.

No damos aquí la prueba (más delicada) de este tercer algoritmo ; de hecho, es más larga y más delicada que la de los algoritmos del hilo. Se comprobará fácilmente que el algoritmo de Dédalo es un caso particular.

El algoritmo de Trémaux también es un caso particular, desde luego delicado de programar, pero ofrece ricos subproductos topológicos [5]. Algunos lo llaman ’’la búsqueda en profundidad’’, ignorando a la vez la existencia de Trémaux y de Dédale, mientras que paradojalmente es este último quien ahonda más profundamente, como se puede verificar con facilidad (un poco de historia de las matemáticas ¡no puede perjudicar a las matemáticas !).

Los dédalos históricos

Monedas de la Antigüedad griega (el dédalo tiene su entrada en el fondo arriba)

Después de presentar tres algoritmos de recorrido miope, vayamos a las representaciones del laberinto por un hilo con mil desvíos dibujado en el plano ; éstas nos conducen a magníficos enunciados matemáticos que llevan a una mejor comprensión del problema del laberinto y, como resultado, a una profundización del significado del mito.

Desde hace 4000 años los artesanos han confeccionado objetos laberínticos filiformes admirables. ¿Cuáles son sus propiedades ?

Se llama dédalo a una curva del plano cerrado (los dos extremos de la curva se confunden, o casi, según los casos) sin intersección con ella misma y recogida sobre sí, motivo de sus múltiples puntos de contacto. Los dédalos históricos compiten en hermosura de ejecución.

El primerísimo dédalo de la historia es el grafiti cretense, tallado en tabletas de greda o grabado en el bronce de monedas griegas. Es habitualmente trazado por los bordes que lo delimitan. Estos forman un laberinto con un solo cruce de cuatro pasillos incidentes, la cruz. El dédalo, en el fondo, se recorre sin elección. Destaquemos la casi simetría del dédalo cretense en relación con el eje de su cruz.

Típico mosaico romano (el dédalo blanco tiene su entrada a la izquierda)

Los antiguos romanos adoraban los mosaicos laberínticos, dividiendo el espacio rectangular en cuatro. El dédalo romano dibuja sus circunvoluciones estrechas en el primer cuadrante y después, según un esquema idéntico, en el segundo, en el tercero y en el cuarto cuadrante, para desembocar en el centro de la configuración, bordeando en el tramo de curva inicial.

Enlozado de la catedral de San Quintin (dédalo negro con entrada a la derecha)

Mil años más tarde, los artesanos se destacaban en la marquetería de los recubrimientos de catedral, según un modelo llamado Camino de Jerusalén o de tipo Chartres. La curva gira alrededor de un centro de doce capas, comenzando sobre el borde frente al gran portal, en un cuello radial nunca atravesado por la curva ; sobre los otros tres ejes radiales de la cruz se alternan punto de cruce y puntos de cambio de sentido (o ’’retirada’’). Como resultado, la curva llega al centro por el cuello donde parece fácil unir los dos extremos de la curva, es decir, sin hacer una circunvolución. Ese dodecadédalo fue fielmente divulgado por los oficiales artesanos de la Edad Media por toda Europa.

Por error de lenguaje, los dédalos históricos a menudo son llamados laberintos. Se advierte un fuerte parentesco matemático entre ellos. Añadamos que sus cuasi simetrías interiores despliegan una belleza maliciosa, confundiendo los puntos de referencia en las miradas que tratan de seguir el trazado (en inglés, puzzled).

El punto de vista matemático

Para resumir, preguntémonos ¿cuál es la estructura matemática del hilo de Ariadna ? Tratemos de liberarnos de la materialidad del ovillo, a fin de cuentas bien cómodo para la intuición. Un laberinto, según nuestra definición, es un grafo sobre el cual opera un algoritmo de recorrido a partir de un vértice $X_0$, que para avanzar en cada encrucijada $X$ no recurre sino a las informaciones de las incidencias en $X$ y a los trazos de las pasadas anteriores en $X$. Una palabra $\mu$ que tiene dobles ocurrencias en un alfabeto $A$ es llamada paréntesizada si cada una de las letras de $A$ tiene sus dos ocurrencias en $\mu$, distribuidas de tal manera que toda pareja de dobles ocurrencias no esté nunca entrelazada. Por ejemplo
\[\mu = a b b c d d c a \]
donde nunca figura una disposición entrelazada, tipo $a..b..a..b$.

Citemos un bonito ejemplo de palabra paréntesizada en el alfabeto de contactos de un dédalo : los contactos interiores aparecen, cada uno dos veces, sobre la curva según una palabra paréntesizada ; igualmente los contactos exteriores.

Contactos interiores (minúsculas) y exteriores (mayúsculas) de un dédalo matemático

Lleguemos a nuestro propósito inicial. Un hilo de Ariadna de un grafo es un recorrido que produce una palabra paréntesizada en el alfabeto de las aristas.

El hilo de Ariadna reducido en un vértice considerado en un instante, es la palabra obtenida en ese instante a partir de un hilo de Ariadna en el cual toda pareja unida, de tipo $XX$, ha sido borrada (enrollamiento) a medida que se recorre ; el hilo reducido no contiene sino las dos primeras ocurrencias de la arista (esto permite huir lo más rápido posible por enrollamiento). Notemos que la arista de regreso en los algoritmos de tipo ’’hilo de Ariana’’ es simplemente la última arista del hilo reducido. El algoritmo de Trémaux es un caso particular de esto, que explota esta propiedad para mejorar la velocidad de ejecución.

Los problemas de tipo filiforme venidos de diversos contextos —aquí el de la mitologia cretense y de nuestro instinto ancestral de explorar recorriendo— se precisan y se ramifican cuando se plantean algunos conceptos matemáticos pertinentes.

Uno se preguntará, en ese espíritu, qué definiciones topológicas sugieren un ovillo de hilo, un nudo, una trenza, un baile de farandola con o sin cruzarse, el organigrama lógico de una máquina para programar, un motor de búsqueda [6]…

Una novela

Las figuras que ilustran este artículo fueron extraídas de la novela del autor, Le Labyrinthe des jours ordinaires, Paris, Éditions du Seuil – La Librairie du XXIè siècle, 2013, 304 p., ’’Una novela oulipiana (de OuLiPo, acrónimo en francés de Taller de Literatura Potencial) que obedece por sí mismo a las leyes que enuncia’’, dice la crítica del Magazine littéraire [7].