Labyrinthes et fil d’Ariane

Piste rouge Le 24 février 2014  - Ecrit par  Pierre Rosenstiehl Voir les commentaires (1)

Les Crétois de l’Antiquité ont diffusé abondamment à travers le monde, par la danse, les graffiti et les pièces de monnaie, le mythe du labyrinthe et du fil d’Ariane. Etait-ce la première apparition d’un algorithme topologique, et en germe, déjà l’annonce de nos pratiques informatiques ? La théorie des graphes éclaire le sujet.

Des couloirs, des carrefours et un explorateur myope

Il s’agit de trouver une méthode imparable pour dénicher un Minotaure immobile dans un labyrinthe, en ressortir, et cela en ne recourant, en tout lieu de l’exploration, qu’aux traces du cheminement déjà accomplit. Décrivons le terrain où s’aventure un explorateur.

Chaque couloir a deux bouts, chacun des bouts de couloir est incident à un carrefour (le même carrefour pour les deux s’il s’agit d’un couloir-boucle) : ainsi est constitué un réseau, ce que, en mathématiques, on appelle un graphe. Les graphes considérés ci-dessous sont finis et s’ils sont tracés dans le plan sans croisement, considérez cela comme fortuit ; la planarité du labyrinthe ne joue aucun rôle ici dans nos algorithmes ; le lecteur pourrait ajouter à Versailles des couloirs ponts ou tunnels à volonté.

Quand un explorateur se présente au bout d’un couloir, il se retrouve à l’autre bout, lequel est incident à un carrefour, que nous appellerons $X$ ; de là, pour progresser, il se présente à l’un des bouts de couloir incidents à $X$, etc., on appelle cela cheminer.

L’explorateur peut, en $X$, laisser une trace de son passage, plaçant une marque de type « alpha » en bout du couloir par lequel il est arrivé en $X$, une marque de type « bêta » en bout du couloir d’où il quitte $X$.

Si l’explorateur, parti d’un premier carrefour-entrée, ne fait usage que des marques alpha et bêta inscrites en un carrefour pour y choisir sa route, on dit qu’il s’agit d’un explorateur myope, c’est-à-dire qu’il ne voit en un carrefour que les bouts de couloir incidents à ce carrefour : il n’a pas de vue d’ensemble du labyrinthe, il n’en a pas la carte ; on pourrait même dire qu’il est en train de la relever ! Ainsi se définit une situation labyrinthique, et le réseau où un explorateur myope chemine mérite (pour celui-ci) le nom de labyrinthe.

Si l’explorateur quitte un carrefour par le bout de couloir d’où il vient d’arriver, on dit qu’il rembobine un fil imaginaire sur une pelote imaginaire. Le rembobinage simule le retour sur ses pas. Il peut s’agir d’un retrait stratégique pour mieux progresser ensuite, ce retrait célèbre vanté par Héraclite (on ne méditera jamais assez sur ce fragment : « rien n’est plus cher à l’éclosion que le retrait »).

JPEG - 52.2 ko
Dédale de Chartres en 3D évoquant l’histoire de Thésée et Ariane

Selon l’aventure mythique crétoise, l’architecte Dédale a construit le labyrinthe alambiqué sur ordre du roi Minos pour y enfermer le Minotaure, mi-homme mi-taureau, progéniture de la reine Pasiphaé amoureuse d’un taureau. Dédale n’a plus les plans du labyrinthe ni la mémoire de ses multiples circonvolutions.

Afin d’aider l’explorateur, en l’occurrence le prince Thésée venu d’Athènes combattre le Minotaure, Dédale lui fournit secrètement, par la main de la princesse Ariane, une pelote de laine. Le stratagème doit lui permettre d’atteindre le Minotaure, et éventuellement de retrouver la porte du labyrinthe où Ariane, postée là avec sa sœur Phèdre, retient le bout du fil de la pelote : alternativement Thésée débobine la pelote en avançant, la rembobine en revenant sur ses pas. Donc, Thésée ne cherche pas tant à assurer sa fuite grâce au fil qui le relie à Ariane, qu’à progresser finement dans le labyrinthe et dénicher le Minotaure à coup sûr.

