labyrinthe

Imaginez des couloirs qui se croisent, des impasses et une sortie invisible depuis l'entrée. À chaque embranchement, plusieurs directions semblent possibles, mais certaines ramènent sur vos pas.

Les mathématiques oublient alors la forme sinueuse des murs. Elles gardent les carrefours et les extrémités, puis relient deux points lorsqu'un couloir permet de passer de l'un à l'autre. Le labyrinthe devient ainsi un réseau où sortir revient à trouver une suite de passages de l'entrée à la sortie.

Un labyrinthe est un espace connexe de couloirs, d'embranchements et d'impasses, muni d'une entrée et d'une sortie recherchée. « Connexe » signifie qu'il existe un parcours continu entre toute paire de points du réseau modélisé. Un labyrinthe simple ne renferme pas d'îlot de murs isolé ; un labyrinthe à îlots en renferme au moins un.

Pour le modéliser, on associe un sommet à l'entrée, à la sortie, à chaque embranchement et à chaque impasse. Une arête relie deux sommets lorsqu'un couloir direct les joint. Si les couloirs se parcourent dans les deux sens, le graphe est non orienté. Un sens imposé conduit au contraire à un graphe orienté. Le graphe général d'un labyrinthe n'est pas forcément acyclique : une boucle de couloirs produit un cycle.

Avec un plan, résoudre le labyrinthe consiste à chercher un chemin entre le sommet d'entrée et celui de sortie. Sans vue globale, la décision se prend localement. Garder toujours le même mur à droite ou à gauche fonctionne dans le cas simple où l'entrée et la sortie sont sur le bord extérieur et où ce mur reste relié à ce bord. En présence d'un îlot, cette règle peut faire boucler ; il faut alors mémoriser ou marquer les passages déjà parcourus.

Un petit labyrinthe possède une entrée E, une sortie S, trois carrefours A, B et C, et une impasse D. Ses couloirs relient E à A, A à B, A à C, B à D, B à C et C à S. La figure traduit exactement ces données en graphe.

1. Depuis E, on atteint A : E–A est le seul premier passage.
2. À A, on choisit B et l'on mémorise E–A–B.
3. À B, la branche vers D aboutit à une impasse. On revient donc à B et l'on marque B–D comme explorée.
4. On emprunte ensuite B–C, puis C–S. Le chemin trouvé est E–A–B–C–S.
5. Le contrôle consiste à vérifier que chaque paire consécutive de ce chemin correspond bien à un couloir annoncé. C'est le cas pour E–A, A–B, B–C et C–S.

Avec un plan complet, on repère les carrefours et les couloirs, puis on cherche une chaîne continue entre l'entrée et la sortie. Ce modèle évite de se laisser distraire par la longueur ou les courbes du dessin.

Sans plan, on peut garder un mur toujours du même côté lorsque l'entrée et la sortie sont sur le bord extérieur, que le labyrinthe est simple et que ce mur rejoint ce bord. Le geste ne demande alors aucune mémoire des carrefours.

Si l'on revient plusieurs fois au même embranchement, cela peut signaler une boucle, mais aussi un simple retour après une impasse. On préfère alors noter les passages essayés, comme dans l'exemple E–A–B–C–S, afin de ne pas répéter indéfiniment le même détour.

Un chemin n'est pas le labyrinthe entier. Le chemin E–A–B–C–S est une suite de passages menant de l'entrée à la sortie. Le graphe du labyrinthe contient aussi les autres possibilités, notamment l'impasse D et le couloir direct A–C. Le critère est simple : le chemin décrit une solution particulière, tandis que le graphe décrit tout le réseau disponible.

Le suivi d'un mur peut tourner en rond. Autour d'un îlot, garder toujours la main du même côté peut ramener au point de départ sans avoir rencontré la sortie. Le retour au même embranchement avec le même mur est le symptôme à surveiller. Il faut alors mémoriser ou marquer les passages explorés.

Un graphe de labyrinthe n'est pas toujours acyclique. Dans l'exemple, A–B–C–A forme un cycle de trois arêtes. Lui imposer un modèle acyclique supprimerait un couloir réel ou confondrait le réseau avec une sélection de chemins. On conserve les cycles dans le graphe, puis on emploie une recherche qui mémorise les sommets ou les passages déjà visités.

Un plan et une vue locale ne donnent pas le même problème. Sur le plan, toutes les branches sont visibles avant le départ. Dans les couloirs, seules les issues du carrefour présent sont connues. Une stratégie valable avec une vue globale ne doit donc pas être présentée comme une règle locale immédiatement applicable.

Sous-graphe — Pour isoler la portion d'un réseau effectivement explorée sans la confondre avec le labyrinthe complet.

Balades dans le graphe divisoriel — Pour prolonger l'idée de parcours sur un réseau dont les sommets et les liens ont une autre signification.