Comment ressortir d'un labyrinthe ?

L'idée salvatrice fut autrefois celle d'Ariane, fille du roi Minos. Ariane aimait Thésée, mais son père l'avait envoyé dans le labyrinthe, où il devait être tué par le monstrueux Minotaure.

Pour sauver la vie de Thésée, Ariane lui remit secrètement un glaive et une pelote de fil, dont il fixa l'extrémité à l'entrée du labyrinthe. Ayant trouvé et tué le Minotaure, Thésée put retrouver le chemin de la sortie à l'aide du fil. Le fil d'Ariane est encore utilisé aujourd'hui par les spéléologues, par exemple. Mais comment faire quand on n'a pas de fil ? Est-on perdu à jamais ?

La solution la plus simple consiste à suivre la paroi avec sa main : la paroi droite avec sa main droite ou la paroi gauche avec sa main gauche. Ainsi, on est assuré de retrouver la sortie – même si ce n’est pas le chemin le plus court, car il faut parcourir tout le labyrinthe. On visitera chacune des places et l’on parcourra deux fois chacun des couloirs : une fois dans chaque sens.

L'entrée et la sortie peuvent bien être différentes, la méthode de la main au mur nous sauvera toujours – par la droite ou par la gauche. Mais dans certains labyrinthes, on ne parcourt ainsi qu'une partie des couloirs et on n'est pas certain d'atteindre la place centrale, qui est pourtant l'objectif ultime. Comment atteindre à tous les coups la place centrale ? Que faire si l’on s'est aventuré dans un labyrinthe et qu'on a perdu l'orientation ?

Dans les labyrinthes où la méthode de la main au mur ne permet pas de parcourir tous les couloirs, il peut arriver qu'on ne retrouve pas la sortie et qu'on tourne éternellement en rond. Existe-t-il une méthode qui permettrait d'atteindre un point quelconque et de retrouver ensuite la sortie ?

Trémaux a proposé une telle méthode à la fin du siècle dernier, à Paris. Sa technique nécessite cependant de repérer le point de départ et d'arrivée de chaque chemin, afin de savoir par quel couloir on est arrivé et si l'on s'est déjà trouvé au même endroit. Le procédé de Trémaux fonctionne seulement si, parmi les chemins qui mènent à un lieu quelconque, on sait lesquels on a déjà suivi et combien de fois.

Colorions en vert les couloirs qui n'ont pas encore été parcourus, en jaune ceux qui ont été parcourus une fois et en rouge ceux parcourus deux fois. Notre promenade débute à un endroit quelconque, par exemple l'entrée.

La règle de conduite est la suivante : Quand on arrive dans une impasse, on rebrousse chemin dans le même couloir. Celui-ci passe alors en rouge et devient interdit à la circulation. Tant que c'est possible, on suit toujours un chemin vert. Il devient jaune, car il a déjà été parcouru une fois. Quand on arrive à un croisement, on poursuit son chemin par l'un des chemins verts. Si toutes les issues sont jaunes, c'est qu'on s'est déjà trouvé à cet endroit et il faut alors emprunter une deuxième fois un couloir jaune. Celui-ci passe alors au rouge et ne pourra plus être emprunté par la suite. Pour éviter de parcourir très souvent certains couloirs et d'en négliger complètement certains autres, il est important de marquer chaque lieu, pour savoir si l'on y est déjà venu et combien de fois on a emprunté un couloir.

La méthode de Trémaux ne fonctionne qu'à cette condition, car à la fin, tous les couloirs sont rouges : on a emprunté chaque chemin exactement deux fois et atteint chaque place. Certes..., mais pourquoi la méthode de la main au mur qui permet de parcourir certains labyrinthes très facilement et d'y atteindre chaque place s'avère impuissante dans d'autres ?

Pour simplifier, on peut représenter un labyrinthe par un graphe. Le critère important, c'est le nombre d'arêtes qui relient entre eux deux nœuds distincts. Ainsi se présente le graphe du premier labyrinthe. C'est un graphe connexe. Connexe signifie qu'il est possible d'atteindre chaque nœud.

Tel n'est pas le cas pour le second labyrinthe. Il possède des circuits fermés ; cela signifie que les points de départ et d'arrivée sont identiques ; mais aucun nœud et aucune arête ne se répète. La théorie des graphes constitue un outil mathématique important. Elle sert notamment à résoudre des problèmes de logistique. Par exemple, des problèmes de transport, la régulation des feux de circulation ou encore des divertissements mathématiques, comme la conception d’un plateau de jeu.

Le graphe a été inventé en 1736 par le mathématicien Leonhard Euler. À l'époque, il lui fallait résoudre le problème suivant : À Königsberg, le fleuve Pregolia se sépare en deux bras, délimitant notamment l'île de Kneiphof. À l'époque d'Euler, les quatre quartiers de la ville étaient reliés par sept ponts. Le problème d'Euler était le suivant :

Peut-on faire une promenade à travers toute la ville en ne traversant qu'une seule fois chacun des ponts ? Euler trouva la solution en inventant le graphe : les zones A, B, C et D séparées par le fleuve forment les nœuds du graphe. Ses arêtes sont les ponts, qui relient chacun deux zones. Ainsi, Euler put démontrer qu'une telle promenade est impossible, car chacun des quatre nœuds possède un nombre impair d'arêtes.