How Does the Euler Circuit Algorithm Solve Mazes?

In summary, the conversation discusses the confusion around an algorithm explained in a textbook on combinatorics. The algorithm involves taking edges in a specific way, depending on whether they are new or old, and not using any edge more than three times. The person used this algorithm in a maze but was unsure about the rule for using edges more than three times. They also do not understand how this algorithm leads to solving the maze. They ask for an alternative explanation and an example. They also request the title, author, and name of the algorithm used in the textbook.
  • #1
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?
 
Physics news on Phys.org
  • #2
Yuuki said:
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?
 

FAQ: How Does the Euler Circuit Algorithm Solve Mazes?

What is an Euler circuit?

An Euler circuit is a path in a graph that visits every vertex exactly once and ends at the starting vertex.

What is the difference between an Euler circuit and an Euler path?

An Euler circuit visits every vertex exactly once and ends at the starting vertex, while an Euler path visits every vertex exactly once but does not necessarily end at the starting vertex.

Can a maze have an Euler circuit?

No, a maze cannot have an Euler circuit because it does not have a starting vertex and ending vertex. It is designed to have dead ends and multiple paths, making it impossible for a circuit to exist.

How can I determine if a graph has an Euler circuit or path?

A graph has an Euler circuit if and only if every vertex has an even degree. A graph has an Euler path if and only if exactly two vertices have an odd degree. You can determine this by counting the number of edges incident to each vertex.

How can I find an Euler circuit or path in a graph?

An algorithm called Hierholzer's algorithm can be used to find an Euler circuit or path in a graph. This algorithm involves removing edges from the graph while keeping track of the removed edges to create the circuit or path.

Similar threads

MHB How many edges does the graph have?
Replies
4
Views
1K
Circuit analysis via polyhedron
Replies
5
Views
2K
Euler circuit in a directed multigraph
Replies
2
Views
5K
MHB Does K5 contain Eulerian circuits? (why?) If yes, draw them.
Replies
4
Views
7K
MHB Problem on Graph Theory and Algorithms
Replies
2
Views
2K
I Graph Theory: (proof)conditions for Euler Circuit in Digraph
Replies
1
Views
2K
I A way to comprehend the geometry of a hypercube
Replies
2
Views
1K
MHB Proof of Euler Tour in Graphs: In-degree($v$)=Out-Degree($v$)
Replies
1
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
Replies
1
Views
886
A Can the orientation of a body be defined by Euler angles?
Replies
18
Views
1K

Hot Threads

Recent Insights

Back
Top