Les peintres de la Renaissance italienne ont créé le concept abstrait de représentation, devenu cher aux mathématiciens. Ci-dessus, dans un même paysage on voit les mêmes personnages à différents instants ! et surtout : cette bâtisse alambiquée constituée d’un couloir filiforme unique qui n’est pas un labyrinthe proprement dit, mais s’affirme comme un fil d’Ariane développé dans un labyrinthe hypothétique et virtuel dont il faut se contenter d’ une représentation. Cette courbe aux méandres très ramassés dessinée dans le plan, nous l’appellerons dédale mathématique ; mais sans trop nous étonner que la langue courante confonde souvent l’objet-le labyrinthe — et sa représentation-le fil d’ Ariane.

Une première ruse du mythe, pour vaincre le labyrinthe, consiste à ne jamais prendre un couloir deux fois dans le même sens. Cette consigne sera préservée dans tous les algorithmes du labyrinthe présentés ci-dessous. Reste à savoir quand Thésée doit rembobiner son fil, et jusqu’où. Il semble que Dédale aurait fait aussi la recommandation suivante : toujours aller de l’avant et ne rembobiner que s’il n’y a pas d’autre solution pour progresser (blocage), mais rembobiner juste un peu, c’est-à-dire jusqu’au prochain carrefour où débobiner devient possible.

Le stratagème des deux ruses de la pelote, évoqué par Phérécyde [1], assure à Thésée de parcourir complètement le labyrinthe, c’est-à-dire tout couloir une fois dans chaque sens, ce qu’on appellera une solution du labyrinthe. Résultat non démontré dans l’Antiquité, bien sûr ! Notons ici qu’une telle solution permet de découvrir le Minotaure où qu’il se terre, de découvrir toutes les éventuelles sorties du labyrinthe et de se retrouver in fine, quand tout couloir a été pris deux fois, à l’entrée dont on est parti (démonstration de l’inévitable retour au carrefour d’entrée laissée au lecteur comme un exercice de « parité », mettant en jeu le fait que tout couloir a deux bouts). Plutôt que d’analyser l’algorithme de Dédale dont la justesse est assez intuitive, nous allons définir celui de Trémaux, plus célèbre parce que plus généreux en sous-produits de calculs.

Arbres et arborescences

JPEG - 21.3 ko
Graphe d’un labyrinthe

La théorie des graphes dit graphe plutôt que réseau, arête plutôt que couloir, sommet plutôt que carrefour (allusion à la théorie des polyèdres et des configurations chimiques), afin de faire un pas de plus vers l’abstraction : pas de longueur ni de largeur d’arête, pas de droite ni de gauche dans les arêtes et les sommets.

Une définition de « topologie combinatoire » élémentaire est la suivante : un arbre est un graphe connexe (ce qui veut dire qu’on peut y cheminer de tout sommet à tout autre) sans cycle (à y cheminer « simplement », c’est-à-dire sans prendre deux fois une même arête, on ne rencontre que des sommets jamais rencontrés) [2].

De la définition il découle qu’à un sommet arbitrairement choisi dans l’arbre — appelons-le racine — va correspondre une orientation des arêtes obtenue par des cheminements simples à partir de la racine. La donnée de la racine d’un arbre définit donc ce qu’on appelle une arborescence. Procédons à un cheminement complet d’une arborescence : partant de la racine, on débobine dans les couloirs dans le sens de l’orientation, on rembobine en sens contraire ; et on remarque que rembobiner juste un peu est ici une nécessité, car abandonner une occasion d’explorer un couloir alors qu’on rembobine, c’est l’abandonner pour toujours (absence de cycle).

Profitons de cette remarque pour définir un cycle en termes de cheminements. Un cycle d’un graphe est un sous-ensemble non vide de ses arêtes tel qu’à y cheminer à partir d’un sommet arbitrairement choisi sur le cycle, sans retrait, toutes les arêtes s’en trouvent parcourues une fois exactement dès que l’on retrouve ce sommet. Alors quelle serait la consigne myope pour trouver une solution du labyrinthe s’il y existait un ou plusieurs cycles.

JPEG - 8.4 ko
Cheminement complet d’un arbre orienté par son enracinement

