Graph theory - Start from vertex A, go through all paths in both directions and end up in A again the shortest way

Question

I am trying to find the name of this problem but don't really know how to search for it. The problem is the following:

Find the path in a graph where you start from vertex A, go through all edges exactly two times per edge in BOTH directions (one time in one direction, second time in the opposite) and end up in vertex A again as a last step.

Would love it if somebody gave me some hints as to how this problem is called (because it sounds like a well-known one) and maybe some directions for its solution.

Answer 1

If you just want to traverse each edge of a connected graph once in each direction then you can use a depth-first search:

• Pick any vertex as the starting point.
• From the current vertex and pick any unvisited incident edge.
  • Mark that edge as visited.
  • If the other end of the edge is an unvisited vertex then move to that new vertex, mark it as visited and then repeat the process from that new vertex.
  • If the other end of the edge is a visited vertex then immediately backtrack (traversing the edge a second time but in the opposite direction) and continue processing edges connected to the current vertex.
  • Once all incident edges to the current vertex have been visited then backtrack along the edge which initially brought you to that vertex and return to processing the edges connected to that previous vertex.

Once the DFS has completed then you will have traversed each edge exactly once in each direction.

You could equally use a breadth-first search instead of a depth-first search.

If you want to visit all the edges in a cycle (without backtracking in the middle of the path) then you are looking for an Eulerian circuit/tour and can use Hierholzer's 1873 algorithm:

Wikipedia

• Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
• As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.