annie122
- 51
- 0
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?
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?