Dictionary of Mathematical Eponymy: Trémaux’s Algorithm

I recently had the chance to employ this one, but didn’t manage to: it turns out that four three-to-six-year-olds are not especially interested in putting down markers and following rules, they just want to run around the maize maze and say “maize maze” and make “amazing” jokes1

What is Tremaux’s algorithm?

Tremaux’s algorithm is a method for finding your way out of a maze by putting down markers to show where you’ve been. Assuming the maze has well-defined passages and junctions, here’s what you do:

  • Every time you enter or leave a passage, you put down a marker.
  • Every time you enter a junction:
    • If all of the passages are unmarked, take one of them (it doesn’t matter which)
    • Otherwise, if the passage you’ve just emerged from only has one mark, go back along it (putting a second marker with the one you’ve just put down).
    • If the path you’ve emerged from has two marks, go along whichever other path has the fewest marks on it (it doesn’t matter which).

This algorithm guarantees finding an exit if it exists; a path (not necessarily the shortest path) from the starting point to the exit can be found by following all of the passage entrances and exits with a single marker.

Why is it important?

It gets you out of mazes. Next!

Oh, all right. It’s a particular case of a depth-first search which has applications in graph theory - particularly in finding spanning trees of graphs, infinite or otherwise.

Who was Charles Pierre Tremaux?

Charles Pierre Tremaux (1859-1882) is another hard-to-track down character from the history of maths. He’s referred to as ‘an author’, possibly from Charrecey in Burgundy. Edouard Lucas refers to him as an ex-student of the Ecole Polytechnique and a telegraph engineer.

As always, if you know more or better, I’d love to hear about it!

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

  1. That last one might be more the parents. OK, the me. []

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter