So in my algorithms class we started learning the basics of graph theory and (as usual) I had to use the Internet as a supplement to my notes and found it to have more definitions but now I am unsure about what Eulerian paths and Eulerian cycles are, so here is my understanding.
- A walk consists of going through adjacent vertices
- (Not covered in class) A trail is a walk in which the used edges are only used once
- A path is a walk in which the vertices are only visited once (because of this, every edge is only used once, so a path is also a trail)
- (Not covered in class) A circuit is a walk in which the beginning and starting vertices are the same but the edges are only used once, while the vertices can be visited more than once
- A cycle is a walk in which the beginning and starting vertices are the same, and the only repeated vertices are the beginning and starting vertices (so it's a type of circuit).
I hope I understand that ^ right, because my confusion comes from when we learned about Eulerian paths and cycles, for which I have a couple of questions:
- If we have a graph with a set of vertices V and a set of edges E, does a Eulerian path have to visit every single edge in E only once?
- Does a Eulerian path allow visiting vertices more than once? If so why aren't they called Eulerian trails, the name seems kinda confusing otherwise.
- Is a Eulerian cycle a special type of Eulerian path that starts and begins in the same vertex? If so, why don't we call them Eulerian circuits instead of Eulerian cycles?
Thank you for your time