De l’observation de l’exploration du labyrinthe-arborescence a jailli l’algorithme de Trémaux (conversation relatée par Édouard Lucas dans Théorie des nombres en 1891 [3]).

L’idée de l’ingénieur Trémaux

L’idée de l’ingénieur Trémaux Trémaux reste fidèle aux principes de l’explorateur avisé dans un graphe connexe :

(i) ne pas prendre deux fois un couloir dans le même sens, et

(ii) rembobiner, c’est toujours rembobiner un peu, c’est-à-dire jusqu’au premier carrefour où débobiner devient possible.

Mais qu’en est-il du choix de l’instant de rembobiner ? Charles-Pierre Trémaux, ingénieur polytechnicien des télégraphes [4], a eu l’idée de transformer tout réseau, par cheminement labyrinthique, en un labyrinthe arborescent. Il propose de rembobiner un peu chaque fois que l’explorateur avec sa pelote vient à buter sur le fil. Cela arrivera, disons en un carrefour $X$ juste après un débobinage le long du couloir $C$. Remarquons qu’ il n’y a pas d’occasion vraiment perdue à rembobiner là, puisque l’explorateur repassera de toutes manières en $X$ en rembobinant le fil sur lequel il a buté.

Ce faisant, Trémaux propose de déconnecter virtuellement le bout de couloir $C$ du carrefour $X$, ce qui ne peut nuire à la connexité du labyrinthe. Comme les cycles du labyrinthe seront détruits lors des opérations virtuelles et sans oubli (grâce aux retraits juste un peu), in fine le labyrinthe est devenu un labyrinthe arborescent, en vertu des définitions vues ci-dessus. Enfin, la solution trouvée du cheminement complet de l’arborescence est solution du labyrinthe de départ ; CQFD.

JPEG - 16.5 ko
Déroulement et enroulement du fil d’Ariane selon Trémaux

Dans le « diaporama » ci-contre, apparaissent les états successifs du fil et de la pelote au cours du déroulement de l’algorithme de Trémaux, appliqué au graphe à trois cycles tracé plus haut.

L’algorithme universel des labyrinthes

Les lecteurs qui cultivent l’art de l’écriture concise des algorithmes préfèreront la règle universelle pour construire une solution d’un labyrinthe sans recourir à une pelote :

(i) ne pas prendre deux fois un couloir dans le même sens ;

(ii) en un carrefour ne reprendre à rebours le couloir par lequel on est arrivé pour la première fois, que s’il n’y a pas d’autre possibilité.

La preuve de ce troisième algorithme, plus délicate, n’est pas donnée ici ; elle est en fait plus longue et plus délicate que celle des algorithmes du fil. On vérifiera facilement que l’algorithme de Dédale en est un cas particulier.

L’algorithme de Trémaux en est aussi un cas particulier, certes délicat à programmer, mais offrant de riches sous-produits topologiques [5]. Certains l’appellent « la recherche en profondeur », ignorant à la fois l’existence de Trémaux et de Dédale, alors que paradoxalement c’est ce dernier qui creuse plus profond, comme on le vérifie aisément (un peu d’histoire des mathématiques ne peut nuire aux mathématiques !).

Les dédales historiques

JPEG - 11.7 ko
Pièces de monnaie de l’Antiquité grecque (le dédale a son entrée par le fond en haut)

Après la présentation de trois algorithmes du cheminement myope, venons-en aux représentations du labyrinthe par un fil aux mille détours dessiné dans le plan ; elles nous conduisent à de magnifiques énoncés mathématiques d’où une meilleure compréhension du problème du labyrinthe et, du coup, à un approfondissement de la signification du mythe.

Depuis 4000 ans les artisans ont confectionné des objets labyrinthiques filiformes admirables. Quelles en sont les propriétés ?

On appelle dédale une courbe du plan fermée (les deux extrémités de la courbe étant confondues ou presque selon les cas) sans intersection avec elle-même et tassée sur elle-même, d’où ses multiples points de contact. Les dédales historiques rivalisent en beauté d’exécution.

