Welcome to our community

Be a part of something great, join today!

Euler circuits and mazes

Yuuki

Member
Jun 7, 2013
43
I didn't understand the algorithm explained in my textbook. ("Introduction to combinatorics" P.165)

I would an alternative explanation with an example.

Here is the algorithm:

(i) from a new vertex, any edge may be taken;

(ii) from an old vertex, if the edge just traversed was nes, then turn around retake it;

(iii) never use any edge three times.

I used the algorithm in one maze, but at one point it became inevitable for me to take the edge for the third time.
A question regarding (iii); does it disallow me from taking the edge more than three times, or is it okay to take an edge, say, four times?

Also, I don't understand how this works. It was explained that the walk constructed in this way is an Euler circuit in the network formed by doubling each edge in the original. How does this lead to solving the maze?
 

Sudharaka

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
I didn't understand the algorithm explained in my textbook. ("Introduction to combinatorics" P.165)
Hi Yuuki, :)

Can you please provide the exact title and the author of your book. Also what is the name of the algorithm used to find Eularian Circuits?