Le tout premier dédale de l’Histoire est le graffiti crétois, , incisé dans des tablettes de terre cuite ou frappé dans le bronze des pièces de monnaie grecques. Il est habituellement tracé par les bords qui le délimitent. Ceux-ci forment un labyrinthe avec un seul carrefour à quatre couloirs incidents, la croix. Le dédale, dans le fond, se parcourt sans choix. Remarquons la presque symétrie du dédale crétois par rapport à l’axe de sa croix.

JPEG - 23 ko
Mosaïque romaine typique (le dédale blanc a son entrée à gauche)

Les Romains antiques aimaient les mosaïques labyrinthiques, partageant l’espace rectangulaire en quatre. Le dédale romain dessine ses circonvolutions serrées dans un premier quartier, puis selon un schéma identique dans le deuxième, le troisième quartier et le quatrième quartier, pour aboutir au centre de la configuration, en longeant in fine le tronçon de courbe initial.

JPEG - 28.5 ko
Pavage de la cathédrale de St Quentin (dédale noir avec entrée à droite)

Les artisans mille ans plus tard excellaient dans la marqueterie des pavages de cathédrale, selon un schéma dit Chemin de Jérusalem ou de type Chartres. La courbe tourne autour d’un centre sur douze couches, commençant sur le bord face au grand portail, dans une gorge radiale jamais traversée par la courbe ; sur les trois autres axes radiaux de la croix alternent points de traversée et points de rebroussement (ou « retrait ») ; in fine la courbe arrive au centre par la gorge où il semble aisé de joindre les deux bouts de la courbe, c’est-à-dire sans opérer de circonvolution. Ce dodécadédale a été fidèlement colporté par les compagnons du Moyen Age à travers toute l’Europe.

Par abus de langage, les dédales historiques sont souvent appelés labyrinthes. On remarque une forte parenté mathématique entre eux. Ajoutons que leurs presque-symétries intérieures dégagent une beauté malicieuse brouillant les repères des regards qui tentent d’en suivre le tracé (en anglais puzzled).

Le point de vue mathématique

Pour nous résumer, demandons-nous quelle est la structure mathématique du fil d’Ariane ? Tentons de nous affranchir de la matérialité de la pelote, au demeurant bien commode pour l’intuition.

Un labyrinthe, selon notre définition, est un graphe sur lequel opère un algorithme de cheminement à partir d’un sommet $X_0$, ne recourant pour progresser en chaque carrefour $X$ qu’à la donnée des incidences en $X$ et qu’aux traces des passages antérieurs en $X$.
Un mot $\mu$ à doubles occurrences sur un alphabet $A$ est dit parenthésé si chacune des lettres de $A$ a ses deux occurrences dans $\mu$, distribuées de telle sorte que toute paire de doubles occurrences ne soit jamais entrelacée, comme
\[\mu = a b b c d d c a \]
où jamais ne figure une disposition entrelacée, telle $a..b..a..b$.

Citons un bel exemple de mot parenthésé sur l’alphabet des contacts d’un dédale : les contacts intérieurs apparaissent, chacun deux fois, sur la courbe selon un mot parenthésé ; les contacts extérieurs également.

JPEG - 9.8 ko
Contacts intérieurs (minuscules) et extérieurs (majuscules) d’un dédale mathématique

Venons-en à notre propos principal. Un fil d’Ariane d’un graphe est un cheminement produisant un mot parenthésé sur l’alphabet des arêtes.

Le fil d’Ariane réduit en un sommet courant, est le mot courant d’un fil d’Ariane dont toute paire collée, de type $XX$, a été effacée (rembobinage) au fur et à mesure du cheminement ; le fil réduit ne contient donc que des premières occurrences d’arête (il permet de fuir au plus vite par rembobinage). Notons que l’arête de retrait dans les algorithmes de type « fil d’Ariane » est simplement la dernière arête du fil réduit. L’algorithme de Trémaux en est un cas particulier, qui exploite cette propriété pour améliorer la vitesse d’exécution.

Des problèmes de type filiforme venus de divers contextes (« divers ailleurs ») — ici celui de la mythologie crétoise et de notre instinct ancestral d’explorer par cheminement — se précisent et se ramifient quand sont posés quelques concepts mathématiques pertinents.

On se demandera, dans cet esprit, quelles définitions topologiques suggèrent : une pelote de fil, un nœud, une tresse, une danse en farandole avec ou sans croisements, l’organigramme logique d’un programme machine, un moteur de recherche [6]

Un roman

Les figures qui illustrent cet article sont extraites du roman de l’auteur, Le Labyrinthe des jours ordinaires, Paris, Éditions du Seuil – La Librairie du XXIè siècle, 2013, 304 p., « Un roman oulipien qui obéit lui-même aux lois qu’il énonce », dit le critique du Magazine littéraire [7].

Post-scriptum :

L’auteur et la rédaction d’Images des mathématiques remercient les relecteurs dont les noms ou pseudonymes sont Marc Jambon, Ludovic Marquis et Roger Mansuy pour leurs questions et leurs commentaires qui ont permis d’améliorer et de préciser une première version de cet article.

Article édité par Michèle Audin

Notes

[1Il s’agit de l’historien grec Phérécyde d’Athènes, qui vécut au cinquième siècle avant Jésus-Christ.

[2Il est question d’arbres (mathématiques) dans plusieurs articles d’Images des mathématiques, notamment dans celui-ci et celui-là. Pour la labyrinthologie on n’a recouru qu’à des concepts définis en termes de cheminements.

[3Ce livre de Lucas est disponible sur le site Gallica de la Bibliothèque nationale de France. La mention du « théorème de Trémaux » se trouve p.103.

[4D’après la base de données des anciens élèves de l’École polytechnique, Charles-Pierre Trémaux a vécu de 1859 à 1882. Cette courte vie explique qu’il n’y ait pas de référence directe à un article de lui.

[5Comme le montrent les travaux de R.E.Tarjan.

[6Certaines des questions posées sont évoquées dans certains articles déjà parus sur Images des mathématiques, par exemple celui-ci. On pourra consulter… le moteur de recherche du site !

[7Les lecteurs qui lisent l’anglais et fréquentent de bonnes bibliothèques pourront lire aussi le livre de Hermann Kern, Through the Labyrinth. Designs and Meanings over 5,000 Years, New York, Prestel Verlag, 2000, 360 p. et l’article de P. Rosenstiehl & R.E. Tarjan, « Gauss codes, planar hamiltonian graphs, and stack sortable permutations », pp. 375-390 dans le Journal of Algorithms 5, 1984.

On consultera avec plaisir l’album de Franco Maria Ricci, LABYRINTHE, préfacé par Umberto Eco, Rizzoli NY, 2013 ; ainsi que l’ouvrage de l’encyclopédiste Hermann… 360 p ; et enfin les cartes savantes du démographe Hervé le Bras, dans Essai de géométrie sociale, Odile Jacob, 2000.

Partager cet article

Pour citer cet article :

Pierre Rosenstiehl — «Labyrinthes et fil d’Ariane» — Images des Mathématiques, CNRS, 2014

Crédits image :

Image à la une - Le tableau du combat de Thésée et le Minotaure dans le labyrinthe de Chartres, Quattrocento, Collection Campana, Musée d’Avignon.
Les images des dédales sont dans le domaine public.
Les autres figures (dessins d’arbres et arborescences) sont extraites du roman de l’auteur et lui sont dues.
Dédale de Chartres en 3D évoquant l’histoire de Thésée et Ariane - Collection Campana, musée d’Avignon

Commentaire sur l'article

  • Labyrinthes et fil d’Ariane

    le 25 février 2014 à 07:15, par Marc JAMBON

    Cet article est vraiment passionnant. S’il est évident de résoudre un labyrinthe arborescent, le cas général est franchement difficile, j’ai eu bien du mal à comprendre et à appliquer la méthode de Trémaux au labyrinthe de Versailles, seul exemple non trivial donné dans cet article, pour finalement y parvenir. Ce Labyrinthe de Versailles existe-t-il, aujourd’hui encore, en vraie grandeur sur le terrain ?

    Pour les amateurs, il existe [en France] un labyrinthe végétal en vraie grandeur, et probablement d’autres, suivre ce lien.

    http://www.musee-du-pruneau.com/dedal_prune.html

    Pour conclure, félicitations à l’auteur.

    Répondre à ce message

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM